快速排序：
快速排序也是一种分治的递归算法。
快速排序算法基本思想：取数组S中任一元素v，作为枢纽元。用枢纽元将S中的元素分成俩部分，对这两部分分别再次进行快速排序。当S中元素个数是0或1时，则返回。因为快速排序要根据枢纽元将元素分成俩部分，因此，枢纽元的选取对程序的时间复杂度是有影响的。一般的枢纽元选取策略是取左端、右端和中间位置上的三个元素的中值作为枢纽元。
程序实现：#include <iostream> using namespace std; typedef int ElementType; void print(int a[], int n){ for(int j= 0; j<n; j++) { cout<<a[j] <<" "; } cout<<endl; } void Swap( ElementType *Lhs, ElementType *Rhs ) { ElementType Tmp = *Lhs; *Lhs = *Rhs; *Rhs = Tmp; } void InsertionSort( ElementType A[ ], int N ) { int j, P; ElementType Tmp; for( P = 1; P < N; P++ ) { Tmp = A[ P ]; for( j = P; j > 0 && A[ j - 1 ] > Tmp; j-- ) A[ j ] = A[ j - 1 ]; A[ j ] = Tmp; } } ElementType Median3( ElementType A[ ], int Left, int Right ) { int Center = ( Left + Right ) / 2; if( A[ Left ] > A[ Center ] ) Swap( &A[ Left ], &A[ Center ] ); if( A[ Left ] > A[ Right ] ) Swap( &A[ Left ], &A[ Right ] ); if( A[ Center ] > A[ Right ] ) Swap( &A[ Center ], &A[ Right ] ); Swap( &A[ Center ], &A[ Right - 1 ] ); /* Hide pivot */ return A[ Right - 1 ]; /* Return pivot */ } #define Cutoff ( 3 )//确保有三个元素用于查找枢纽元 void Qsort( ElementType A[ ], int Left, int Right ) { int i, j; ElementType Pivot; if( Left + Cutoff <= Right )//对于小数组来说，插入排序的效果更好 { Pivot = Median3( A, Left, Right ); i = Left; j = Right - 1;//i是左端第一个，j是右端第二个元素。最右端位置存放枢纽元。 for( ; ; ) { while( A[ ++i ] < Pivot ){ }//先将i+1，移过左端第一个，再和枢纽元进行比较，因为在选择枢纽元的时候已经将A[Left]与枢纽元比较过了，而且 while( A[ --j ] > Pivot ){ }//先将j-1，移过右端第二个，再和枢纽元进行比较，因为在选择枢纽元的时候已经将右端第二个与枢纽元比较过了 if( i < j ) Swap( &A[ i ], &A[ j ] );//将i移过小于枢纽元的元素，将j移过大于枢纽元的元素。若i仍然小于j。就交换指针i和j所在的元素。 else break;//否则就结束。 } Swap( &A[ i ], &A[ Right - 1 ] ); //将枢纽元放到左右部分元素交汇处。 Qsort( A, Left, i - 1 );对左右部分递归调用快速排序 Qsort( A, i + 1, Right ); } else /* Do an insertion sort on the subarray */ InsertionSort( A + Left, Right - Left + 1 ); } void Quicksort( ElementType A[ ], int N ) { Qsort( A, 0, N - 1 ); } int main() { int a[10]={8,1,4,9,0,3,5,2,7,6}; print(a,10); Quicksort(a,10); print(a,10); system("pause"); return 0; }
程序实现分析：
十个元素：
先找出第一个位置、最后一个位置以及中间位置处的元素的中间值[（left+right）/2]向下取整作为枢纽元，找到枢纽元与最后一个位置处的值交换。
初始时刻i指向第一个元素，j指向倒数二个元素，最后一个位置存放的是枢纽元。此时，i所指向的元素大于枢纽元，停止。j往前移动指向2，j所指向的元素小于枢纽元，停止。将i和j所指向的值进行交换。
i向后移动，直到i指向9，大于枢纽元，停止。j往前移动指向5，j所指向的元素小于枢纽元，停止。将i和j所指向的值进行交换。
这时，i继续向后移，移过那些小于枢纽元的元素，直到i指向9，大于枢纽元，停止。j向前移移过大于枢纽元的元素，直到j指向3，小于枢纽元，停止。
此时i>j.i以后的元素全部大于枢纽元，i以前的元素全部小于枢纽元。因此，不再交换。
这时，整个数组被枢纽元分成俩部分，第一部分：left到i-1位置上的元素均小于枢纽元。第二部分：i+1到right部分的元素均大于枢纽元。分别对这两部分再次进行快速排序。最终得以将数组全部排好序。
简易算法实现：
#include<iostream> using namespace std; #define MAX 255 void QuickSort(int *a,int left, int right) { if (left >= right) return; int mid = a[left]; int i = left+1; int j = right; int temp; while (1) { while (a[i] < mid) i++; while (a[j] > mid) j--; if (i < j) { temp = a[j]; a[j] = a[i]; a[i] = temp; } else break; } temp = a[left]; a[left] = a[j]; a[j] = temp; QuickSort(a,left,j-1); QuickSort(a, j+1, right); } int main() { int a[MAX]; int n=0; cout << "请输入需要排序的数的个数：" << endl; cin >> n; cout << "请依次输入每个数：" << endl; for (int i = 0; i < n; i++) { cin >> a[i]; } QuickSort(a,0, n-1); cout << "经过排序后的数组为：" << endl; for (int i = 0; i < n; i++) { cout<< a[i]<<" "; } }
