快速排序，是一个较为高效的不稳定排序算法，其排序效率在同为O(N*logN)的几种排序算法当中也较为高效，使用率可谓名列前茅，尽管它是一种不稳定的排序算法（排序的过程中相等的值的位置可能有所变化），但仍然十分受欢迎。其核心思想是选中一个基点，通过一次排序操作将整个序列划分为两个子序列，左子序列的值都比基点要小，右子序列的值都比基点要大，按照该方法又对两个子序列进行快排操作，不断地重复上面的操作，最后达到全部的序列都排序好，使整个序列排序为有序数列。其算法思想的本质也是分治策略，对数据分布越乱的序列排序效率越高。
其实现原理如下： 1.寻找一个基点，作为后续对比的参照，一般选用第一个数据作为基点。 2.以该基点为参照数值，将比其小的数据挪到序列的左边，比其大的数据挪到序列的右边。 3.取上一次排序完成后的基点的下标为划分点，将划分开的左右两个子序列重复进行快排操作 4.最终全部子序列排序好后，得到的整个序列既是已经有序排列完成的。
下面附上实现代码：
#include <iostream> #include <vector> using namespace std; class Solution { public: //快排底层原理 int Partition(vector<int> &arr, int left, int right) { int boundkey = arr[left]; //取每轮的第一个数作为基数 //调整位置 以基数为参照，小的往左跑，大的往右跑 while(left < right) { while(left < right && arr[right] >= boundkey) { right--; } arr[left] = arr[right]; while(left < right && arr[left] <= boundkey) { left++; } arr[right] = arr[left]; } arr[left] = boundkey; return left; } //快排实现 void QuickS(vector<int> &arr, int start, int end) { int left = start; int right = end; int *temp = new int[(end - start + 1) * 2](); //构建存放下次需要进行快排的前后下标的临时空间 int top = 0; temp[top++] = end; //将末尾点下标存入临时空间第一个位置 temp[top++] = start; //将起始点下标存入临时空间第二个位置 //若k处于较中间位置，则先不断将左子序列排序取中再排序，直到左子序列排序完成，再进行右子序列不断快排 while (top != 0) { left = temp[top - 1]; top--; right = temp[top - 1]; top--; int k = Partition(arr, left, right); if (k + 1 < right)//右边区间有两个元素 { temp[top++] = right; temp[top++] = k + 1; } if (left < k - 1)//左边区间有两个元素 { temp[top++] = k - 1; temp[top++] = left; } } free(temp); } //快排的封装 void QuickSort(vector<int> &arr) { if(arr.empty() || arr.size() == 1) { return; } int len = arr.size(); QuickS(arr, 0, len - 1); } };以上便是普通的快速排序实现。但是否可以实现的更加高效呢？答案是肯定的，首先我们知道，快排针对数据量较大且比较乱的序列排序的效率才高，那么我们可以通过人为判断数组长度来更换其他排序方式，如果数据量小的话，换成插入排序的效率会更高一些，还有每次取的中值可以更换为上一次的左、中、右三个值当中的中间大的那个值，以达到减少排序的递归次数，提高效率。优化的方法代码如下：
#include <iostream> #include <vector> using namespace std; class Solution { public: //交换数组中的两个元素位置 void Swap(vector<int> &arr, int firstindex, int secondindex) { int temp = arr[firstindex]; arr[firstindex] = arr[secondindex]; arr[secondindex] = temp; } //函数处理完成后 中间大的数在left位置 void MoveMiddleMaxNum(vector<int> &arr, int left, int mid, int right) { if (arr[mid] > arr[right])//mid位置是后面较大的 right是较小的 { Swap(arr, mid, right); } if (arr[left] < arr[right]) { Swap(arr, left, right); } if (arr[left] > arr[mid]) { Swap(arr, left, mid); } } //判断当数组大小<20时 直接插入效率更高 void MyInsertSort(vector<int> &arr, int left, int right) { int temp = 0; int i = left + 1; int j = i - 1; for (i = left + 1; i <= right; i++) { temp = arr[i]; for (j = i - 1; j >= left && arr[j] > temp; j--) { arr[j + 1] = arr[j]; } arr[j + 1] = temp; } } //快排底层原理 int Partition(vector<int> &arr, int left, int right) { int boundkey = arr[left]; //取每轮的第一个数作为基数 //调整位置 以基数为参照，小的往左跑，大的往右跑 while(left < right) { while(left < right && arr[right] >= boundkey) { right--; } arr[left] = arr[right]; while(left < right && arr[left] <= boundkey) { left++; } arr[right] = arr[left]; } arr[left] = boundkey; return left; } //快排实现-优化 void QuickSS(vector<int> &arr, int start, int end) { if (start < end) { if (end - start < 20) { MyInsertSort(arr, start, end); } int mid = (end - start) / 2 + start; MoveMiddleMaxNum(arr, start, mid, end); int k = Partition(arr, start, end); //聚集优化 一趟快排之后 QuickSS(arr, start, k - 1); QuickSS(arr, k + 1, end); } } //快排的封装 void QuickSort(vector<int> &arr) { if(arr.empty() || arr.size() == 1) { return; } int len = arr.size(); QuickSS(arr, 0, len - 1); } };