快速排序的C++实现
快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。
分治法在计算机科学中，是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础，如本次的快速排序,还有归并排序,傅里叶变换等等。
快速排序的基本思想是：
1．先从数列中取出一个数作为基准数。
2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
3．再对左右区间重复第二步，直到各区间只有一个数。
下面先来看实例吧。
//以一个数组作为示例，取区间第一个数为基准数//快速排序用C++实现如下：//快速排序using namespace std;void quickSort(int a[],int,int);int main(){int array[] = {23,56,21,77,35,3,7,34,7,43,76,29,79},k;int len = sizeof(array) / sizeof(int);cout << "The unsorted array is:" << endl;for (k = 0;k < len; k++)cout << array[k] << ",";cout << endl;quickSort(array,0,len-1);cout << "The sorted arrayare is:" << endl;for (k = 0; k < len; k++)cout << array[k] << ",";cout << endl;system("pause");return 0;}void quickSort(int s[], int l, int r){if (l< r){int i = l, j = r, x = s[l];while (i < j){while(i < j && s[j]>= x) // 从右向左找第一个小于x的数j--;if(i < j)s[i++] = s[j];while(i < j && s[i]< x) // 从左向右找第一个大于等于x的数i++;if(i < j)s[j--] = s[i];}s[i] = x;quickSort(s, l, i - 1); // 递归调用quickSort(s, i + 1, r);}}
运行结果:
最后,快排的时间复杂度
最坏情况下的时间复杂度: O(n2)
平均情况的时间复杂度: O(nlog2n)
最好的时间复杂度: O(nlog2n)
空间复杂度: O(log2n) - O(n)
稳定性:不稳定