本文共 1200 字，大约阅读时间需要 4 分钟。

（1）快排的思想

实际上每一个step 都是将序列分别为两部分，前半部分小于它，后半部分大于它（图中以5为例，我们考虑增序） 然后对前半部分和后半部分进行同样的操作（递归）

下面是详细的步骤：

（1）以5作为中枢变量，令i指向第二个下标，j指向最后一个下标 （2）先让j向前移动，直到遇到小于5的数字，再让i向后移动（i++），直到遇见大于5的数8，交换两个数字的位置【不断重复】 9>5,那么i指针不动，j向前移动直到和i指向同一个位置（此时结束） 最后一步：将5和1交换位置（i或j所指的位置） 递归，对前半部分{1，2}和后半部分{9，7，8}，执行相同的操作

（2）快排的代码实现

#include 
   
    /* 不稳定，o(nlogn) */typedef int elemtype; int partition(elemtype *a,int  start,int  end);void QuickSort(elemtype *a,int start,int end){//将数组和其起始位置坐标传入      if (start >= end) { return;} //递归终止条件，相当于排序的子数组中只有一个值      int pivotIndex = partition(a, start, end);//通过patition函数得到pivot中枢的值 	 QuickSort(a,start,pivotIndex-1); //对左边子列递归 ，pivot为中枢 	 QuickSort(a,pivotIndex+1,end);//对右边子列递归 }int partition(elemtype *a,int  start,int  end){	int pivotValue = a[start];//将第一个数作为中枢量	int pivotIndex = start;	int i = start+1;//指向第二个元素 	int j = end; //指向最后一个元素 	while(i
    
     =pivotValue&&i
     
      a[i]){	 a[pivotIndex]=a[i];	 a[i]=pivotValue;	 pivotIndex=i;//中枢变量新的位置 ，或者用j也行     }	 return pivotIndex;} int main(){	int a[10]={18,3,34,-22,5,19,78,66,23,55};	QuickSort(a,0,9);	for(int i=0;i<10;i++){		printf("%d ",a[i]);	}	return 0;}
     
    
   

注意点：必须从右边开始,因为基数选的最左边 ,主要就是从左边开始，你不能保证你最后交换的那个数，是小于等于左边的。

转载地址：http://qrqen.baihongyu.com/