数据结构排序之快排
1 快排思路讲解
1. hoare版本
选一个基准：从待排序的数组中选择一个元素作为“基准”。通常选择第一个元素、最后一个元素、中间元素，或者通过随机选则。
分区:
使用基准元素将数组分成两个部分：小于等于基准的元素和大于等于基准的元素。
可以使用两指针方法来完成分区过程。
单次：
- end找小
- begin找大
- 交换begin和end上的值
- 当我们的begin大于等于end 结束寻找
- 跳出循环，将我们的begin和keyi 上的值进行交换。
为什么和我们的begin上的值进行交换是可以的：
因为我们的显示进行找小于我们的keyi的值的操作，在去找大的，那我们就能保证我们的begin上的值在结束的时候一定是吧我们的keyi上的值小的，
递归排序: 对基准元素左边和右边的子数组递归调用快速排序函数。
过程图：
代码：
int key=left;
int temp = a[key];//比较的值
int begin = left;
int end = right;
while (begin < end)
{while (begin < end && temp <= a[end])//先走右边{end--;}while (begin < end && temp >= a[begin]){begin++;}//交换两个数值使左边的数小于temp，右边的数大于tempSwag(&a[begin], &a[end]);
}
//交换我们的key上的值和我们相遇的位置的值,这样就排好一个值了
Swag(&a[key], &a[begin]);
key = begin;这是我们单趟的结果，对于我们的整个快排，外层的代码就是整体逻辑了，递归分治法解决，
递归分治两部曲：1.子问题：左右两边分别有序；2.返回条件： 当区间里面只有一个数或者我们的left>right,即我们的left>=right；
对于我们的快排，每次我们都是将我们的一个数排序好，左边是比它小的数，右边是比它大的数。然后我们在讲它的左右两边进行分别的排序，如果我们的左右两边是有序的，那么这个数组就是有序的。
快排优化三数取中：
我对于我们的快排，最好的情况是我们的进行分割区间的时候两边均匀一些，最好是每边一半的情况，如果每次选key最接近 二分查找 效率最高 时间复杂度 O(N*logN)，如果是有序的情况，每次的key都固定在最左边的情况，那么 时间复杂度为O(N^2)那么当我们的数据很多的时候就会有栈溢出的风险。而且运行效率也会下降很多。所有这个时候我们的就要采取我们的三数取中的方法，降低了我们的所取的key位置上的数出现极端的情况的概率，
三数：最左边的数和最右边的数，和中间中间里的数。对这三个数进行比较，取第二大的数，也就是既不是最小的数也不是最大的数，
在将这个数与我们的left位置上的数进行交换，我们的key还是left位置上的数。
代码：
int FindMid(int* a, int left, int right)
{int mid = (left + right) / 2;if (a[left] > a[right]&&a[left]>a[mid]){if (a[right] > a[mid]){return mid;}else {return right;}}else if(a[right]>a[left]&&a[right]>a[mid]) {if (a[left] < a[mid]){return left;}else {return mid;}}else if (a[mid] > a[right] && a[mid] > a[left]){if (a[right] > a[left]){return left;}else {right;}}
}进一步优化
当我们的区间里面的数据很少的时候，其实就可以不继续用我们快排去进行排序了，因为我们剩下的数据量不是很大，所以我们采用其他的效率不是很快的排序对我们的效率不会有很大影响
我们这里可以采用我们的插入排序来进行排序，不用堆排序是因为建堆很麻烦。
if (right - left <= 10)
{//采用插入排序for (int i = 0; i < 9; i++){int end = i;int temp = a[end + 1];while (end >= 0){if (a[end] > temp){a[end + 1] = a[end];}else {break;}end--;}a[end + 1] = temp;}}快排优化之后的完整版的代码：
void Swag(int* a, int* b)
{int tem = *a;*a = *b;*b = tem;}
int FindMid(int* a, int left, int right)
{int mid = (left + right) / 2;if (a[left] > a[right]&&a[left]>a[mid]){if (a[right] > a[mid]){return mid;}else {return right;}}else if(a[right]>a[left]&&a[right]>a[mid]) {if (a[left] < a[mid]){return left;}else {return mid;}}else if (a[mid] > a[right] && a[mid] > a[left]){if (a[right] > a[left]){return left;}else {right;}}
}
void QuickSort(int* a, int left, int right)
{if (left >= right){return;}
if (right - left <= 10)
{//采用插入排序for (int i = 0; i < 9; i++){int end = i;int temp = a[end + 1];while (end >= 0){if (a[end] > temp){a[end + 1] = a[end];}else {break;}end--;}a[end + 1] = temp;}}else{//优化我们的快排//三个数中间的那个数，不要最大和最小的数做keyint key = FindMid(a,left,right);Swag(&a[left], &a[key]);key = left;int temp = a[key];//比较的值int begin = left;int end = right;while (begin < end){while (begin < end && temp <= a[end])//先走右边{end--;}while (begin < end && temp >= a[begin]){begin++;}//交换两个数值使左边的数小于temp，右边的数大于tempSwag(&a[begin], &a[end]);}//交换我们的key上的值和我们相遇的位置的值,这样就排好一个值了Swag(&a[key], &a[begin]);key = begin;QuickSort(a, left, key - 1);//排左边的QuickSort(a, key + 1, right);//排右边的}
}2. 挖坑法
- 选择基准值：首先从数组中选择一个基准值，这个基准值可以是数组的第一个元素、最后一个元素或者任意一个元素。一般采取第一个。
- 挖坑：将基准值从数组中移除，形成一个“坑”，这个坑的位置就是基准值原本的位置。
- 填坑：从数组的两端开始，向中间遍历，
- 先从右边开始，找到比基准值小的元素就将其填入刚才挖出的“坑”中。
- 同时，从左边也开始向中间遍历，找到比基准值大的元素也填入“坑”中。当两个遍历的指针相遇时，基准值就被正确地放置在了最终的位置上。
- 递归处理：然后将基准值左侧和右侧的子数组分别进行同样的操作，即对这两个子数组进行快速排序，直到每个子数组只有一个元素或者为空。
完整代码;
// 快速排序挖坑法
int PartSort2(int* a, int begin, int end)
{int left = begin, right = end;int key = a[begin];int hole = begin;while (left < right){//right找小while (left < right && a[right] >= key){right--;}//把a[right]放到a[hole] right 位置就是新的坑位a[hole] = a[right];hole = right;//left找大while (left < right && a[left] <= key){left++;}//把a[left]放到a[hole] left 位置就是新的坑位a[hole] = a[left];hole = left;}a[hole] = key;return hole;
}
void QuickSort(int* a, int begin, int end)
{if (begin >= end){return;}int keyi = PartSort2(a, begin, end);//整个数组被分为[begin,keyi-1] keyi [keyi+1,end]QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end);
}3 前后指针
我们的前后指针的主体思想还是运用我们的hoare的主体思想。
三个主要步骤
cur 找比key小的，prev 找比 key 大的
- cur < key：pre++，swap(cur, pre)，cur++
- cur >= key ：cur++
- cur 越界后，pre 和 key 交换
代码：
//前后指针
void QuickSort(int* a, int left, int right)
{if (left >= right){return;}// 三数取中int midi = FindMid(a, left, right);Swap(&a[left], &a[midi]);int keyi = left;int prev = left;int cur = prev + 1;while (cur <= right){if (a[cur] < a[keyi] && ++prev != cur)Swap(&a[prev], &a[cur]);cur++;}//交换我们的key上的值和我们相遇的位置的值,这样就排好一个值了Swap(&a[prev], &a[keyi]);keyi = left;QuickSort(a, left, keyi - 1);//排左边的QuickSort(a, keyi + 1, right);//排右边的}
4快速排序的特性总结：
1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(logN)
4. 稳定性：不稳定
2改进快排之三路划分
决定快排性能的关键点是每次单趟排序后，key对数组的分割，如果每次选key基本⼆分居中，那么快 排的递归树就是颗均匀的满⼆叉树，性能最佳。但是实践中虽然不可能每次都是⼆分居中，但是性能 也还是可控的。但是如果出现每次选到最⼩值/最⼤值，划分为0个和N-1的⼦问题时，时间复杂度为 O(N^2)，数组序列有序时就会出现这样的问题，我们前⾯已经⽤三数取中或者随机选key解决了这个问 题，也就是说我们解决了绝⼤多数的问题，但是现在还是有⼀些场景没解决(数组中有⼤量重复数据 时)，类似⼀下代码：
数组中有多个跟key相等的值 int a[] = { 6,1,7,6,6,6,4,9 }; int a[] = { 3,2,3,3,3,3,2,3 };
数组中全是相同的值 int a[] = { 2,2,2,2,2,2,2,2 };
如果重复的数据非常之多，这个时候如果我们再去用原来的快排的话，效率就会很低。这个时候我们就得采用我们的三路划分的方法来改进我们的快排。
思路：
- key默认取left位置的值。
- left指向区间最左边，right指向区间最后边，cur指向left+1位置。
- cur遇到⽐key⼩的值后跟left位置交换，换到左边，left++，cur++。
- cur遇到⽐key⼤的值后跟right位置交换，换到右边，right--。
- cur遇到跟key相等的值后，cur++。
- 直到cur>right结束。
代码：
//交换函数
void Swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = tmp;
}
void QuickSort(int* a, int left, int right)
{if (left >= right)return;int begin = left;int end = right;// 随机选keyint randi = left + (rand() % (right-left));Swap(&a[left], &a[randi]);
// 三路划分
// left和right指向就是跟key相等的区间// [begin, left-1] [left, right] right+1, end]int key = a[left];int cur = left+1;while(cur <= right){// 1、cur遇到⽐key⼩，⼩的换到左边，同时把key换到中间位置// 2、cur遇到⽐key⼤，⼤的换到右边if(a[cur] < key){Swap(&a[cur], &a[left]);++left;++cur;}else if(a[cur] > key){Swap(&a[cur], &a[right]);--right;}else{++cur;}}// [begin, left-1] [left, right] right+1, end]QuickSort(a, begin, left - 1);QuickSort(a, right+1, end);
}3 快排之自省排序
introsort是introspectivesort采⽤了缩写，他的名字其实表达了他的实现思路，他的思路就是进⾏⾃ 我侦测和反省，快排递归深度太深（sgistl中使⽤的是深度为2倍排序元素数量的对数值）那就说明在 这种数据序列下，选key出现了问题，性能在快速退化，那么就不要再进⾏快排分割递归了，改换为堆 排序进⾏排序。
代码：
void Swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = tmp;
}
void AdjustDown(int* a, int n, int parent)
{int child = parent * 2 + 1;while (child < n){// 选出左右孩⼦中⼤的那⼀个if (child + 1 < n && a[child + 1] > a[child]){++child;}if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}
void HeapSort(int* a, int n)
{// 建堆 -- 向下调整建堆 -- O(N)for (int i = (n - 1 - 1) / 2; i >= 0; --i){AdjustDown(a, n, i);}// ⾃⼰先实现 -- O(N*logN)int end = n - 1;while (end > 0){Swap(&a[end], &a[0]);AdjustDown(a, end, 0);--end;}
}
void InsertSort(int* a, int n)
{for (int i = 1; i < n; i++){int end = i-1;int tmp = a[i];// 将tmp插⼊到[0,end]区间中，保持有序while (end >= 0){if (tmp < a[end]){a[end + 1] = a[end];--end;}else{break;}}a[end + 1] = tmp;}
}
void IntroSort(int* a, int left, int right, int depth, int defaultDepth)
{if (left >= right)return;// 数组⻓度⼩于16的⼩数组，换为插⼊排序，简单递归次数if(right - left + 1 < 16){InsertSort(a+left, right-left+1);return; }// 当深度超过2*logN时改⽤堆排序if(depth > defaultDepth){HeapSort(a+left, right-left+1);return;
}depth++;int begin = left;int end = right;// 随机选keyint randi = left + (rand() % (right-left));Swap(&a[left], &a[randi]);int prev = left;int cur = prev + 1;int keyi = left;while (cur <= right){if (a[cur] < a[keyi] && ++prev != cur){Swap(&a[prev], &a[cur]);}++cur;}
Swap(&a[prev], &a[keyi]);keyi = prev;// [begin, keyi-1] keyi [keyi+1, end]IntroSort(a, begin, keyi - 1, depth, defaultDepth);IntroSort(a, keyi+1, end, depth, defaultDepth);
}
void QuickSort(int* a, int left, int right)
{int depth = 0;int logn = 0;int N = right-left+1;for(int i = 1; i < N; i *= 2){logn++;}// introspective sort -- ⾃省排序IntroSort(a, left, right, depth, logn*2);
}