C语言的快速排序及分析
一、快速排序
一般而言，学习C语言较为简单的排序，则是直接插入排序和冒泡排序。而这两者在数据较大的时候则速度就很慢了。
快速排序的速度大于前者并且较为简单，所以写下学习快速排序的过程，供以后复习。
快速排序的原理：
1、快速排序是分治思想，将数列分解排序。
2、具体过程是：先任取一个值作为基准，然后将小于该基准值的数放在该数的左侧，大于该数的数放在右侧。
3、然后就是重复地将左侧与右侧持续进行该过程，直到将其分成两个数为一组，然后比较交换。这样，就实现了排序。
具体实现：
先定义一个交换函数，方便后续的交换
1 void swap(int a[],int i,int j) 2 { 3 a[i]=a[i]^a[j]; 4 a[j]=a[i]^a[j]; 5 a[i]=a[i]^a[j]; 6 }
接下来是快速排序的具体算法
1 void quicksort(int a[],int low,int high) 2 { 3 if(low<high)//保证分开的组的成员在两个以上才需要排序 4 { 5 int last=low;//last为基准，并设置为组的第一个数 6 for(int i=last+1;i<=high;i++)//从基准后开始循环 7 { 8 if(a[i]<a[last])//如果小于基准，则放在基准的左侧 9 { 10 swap(a,last,last+1);//将基准与后一位交换 11 last++; //交换后的新基准 12 if(i!=last) // 13 swap(a,last-1,i); 14 } 15 } 16 quicksort(a,low,last); 17 quicksort(a,last+1,high); //对两部分的数继续上述过程 18 } 19 }
上述代码是我在看到快速排序的原理后自己写的，显然满足其原理，而且较为简单理解，毕竟从一端开始比较。
但是实际的快速排序并不是这样来的，而是更进一步的优化，采用了从两端比较的方式。
下面贴出具体代码：
1 void quicksort2(int *a,int low,int high) 2 { 3 int i = low; //i,j分别从首端和尾端开始变化 4 int j = high; 5 int temp = a[i]; //temp作为比较的基准 6 7 if( low < high)//保证有数可排 8 { 9 while(i < j) 10 { 11 while((a[j] >= temp) && (i < j))//基准第一位，所以先从后开始 12 { //直到循环到比其小的时候开始将后赋值给前一位 13 j--; 14 } 15 a[i] = a[j];//这里采用赋值而不是交换，在循环外会把丢失的temp补上 16 while((a[i] <= temp) && (i < j)) 17 { 18 i++; 19 } 20 a[j]= a[i];//同上 21 } 22 a[i] = temp; 23 quicksort2(a,low,i-1); 24 quicksort2(a,j+1,high); 25 } 26 }
以上就是快速排序的过程了。
若是仔细观察的话会发现一个小细节，那就是快排的每一次循环完成后都完成了一个的数的排序——那就是基准值。
快排的原理是将大于基准值的数放在后面，小于的放在前面。这样，每次的排序后基准值的位置确定。那么久可以演化为
另一种问题：求解一组数中的第n大的数。这样可以不完全排序就能解出答案。
具体代码如下：
1 int getresult(int *a,int low,int high,int k) 2 { 3 int i=low; 4 int j=high; 5 int temp=a[i]; 6 if(low<high) 7 { 8 while (i<j) 9 { 10 while ((a[j]>=temp)&&(i<j)) 11 { 12 j--; 13 } 14 a[i]=a[j]; 15 while ((a[i]<=temp)&&(i<j)) 16 { 17 i++; 18 } 19 a[j]=a[i]; 20 } 21 a[i]=temp;//前面代码与快排一模一样，不做赘述 22 if(i==k-1)//如果基准刚好为所求，则返回 23 return a[i]; 24 else if(i>high-k+1)//下面根据大小来选择对哪边进行重复 25 getresult(a,low,i-1,k); 26 else 27 getresult(a,j+1,high,k); 28 } 29 }
恩，具体就这些。
版权声明：本文为feng124原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。