之前关于快速排序一直比较模糊，网上有几种常见写法：
方法一：
1 void quickSort(int s[], int l, int r) 2 { 3 if (l< r) 4 { 5 int i = l, j = r, x = s[l]; 6 while (i < j) 7 { 8 while(i < j && s[j]>= x) // 从右向左找第一个小于x的数 9 j--; 10 if(i < j) 11 s[i++] = s[j]; 12 while(i < j && s[i]< x) // 从左向右找第一个大于等于x的数 13 i++; 14 if(i < j) 15 s[j--] = s[i]; 16 } 17 s[i] = x; 18 quickSort(s, l, i - 1); // 递归调用 19 quickSort(s, i + 1, r); 20 } 21 }
方法二：
1 1 void quicksort(point list[],int m,int n) 2 2 { 3 3 int key,i,j,k; 4 4 if( m < n) 5 5 { 6 6 k = choose_pivot(m,n); 7 7 if(m != k) 8 8 swap(list[m],list[k]); 9 9 key = list[m].len;10 10 i = m+1;11 11 j = n;12 12 while(i <= j)13 13 {14 14 while((i <= n) && (list[i].len <= key)) i++;15 15 while((j >= m) && (list[j].len > key)) j--;16 16 if( i < j)17 17 swap(list[i],list[j]);18 18 }19 19 // 交换两个元素的位置20 20 if(m != j)21 21 swap(list[m],list[j]);22 22 // 递归地对较小的数据序列进行排序23 23 quicksort(list,m,j-1);24 24 quicksort(list,j+1,n);25 25 26 26 }27 27 28 28 }
下面介绍如题的一种快速排序，大概思想是：（1）选取枢纽值是采用三数中值法 （2）当数据元素个数很小时，采用插入排序
1 #define cutoff 5 //定义数值，当待排序的个数小于等于cutoff，采用插入排序 2 3 void QuickSort( int A[], int N )//驱动例程 4 { 5 Qsort( A, 0, N-1 ); 6 } 7 8 /* 9 三数中值法，就是把左端，右端和中心位置的三个元素进行排序，然后将中心位置的主元换到倒数第二个位置。10 返回主元的值11 */12 int Median3( int A[], int left, int right)13 {14 int center;15 16 center = left + ( right - left ) / 2; //数很大时，避免数据溢出 17 18 if( A[left] > A[center] )19 swap(A[left],A[center]);//传递的是引用，直接用c++的库函数即可20 if( A[left] > A[right] )21 swap( A[left], A[right] );22 23 if( A[center] > A[right] )24 swap( A[center], A[right] );25 26 swap( A[center], A[right-1] );27 28 return A[right-1];29 }30 31 /*32 快速排序主例程33 */34 void Qsort( int A[], int left, int right )35 {36 int i,j;37 int Pivot38 i = left;39 j = right - 1;40 41 if( left + cutoff <= right )42 {43 Pivot = Median3( A[], left, right );44 for( ; ; )45 {46 while( A[++i] < Pivot );47 48 while( A[--j] > Pivot );49 50 if( i< j )51 swap( A[i], A[j] );52 else53 break;54 }55 swap( A[right-1], A[i] );56 57 Qsort( A, left, i-1);58 Qsort( A, i+1, right);59 }60 else61 {62 InsertionSort( A+left, right - left + 1 );63 }64 65 }