精华内容
下载资源
问答
  • 对数组进行快速排序

    2020-11-08 20:49:23
     //递归的对t左边进行排序 quicksort(a,i+1,high); //递归的对右边进行排序 } } int main(){ int a[100]; int n; cout请输入数组的大小:" cin>>n; for(int i=0;i cin>>a[i]; } quicksort(a,0,n-1); for(i=0;i ...

    #include<iostream>
    using namespace std;

    void quicksort(int a[],int low,int high){
        int t;
        int i=low,j=high;
        if(low<high){
            t=a[low];
            while(i<j){                        //下边这个循环完成了一趟循环,数组中小于t的关键字放在左边,大于t的放在右边
                while(j>i&&a[j]>=t)            //从右往左扫描找到一个小于t的关键字
                    --j;
                if(i<j){
                    a[i]=a[j];                //找到以后放在t的左边
                    ++i;                    //i右移一位
                }
                while(i<j&&a[i]<=t)            //从左往右扫描找到一个大于t的关键字
                    ++i;
                if(i<j){
                    a[j]=a[i];                //找到以后放在t的右边
                    --j;                    //j左移一位
                }
            }
                a[i]=t;                        //t放在最终的位置
                quicksort(a,low,i-1);        //递归的对t左边进行排序
                quicksort(a,i+1,high);        //递归的对右边进行排序
        }
        
    }

    int main(){
        int a[100];
        int n;
        cout<<"请输入数组的大小:"<<endl;
        cin>>n;
        for(int i=0;i<n;i++){
            cin>>a[i];
        }
        quicksort(a,0,n-1);
        for(i=0;i<n;i++){
            cout<<a[i]<<" ";
        }
        return 0;
    }

    展开全文
  • 使用SOrt方法对数组进行快速排序。程序可以完全正确运行,
  • C#使用sort方法对数组进行快速排序
  • 利用堆对数组进行快速排序,以对数组进行升序排序为例,用最大堆可以实现。实现的方法如图所示,一图解千语。先将最大堆的顶结点和尾结点交换,在堆中排除掉尾结点,接着对新的堆进行重新构建一个最大堆。依次类推,...

    利用堆对数组进行快速排序,以对数组进行升序排序为例,用最大堆可以实现。实现的方法如图所示,一图解千语。先将最大堆的顶结点和尾结点交换,在堆中排除掉尾结点,接着对新的堆进行重新构建一个最大堆。依次类推,直到最后堆的元素个数为0。
    在这里插入图片描述在前期代码实现的基础上进行了优化,直接将要排序的数组传进去,不用另外申请额外的空间。完整的代码实现如下:

    /*
       利用堆对数组进行快速排序,以对数组进行升序排序为例,用最大堆
    */
    #include<Windows.h>
    #include<iostream>
    using namespace std;
    #define DEFAULT_CAPACITY 100
    typedef struct _heap {
    	int* arr;
    	int size;//当前已存储的元素个数
    	int capacity;//最大的存储容量
    }heap;
    bool initHeap(heap& h, int* array, int size);
    void buildHeap(heap& h);
    void adjustHeapDown(heap& h, int i);
    void heapSort(heap& heap);
    bool popMax(heap& heap, int& value);
    
    int main() {
    	//01 建最大堆
    	int arr[] = { 4, 99, 23, 35, 23, 9, 1, 39, 21, 324, 231, 0 };
    	int size = sizeof(arr) / sizeof(arr[0]);
    	heap heap;
    	if (initHeap(heap, arr, size)) {
    		fprintf(stderr, "建最大堆成功!");
    	}
    	else {
    		fprintf(stderr, "建最大堆失败!");
    		exit(1);
    	}
    	cout << "遍历整个最大堆!" << endl;
    	for (int i = 0; i < heap.size; i++) {
    		cout << heap.arr[i] << " ";
    	}
    
    	//02 利用最大堆对数组进行排序
    	heapSort(heap);
    	cout << "数组排序的结果如下:" << endl;
    	for (int i = 0; i < size; i++) {
    		cout << arr[i] << " ";
    	}
    
    
    	cout << endl;
    	system("pause");
    	return 0;
    }
    bool initHeap(heap& heap, int* array, int size) {
    	
    	heap.arr = array;
    	if (!heap.arr) return false;
    	heap.size = size;
    	heap.capacity = size;
    
    	if (size > 0) {
    		//建堆的第一种方法
    		buildHeap(heap);
    		//建堆的第二种方法
    		/*for (int i = 0; i < size; i++) {
    			insertHeap(heap, arr[i]);
    		}*/
    	}
    	return true;
    }
    void buildHeap(heap& heap) {
    	for (int i = (heap.size - 2) / 2; i >= 0; i--) {//从最后一个父节点开始
    		adjustHeapDown(heap, i);
    	}
    }
    void adjustHeapDown(heap& heap, int index) {
    	/*判断否存在大于当前节点的子节点,如果不存在 ,则堆本身是平衡的,
    	不需要调整;如果存在,则将最大的子节点与之交换,交换后,如果这个子节点还
    	 有子节点,则要继续按照同样的步骤对这个子节点进行调整*/
    	int cur = heap.arr[index];//当前待调整的结点
    	int parent, child;
    	for (parent = index; (parent * 2 + 1) < heap.size; parent = child) {
    		child = 2 * parent + 1;
    		if ((child + 1) < heap.size && heap.arr[child] < heap.arr[child + 1]) {
    			child++;
    		}
    		if (heap.arr[child] > cur) {
    			heap.arr[parent] = heap.arr[child];
    			heap.arr[child] = cur;
    		}
    		else {
    			break;
    		}
    	}
    }
    
    bool popMax(heap& heap, int& value) {
    	if (!heap.size) return false;
    	/*value = heap.arr[heap.size - 1];
    	heap.size--;*/
    	value = heap.arr[0];
    	heap.arr[0] = heap.arr[--heap.size];//将尾结点赋值给头结点
    	adjustHeapDown(heap, 0);
    	return true;
    }
    void heapSort(heap& heap) {
    	if (heap.size < 1) return;
    	while (heap.size > 0) {
    		int tmp = heap.arr[0];
    		heap.arr[0] = heap.arr[heap.size-1];
    		heap.arr[heap.size - 1] = tmp;
    		heap.size--;
    		adjustHeapDown(heap, 0);
    	}
    }
    
    
    展开全文
  • //快速排序升序的实现原理 //比pivot中轴小的到左边,比pivot大的到右边 //high小而赋值(给low),大而移动 //low小而移动,大而赋值(给high) //low/high相等时,此轮结束 #include <stdio.h> void ...

     

    //快速排序升序的实现原理
    //比pivot中轴小的到左边,比pivot大的到右边
    //high小而赋值(给low),大而移动
    //low小而移动,大而赋值(给high)
    //low/high相等时,此轮结束

    #include <stdio.h> void quickSortUp(int* p,int low,int high)// 升序排列 { if(low < high) { int l = low; int h = high; int pivot = p[l]; while(l < h)//相等时就达到了pivot要填的下标位置 //注意点1 这里不能使用<=,多了=会死循环 { while(p[h] >= pivot && h>l)//注意点2 这里不能使用<,少了=会死循环 { h--; } p[l] = p[h]; while(p[l] <= pivot && l<h)//注意点2 这里不能使用<,少了=会死循环 { l++; } p[h] = p[l]; } int pos = h;//pos = l; p[pos] = pivot; quickSortUp(p,low,pos-1);//左半边 quickSortUp(p,pos+1,high);//右半边 } } //快速排序 降序实现 void quickSortDown(int* p,int low,int high)//降序排列 { if(low < high) { int l = low; int h = high; int pivot = p[l]; while(l < h)//注意点1 这里不能使用<=,多了=会死循环 { while(p[h] <= pivot && h>l)//注意点2 这里不能使用<,少了=会死循环 { h--; } p[l] = p[h]; while(p[l] >= pivot && l<h) { l++; } p[h] = p[l]; } int pos = h;//pos = l; p[pos] = pivot; quickSortDown(p,low,pos-1);//左半边 quickSortDown(p,pos+1,high);//右半边 } } int main(void) { int arrtest[] = {6,1,7,4,9,8,2,3,5,0,9}; // int arrtest[] = {9,1,7,4,9,8,2,6,9,3,5,0,9}; quickSortDown(arrtest,0,sizeof(arrtest)/sizeof(*arrtest)-1); int i; for(i = 0;i<sizeof(arrtest)/sizeof(*arrtest);i++) { printf("%3d",arrtest[i]); } putchar(10); return 0; }

     

    转载于:https://www.cnblogs.com/ZhuLuoJiGongYuan/p/9523352.html

    展开全文
  • 快速排序: 使用快速排序算法对数组进行排序 题目 一个数组有 N 个元素,使用快速排序对其进行排序输出(本题还会人工阅卷,请使用快速排序算法进行排序) 输入描述: 输入为两行。 第一行一个整数n(1 ≤ n ≤ 100000),...

    快速排序: 使用快速排序算法对数组进行排序

    题目

    一个数组有 N 个元素,使用快速排序对其进行排序输出(本题还会人工阅卷,请使用快速排序算法进行排序)
    输入描述:
    输入为两行。 第一行一个整数n(1 ≤ n ≤ 100000),表示一共有n个元素 第二行为n个数,即每个元素,每个整数都在32位int范围内。以空格分隔。
    输出描述:
    输出一行,即排序之后的数组,以空格分隔,行末无空格

    示列

    输入

    10 293 108 161 783 376 265 330 598 646 812
    

    输出

    108 161 265 293 330 376 598 646 783 812
    

    练习地址

    牛客网快速排序练习地址

    解题代码

    在牛客网的编译环境上有一个测试用例过不了,但是在本地编译,同样的测试用例就可以过,有时间再研究一下。

    #include<iostream>
    #include<vector>
    using namespace std;
    
    void swap_two( int &first_number, int &second_number )
    {
        int swap = first_number;
        first_number = second_number;
        second_number = swap;
    }
    
    int quick_sort( vector<int> &vector_sort, int first_point, int last_point )
    {
        if( first_point >= last_point )      //传进来的first_point 可能会大于 last_point,因为下面quick_sort( vector_sort, left_point + 1, last_point )
            return 0;
    
        int left_point = first_point + 1;   // left_point赋值的时候 first_point + 1,防止quick_sort( vector_sort, first_point, left_point - 1 )时小于first_point
        int right_point = last_point;
        int benchmark = first_point;
        while( left_point < right_point )
        {
            if( vector_sort[right_point] > vector_sort[benchmark] ) right_point--;
            else if( vector_sort[left_point] <= vector_sort[benchmark] ) left_point++;
            else swap_two(vector_sort[left_point], vector_sort[right_point]);
        }
    
        swap_two(vector_sort[left_point], vector_sort[benchmark]);
    
        quick_sort( vector_sort, first_point, left_point - 1 );
        quick_sort( vector_sort, left_point + 1, last_point );
        return 0;
    }
    
    int main()
    {
        int size = 0;
        cin >> size;
        int num;
        vector<int> quick_sort_v;
        quick_sort_v.reserve(size);
        do
        {
            cin >> num;
            quick_sort_v.push_back(num);
        } while (getchar() != '\n');
    
        for(auto i : quick_sort_v )
            cout << i << ' ';
        cout << endl;
    
        quick_sort(quick_sort_v, 0, quick_sort_v.size() - 1);
    
        for(auto i : quick_sort_v )
            cout << i << ' ';
        cout << endl;
    }
    
    展开全文
  • package main ...//对数组进行冒泡排序 func BubbleSort(values [] int) { var arrlen int =len(values) for i:=0;i;i++{ for j:=0;j(values)-1-i;j++{ if values[j]>values[j+1]{ val
  • 本例快排不对原数组进行排序,而是对原数组下标index数组进行排序 package aaaaaa; import java.math.*; import java.util.*; public class Main { public static int maxn=10000+10; public static int a[]=new...
  • Java 实现快速排序对数组进行排序

    千次阅读 2018-12-02 15:49:13
    基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据要小,然后再按照这个方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据...
  • * 用快速排序方法进行数组排序 * User: knight * Date: 2017/11/3 * Time: 13:34 */ /** * 快速排序: * 再数组中去一个值作为标准(一般以数组第一个元素作为标准) * 遍历这个这个数组除标准...
  • 基本思想是:通过一趟排序将要排序数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据小,然后再按此方法对这两部分数据分别进行快速排序。整个排序过程可以递归进行,以此是整个数据变成有序...
  • 在实际开发中,有很多场景需要我们将数组...对数组元素进行排序的方法有很多种,比如冒泡排序、归并排序、选择排序、插入排序、快速排序等,其中最经典最需要掌握的是「冒泡排序」。 以从小到大排序为例,冒泡排序...
  • java对数组进行排序

    2017-12-07 22:40:32
    JAVA中在运用数组进行排序功能时,一般有四种方法:快速排序法、冒泡法、选择排序法、插入排序法。 快速排序法主要是运用了Arrays中的一个方法Arrays.sort()实现。 冒泡法是运用遍历数组进行比较,通过不断的比较...
  • 在实际开发中,有很多场景...对数组元素进行排序的方法有很多种,比如冒泡排序、归并排序、选择排序、插入排序、快速排序等,其中最经典最需要掌握的是「冒泡排序」。以从小到大排序为例,冒泡排序的整体思想是这...
  • 对数组进行排序

    2012-04-15 22:00:07
    比如有一个整型数组:  int[] intArray = new int[] {4, 1,...你这个时候是否在想快速排序的算法?看看下面的实现方法:  import java.util.*; public class Sort{ public static void main(String[] args){ ...
  • VC 对数组进行排序的一个算法实例,基于函数指针的数组,代码中一共包含四种排序方法:泡沫排序法(bubble)、插入排序法(insertion)、快速排序法(quick)和选择排序法(selection)。在头文件中还使用了模板技术...
  • OCdemo - 05 OC中快速对数组进行排序

    千次阅读 2015-10-14 20:19:51
     // 冒泡排序  for (int i = 0; i ; i++) {  for (int j = 0; j ; j++) {  if ([marray[j] compare:marray[j + 1]] == NSOrderedDescending) {  //升序排列  [marray exchangeObjectAtIndex:j ...
  • 首先,对数组元素进行排序方法总结为以下两类: 一、简单排序算法(时间复杂度O(n*n)) 1.插入排序 2.选择排序 3.交换排序,即冒泡排序 二、先进排序算法(时间复杂度O(n*logn)) 1.快速排序 2.归并...
  • 设计了一个网页,使用不同的排序算法(例如Heap,Merge,Quick和Bubble)对数组进行可视化排序。使用ReactJS来提高对网站内用户界面设计,测试和调试的理解改进了数据结构和算法的概念以及前端端开发 堆排序 合并...
  • 对数组元素进行排序的方法有很多种,比如冒泡排序、归并排序、选择排序、插入排序、快速排序等,其中最经典最需要掌握的是「冒泡排序」。 以从小到大排序为例,冒泡排序的整体思想是这样的: 从数组头部开始,不断...
  • Java 使用sort方法对数组进行排序

    千次阅读 2018-12-02 19:48:39
    再使用冒泡排序、快速排序等方式进行排序时,需要手动编写一堆代码,比较麻烦。因此Java中的Arrays类提供了一个sort方法,使用该方法可以很方便的对各种数组进行排序,大大降低了数组排序的难度。sort()方法有很多...
  • 2011年12月19日,参考网上用C语言实现的快速排序,经过一番修改后,用shell(我的测试环境为centos5的bash-v3.x)实现了相同功能:对数组进行升序排序。 注:如果代码框里的代码复制出来后显示异常,就麻烦下载附件...
  • 通过Arrays.sort()方法对数组进行排序

    千次阅读 2019-07-23 22:44:31
    一、Arrays.sort()方法是一种快速排序方法,它合适用于元素少于47个数的排序,具体排序可以参考下面的代码。 二、它可以用于数组的从小到大也可以用于数组的从大到小进行排序,下面讲解一下四种排序的方法。 a) ...
  • 项目 4-1 对数组进行排序  一维数组以基于索引的线性列表来组织其中的数据,这是一种很好的可用于排序的数据结构。在这个项目中,我们将学习一种简单的对数组进行排序的方法。或许你已经知道有多种不同的排序算法。...
  • 5,编写一个控制台程序,要求用户输入一数字用空格间隔,对用户...Array.Sort()方法,CLR提供的排序方法,使用的是快速排序。 string str = Console.ReadLine(); string[] strArray = str.Split(' '); ...
  • 常用的排序算法有:冒泡排序、选择排序、插入排序、快速排序、希尔排序等。冒泡排序算法(Bubble Sort)是一种流行但低效的排序算法。 1、冒泡排序的原理  冒泡排序的原理是反复比较待排序数组中所有相邻的两个...
  • 快速排序

    2021-04-21 18:56:47
    需求:随机生成一个10个元素的int数组,并对数组进行快速排序 /* * 需求;100内随机一个10个int数据类型的数组,并对数组中的元素进行快速排序(降序) * * * */ public class Test { public static void main...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 728
精华内容 291
关键字:

对数组进行快速排序