快速排序--[算法导论]

对于包含n个数的输入数组来说，快速排序是一种最坏情况时间复杂度为O(n2)的排序算法。虽然最坏情况时间的复杂度很差，但是快速排序通常是实际排序应用中最好的选择，因为它的平均性能非常好：它的期望时间复杂度是O(nlgn)，而且O(nlgn)中隐含的常数因子非常小，另外，它还能够进行原址排序，甚至在虚存环境中也能很好的工作。

快速排序使用了分治的思想：

分解：将数组A[low..high]划分为两个子数组A[low..mid - 1]以及A[mid + 1..high]，使得A[low..mid - 1]子数组中的元素小于A[mid]，而在A[mid + 1..high]中的元素都大于A[mid]元素，返回mid位置；

解决：通过递归调用快速排序，对子数组继续进行排序；

合并：因为子数组是按照原址排序的，故不需进行合并：数组已经有序。

其中分解：

进行原址重排：

如对数组A[] = {2, 8, 7, 1, 3, 5, 6, 4}进行快速排序；

在Partition进行原址重排：

以最后一个元素为x = 4，浅灰色部分是<=x，深灰色部分则是>x；第一轮排序到此为止；

继续运行QuickSort，直到p >= r为止(即low >= high)；

代码：

#include 
  
   
#include 
   
     #include 
    
      using namespace std; void swap(int &m, int &n) //交换 { int temp = m; m = n; n = temp; } int Partition(int *A, int low, int high) { int i = low - 1; int pivot = A[high]; //最后一个元素作为基点 for(int j = low; j < high; j++) // { if(A[j] <= pivot) //判断 { i++; swap(A[i], A[j]); //交换 } } swap(A[i + 1], A[high]); //交换 return i + 1; //返回基准下标 } void QuickSort(int *A, int low, int high) { int pivotpos; //基准元素所对应的位置 if(low < high) { pivotpos = Partition(A, low, high); //对数据进行划分，pivotpos是基准元素下标 QuickSort(A, low, pivotpos - 1); //前半部数据 QuickSort(A, pivotpos + 1, high); //后半部数据 } } int main() { int A[] = {2, 8, 7, 1, 3, 5, 6, 4}; int length = sizeof(A) / sizeof(int) - 1; // QuickSort(A, 0, length); //进行排序 cout<<"排列："; for(int i = 0; i <= length; i++) //输出排列结果 cout<