前言：快排最早由图灵奖获得者Tony Hoare设计出来的，他在形式化理论以及ALGOL60编程语言中，都有卓越的发明中都有卓越的贡献。是上世纪最伟大的计算机科学家之一；快排是他的一个小发明，被列为20世纪十大算法（有关十大算法参见链接博客https://www.sohu.com/a/228987774_488171）之一。另外：快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高，因此经常被采用，再加上快速排序思想----分治法也确实实用，因此很多软件公司的笔试面试，包括像腾讯，微软等知名IT公司都喜欢考这个，还有大大小的程序方面的考试如软考，考研中也常常出现快速排序的身影。
希尔排序相当于插入排序的升级，他们同属于插入排序类；
堆排序相当于选择排序的升级，他们同属于选择排序类；
快速排序属于最慢的冒泡排序的升级，同属于交换排序类；
快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。
基本思想是：
1．先从数列中取出一个数作为基准数。2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。3．再对左右区间重复第二步，直到各区间只有一个数
第一趟排序之后：比基准数小的都在基准数左边，比基准数大的都在基准数右边：
之后的做法是
即递归：
递归执行的条件：i<j (保证i在j的左边)
#include<iostream> #include<vector> using namespace std; void print(vector<int> a) { for (int i = 0; i < a.size(); i++) { cout << a[i] << " "; } cout << endl; } void quick_sort(vector<int> &arr,int start,int end) { //递归终止条件 print(arr); if (start >= end) return; int i = start; int j = end; //基准数 int temp = arr[start]; if (i<j) { while (i<j) { //从右往左找比基准数小的 while (i<j && arr[j]>=temp) { j--; } //填坑 if (i < j) { arr[i] = arr[j]; i++;//填完数字 i右移 } //从左向右找比基准数大的 while (i<j && arr[i]<temp) { i++; } //填坑 if (i < j) { arr[j] = arr[i]; j--; } } //循环退出 i=j 基础数位置放在i = j的位置 arr[i] = temp;//保证左边比基准数小，右边比基准数大 //第一个基准数放在该放的位置 //递归 quick_sort(arr, start, i - 1); quick_sort(arr, i + 1, end); } } int main() { vector<int> arr{0,9,1,5,8,3,7,4,6,2}; cout << "原数组:" << endl; print(arr); //快速排序 quick_sort(arr, 0, arr.size() - 1); cout << "排序后：" << endl; print(arr); system("pause"); }时间复杂度分析：时间性能取决于递归的深度：最优的情况是O（nlogn）;最坏的情况是：O（n方）
//version.2 #include<iostream> #include<vector> using namespace std; void print(vector<int> a) { for (int i = 0; i < a.size(); i++) { cout << a[i] << " "; } cout << endl; } int number(vector<int> &arr, int L, int R) { int i = L; int j = R; //基准数 int temp = arr[i]; while (i < j) { //从右往左找比基准数小的 while (i < j && arr[j] >= temp) { j--; } arr[i] = arr[j]; //从左往右找比基准数大的 while (i < j && arr[i] < temp) { i++; } arr[j] = arr[i]; } arr[i] = temp; return i; } void quick_sort(vector<int> &arr, int L, int R) { if (L >= R)return; int i = number(arr, L, R); quick_sort(arr, L, i - 1); quick_sort(arr, i + 1, R); } void main(){ vector<int> arr = { 0,9,1,5,8,3,7,4,6,2 }; print(arr); int l = 0; int r = arr.size()-1; quick_sort(arr, l, r); print(arr); system("pause"); }
快排非递归：
#include<iostream> #include<vector> #include<stack> using namespace std; int base_number(vector<int>&arr, int l, int r) { int i = l, j = r; int temp = arr[l]; while (i < j) { while (i < j &&arr[j] >= temp) { j--; } arr[i] = arr[j]; while (i < j &&arr[i] <= temp) { i++; } arr[j] = arr[i]; } arr[i] = temp; return i; } void quicksort(vector<int>& arr, int l, int r) { stack<int> st; int k; if (l < r) { st.push(l); st.push(r); while (!st.empty()) { int j = st.top(); st.pop(); int i = st.top(); st.pop(); k = base_number(arr, i, j);//基准数 if (i < k - 1) { st.push(i); st.push(k - 1); } if (j > k + 1) { st.push(k + 1); st.push(j); } } } } int main(){ vector<int> arr = { 1,26,5,65,26,98,36,36,871,2,3,56 }; quicksort(arr, 0, arr.size() - 1); for (int i = 0; i < arr.size() - 1; i++) { cout << arr[i] << " "; } system("pause"); return 0; }
