快速排序

快速排序基本思想：

简介：Quicksort (sometimes called partition-exchange sort) is an efficient sorting algorithm. Developed by British computer scientist Tony Hoare in 1959[1] and published in 1961,[2] it is still a commonly used algorithm for sorting. When implemented well, it can be about two or three times faster than its main competitors, merge sort and heapsort -----from wiki 快速排序也是分治算法的一种，而且在现实中应用很广泛，很多语言的qsort就是快排的优化版本

图片来自维基百科[(htps://en.wikipedia.org/wiki/Quicksort#/media/File:Sorting_quicksort_anim.gif)]

1、数组划分

核心思想：

选取固定位置的主元x(如尾元素)维护两个部分的右端下标i，j比较A[j] 和 x的大小 if: A[j] <= x : swap(A[i+1], A[j]), i,j都向后移动 if: A[j] > x : j 向后移动 注：A[i+1] 是大数区最左边的一个数。

实现方法

选取固定位置主元𝒙（如尾元素）维护两个部分的右端点变量𝒊,𝒋考察数组元素𝑨 𝒋 ，只和主元比较 若𝑨 𝒋 ≤ 𝒙，则交换𝑨[𝒋]和𝑨[𝒊 + 𝟏]，𝒊,𝒋右移 若𝑨 𝒋 > 𝒙，则𝒋右移把主元放在中间作分界线

2、伪代码

3、算法实现

#include<iostream> using namespace std; int a[20]={0,1,2,3,4,5,6,7,8,9}; int Partition(int A[], int p, int r) // 数组划分，r是主元的位置，固定选取 { // p是起始位置，r是选取的主元的位置 int x = A[r]; // x即为主元 int i = p - 1; for (int j = p; j < r; j++) { if (A[j] <= x) { swap(A[j], A[i+1]); i++; // i右移 } // else { // 如果A[j] > x, 只需要j右移 // } } swap(A[i+1], A[r]);//交换大数区最左边(A[i+1])和主元 int q = i+1; return q; // 返回的是大数区左边界的值 } void QuickSort(int A[], int p, int r) // 快速排序主函数 { if (p < r){ int q = Partition(A, p, r); // q是主元的下标 QuickSort(A, p, q-1); // 对主元左边排序 QuickSort(A, q+1, r); // 对主元右边排序 } } int main() { QuickSort(a,0,9); for (int i = 0; i < 10; i++) { cout << a[i] << " " << endl; } return 0; }

4、时间复杂度分析

最好： 每次选取的主元都在中间，子问题规模变成原来的1/2 $T(n)=2T(\frac{n}{2})+n$ 时间复杂度是：$O(nlogn)$

最坏： 每次选取的主元都在最后，子问题规模每次减1: $T(n)=T(n-1)+T(0)+n$ 时间复杂度是：$O(n^2)$

随机化快速排序：

相较于上面的变化是：主元的选取不再是最后一个，而是随机选取

1、 伪代码

2、算法实现

#include<iostream> #include<cstdio> #include<cstdlib> using namespace std; int a[20]={0,1,2,3,4,5,6,7,8,9}; int Partition(int A[], int p, int r) // 数组划分，r是主元的位置，固定选取 { // p是起始位置，r是选取的主元的位置 int x = A[r]; // x即为主元 int i = p - 1; for (int j = p; j < r; j++) { if (A[j] <= x) { swap(A[j], A[i+1]); i++; // i右移 } // else { // 如果A[j] > x, 只需要j右移 // } } swap(A[i+1], A[r]);//交换大数区最左边(A[i+1])和主元 int q = i+1; return q; // 返回的是大数区左边界的值 } void QuickSort(int A[], int p, int r) // 快速排序主函数 { if (p < r){ int q = Partition(A, p, r); // q是主元的下标 QuickSort(A, p, q-1); // 对主元左边排序 QuickSort(A, q+1, r); // 对主元右边排序 } } // 随机化快速排序：随机选取主元 int Randomized_Partition(int A[], int p, int r) { int s = (rand() % (r-p+1)) + p; swap(A[s], A[r]); // 令A[s]作为主元 int q = Partition(A, p, r); return q; } // void Randomized_Qsort(int A[], int p, int r) { if (p < r) { int q = Randomized_Partition(A, p, r); Randomized_Qsort(A, p, q-1); Randomized_Qsort(A, q, r); } } int main() { Randomized_Qsort(a,0,9); for (int i = 0; i < 10; i++) { cout << a[i] << " " << endl; } return 0; }

3、时间复杂度分析