网站导航
> 文章列表 > 数据结构_第十三关（2）：快速排序

数据结构_第十三关（2）：快速排序

网友: 文章列表 2024-03-21 23:41:54

数据结构_第十三关（2）：快速排序

目录

1.快速排序

原理：

 代码如下（递归实现）：

性能比较

快速排序的特性总结

2.快速排序的优化

1）三数取中优化：

2）小区间优化：

3. 挖坑法（快排的另一种思路）：

4. 快慢指针法（快排的第三种思路）：

5.快速排序（非递归版代码）

6.源代码（VS2022下编写）

1.快速排序

基本思想：

任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止

原理：

如上述图所示，此时就完成了一次单趟排序

单趟排序的作用：

  1. 使得key到了准确的位置
  2. 使得key左边的数都小于key，key右边的数都大于key

剩下的问题：让左区间有序、有区间有序，整体就ok了

然后再对其递归排序数组key的左边和右边，最终就可排好序

注意的点：

  • 左边和右边都可以做key，但是
  • 左边做key，右边要先走
  • 右边做key，左边要先走
  • 这是为了保证相遇的位置，一定比key要小（左边做key的情况下）

 代码如下（递归实现）：

这个代码写起来会有很多坑，如下，单趟排序：

正确代码： 

void QuickSort(int* a, int begin, int end)
{if (begin >= end){return;}int left = begin, right = end;int keyi = left;while (left < right){// 右边先走，找小while (left < right && a[right] >= a[keyi]){--right;}// 左边再走，找大while (left < right && a[left] <= a[keyi]){++left;}Swap(&a[left], &a[right]);}Swap(&a[left], &a[keyi]);keyi = left;// [begin, keyi-1]  keyi [keyi+1, end]QuickSort(a, begin, keyi - 1);QuickSort(a, keyi+1, end);
}

性能比较

和上之前的简单排序算法的效率比较如下：

 1万随机数据量下测得

  10万随机数据量下测得

 

去掉选择排序和冒泡排序， 100万随机数据量下测得

去掉直接插入排序 ， 1000万随机数据量下测得

可以看出在数据量达到1000万级别时，快速排序似乎不占优势

因为key的取值，我们可以给快排进行优化，如第二部分。

快速排序的特性总结

  1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
  2. 时间复杂度：O(N*logN)
  3. 空间复杂度：O(logN)
  4. 稳定性：不稳定

在快速排序的时间复杂度计算中，最坏情况为：

没次key都是最大或者最小的，

实际情况：有序

此时，时间复杂度为O（N^2）

快排的中心思想就是：

  • 不管你怎么选key，在第一趟排序之后，key的位置是正确的，
  • 并且，key左边的数小于key，key右边的数大于key

因为key的选择可以不同，所以快排就有了一下的改进：

2.快速排序的优化

1）三数取中优化：

 （主要对时间进行优化）

原理：

选择最左边，最中间，最右边的三个数作比较，选出最小的数作为key

代码如下：

//快排改进：key选值的三数取中
int GetMidIndex(int* a, int begin, int end)
{int mid = (begin + end) / 2;if (a[begin] < a[mid]){if (a[mid] < a[end]){return mid;}else if (a[begin] > a[end]){return begin;}else{return end;}}else // a[begin] > a[mid]{if (a[mid] > a[end]){return mid;}else if (a[begin] < a[end]){return begin;}else{return end;}}
}
void MidQuickSort(int* a, int begin, int end)
{if (begin >= end){return;}int mid = GetMidIndex(a, begin, end);Swap(&a[begin], &a[mid]);int left = begin, right = end;int key = left;while (left < right){// 右边先走，找小while (left < right && a[right] >= a[key]){--right;}// 左边再走，找大while (left < right && a[left] <= a[key]){++left;}Swap(&a[left], &a[right]);}Swap(&a[left], &a[key]);key = left;// [begin, keyi-1]  key [keyi+1, end]QuickSort(a, begin, key - 1);QuickSort(a, key + 1, end);
}

加入三数取中之后，快排的时间复杂度就可以认为是：O（N*logN）；

性能比较：

之前1000万随机数据量下测得的数据：

加入三数取中后，1000万随机数据量下测得的数据：

 可以看到，此时快排的效率有了明显的提高

2）小区间优化：

（主要对空间进行优化）

c++官方库，QST库都的快排都在用小区间优化

原理：

到最后10个数的时候，用递归的话，可以看到还需要4层深度的递归

 

对最后一小段区域的排序，我们用直接插入排序就行

 代码如下：

//小区间优化（优化空间）
void SpaceQuickSort(int* a, int begin, int end)
{if (begin >= end){return;}if ((end - begin + 1) < 10){// 小区间用直接插入替代，减少递归调用次数InsertSort(a + begin, end - begin + 1);}else{int mid = GetMidIndex(a, begin, end);Swap(&a[begin], &a[mid]);int left = begin, right = end;int keyi = left;while (left < right){// 右边先走，找小while (left < right && a[right] >= a[keyi]){--right;}// 左边再走，找大while (left < right && a[left] <= a[keyi]){++left;}Swap(&a[left], &a[right]);}Swap(&a[left], &a[keyi]);keyi = left;// [begin, keyi-1]  keyi [keyi+1, end]QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end);}
}

因为空间对效率的提示并不大，这里就不进行测试了，感兴趣的可以自己测一测

3. 挖坑法（快排的另一种思路）：

原理：

代码如下（递归实现）：

// 快速排序，挖坑法
void HoleQuickSort(int* a, int begin, int end)
{if (begin >= end){return;}//小区间优化if ((end - begin + 1) < 10){// 小区间用直接插入替代，减少递归调用次数InsertSort(a + begin, end - begin + 1);}else{//三数选中间优化int mid = GetMidIndex(a, begin, end);Swap(&a[begin], &a[mid]);int left = begin, right = end;int key = a[left];int hole = left;while (left < right){// 右边找小，填到左边坑里面while (left < right && a[right] >= key){--right;}a[hole] = a[right];hole = right;// 左边找大，填到右边坑里面while (left < right && a[left] <= key){++left;}a[hole] = a[left];hole = left;}a[hole] = key;// [begin, key-1]  key [key+1, end]QuickSort(a, begin, key - 1);QuickSort(a, key + 1, end);}
}

4. 快慢指针法（快排的第三种思路）：

 原理：

代码如下（递归实现）：

//快慢指针法
void PointQuickSort(int* a, int begin, int end)
{if (begin > end){return;}//小区间优化if ((end - begin + 1) < 10){// 小区间用直接插入替代，减少递归调用次数InsertSort(a + begin, end - begin + 1);}else{//三数选中间优化int mid = GetMidIndex(a, begin, end);Swap(&a[begin], &a[mid]);int prev = begin, cur = begin + 1;int key = prev;while (cur <= end){while (cur <= end){if (a[cur] >= a[key] && ++prev != cur)//++prev和cur的下标如果相等，就不要进行交换{Swap(&a[++prev], &a[cur]); //一定是先++prev，在用prev }cur++;}}Swap(&a[prev], &a[key]);PointQuickSort(a, begin, key);PointQuickSort(a, key + 1, end);}
}

5.快速排序（非递归版代码）

非递归实现的方式有两种，一种是用栈实现，一种是用队列实现

用栈实现又叫做深度优先、用队列实现又叫做广度优先

原理如下：

基于栈的深度优先：

 

可以看出来，利用栈进行快排，是先左边的区间，后右边的区间，是往深的走，所以叫做深度优先

基于队列的广度优先：

基于队列的快排，是一层层的走的，和之前二叉树的层次遍历原理是相同的，因为是一层一层的走，所以叫做广度优先

代码如下（这里采用基于栈的深度优先）：

//快速排序（非递归）
//利用堆实现的叫做深度优先
void QuickSortNonR(int* a, int begin, int end)
{ST st;StackInit(&st);StackPush(&st, begin);StackPush(&st, end);while (!StackEmpty(&st)){int right = StackTop(&st);StackPop(&st);int left = StackTop(&st);StackPop(&st);//进行一次快排int prev = left, cur = left + 1;int key = left;while (cur <= right){//++prev和cur的下标如果相等，就可以不用进行交换if (a[cur] < a[key] && ++prev != cur){Swap(&a[prev], &a[cur]); }cur++;}Swap(&a[prev], &a[key]);key = prev;// [left, key-1] keyi [key+1, right]if (key + 1 < right){StackPush(&st, key + 1);StackPush(&st, right);}if (left < key - 1){StackPush(&st, left);StackPush(&st, key - 1);}}StackDestroy(&st);
}

 

6.源代码（VS2022下编写）

#include "Stack.h" //引入了之前写的栈结构#include<stdio.h>
#include<stdlib.h>
#include<time.h>//声明：//快速排序
void QuickSort(int* a, int begin, int end);
//三数取中
void MidQuickSort(int* a, int begin, int end);
//小空间优化
void SpaceQuickSort(int* a, int begin, int end);
//挖坑法
void HoleQuickSort(int* a, int begin, int end);
//快慢指针法
void PointQuickSort(int* a, int begin, int end);
//非递归法
void QuickSortNonR(int* a, int begin, int end);//实现//快速排序
void QuickSort(int* a, int begin, int end)
{//end -= 1;if (begin >= end){return;}int left = begin, right = end;int key = left;while (left < right){// 右边先走，找小while (left < right && a[right] >= a[key]){--right;}// 左边再走，找大while (left < right && a[left] <= a[key]){++left;}Swap(&a[left], &a[right]);}Swap(&a[left], &a[key]);key = left;// [begin, keyi-1]  key [keyi+1, end]QuickSort(a, begin, key - 1);QuickSort(a, key + 1, end);
}
//快排改进：key选值的三数取中（优化时间）
int GetMidIndex(int* a, int begin, int end)
{int mid = (begin + end) / 2;if (a[begin] < a[mid]){if (a[mid] < a[end]){return mid;}else if (a[begin] > a[end]){return begin;}else{return end;}}else // a[begin] > a[mid]{if (a[mid] > a[end]){return mid;}else if (a[begin] < a[end]){return begin;}else{return end;}}
}
void MidQuickSort(int* a, int begin, int end)
{if (begin >= end){return;}int mid = GetMidIndex(a, begin, end);Swap(&a[begin], &a[mid]);int left = begin, right = end;int key = left;while (left < right){// 右边先走，找小while (left < right && a[right] >= a[key]){--right;}// 左边再走，找大while (left < right && a[left] <= a[key]){++left;}Swap(&a[left], &a[right]);}Swap(&a[left], &a[key]);key = left;// [begin, key-1]  key [key+1, end]QuickSort(a, begin, key - 1);QuickSort(a, key + 1, end);
}
//小区间优化（优化空间）
void SpaceQuickSort(int* a, int begin, int end)
{if (begin >= end){return;}if ((end - begin + 1) < 10){// 小区间用直接插入替代，减少递归调用次数InsertSort(a + begin, end - begin + 1);}else{int mid = GetMidIndex(a, begin, end);Swap(&a[begin], &a[mid]);int left = begin, right = end;int keyi = left;while (left < right){// 右边先走，找小while (left < right && a[right] >= a[keyi]){--right;}// 左边再走，找大while (left < right && a[left] <= a[keyi]){++left;}Swap(&a[left], &a[right]);}Swap(&a[left], &a[keyi]);keyi = left;// [begin, keyi-1]  keyi [keyi+1, end]QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end);}
}
// 快速排序，挖坑法
void HoleQuickSort(int* a, int begin, int end)
{if (begin >= end){return;}//小区间优化if ((end - begin + 1) < 10){// 小区间用直接插入替代，减少递归调用次数InsertSort(a + begin, end - begin + 1);}else{//三数选中间优化int mid = GetMidIndex(a, begin, end);Swap(&a[begin], &a[mid]);int left = begin, right = end;int key = a[left];int hole = left;while (left < right){// 右边找小，填到左边坑里面while (left < right && a[right] >= key){--right;}a[hole] = a[right];hole = right;// 左边找大，填到右边坑里面while (left < right && a[left] <= key){++left;}a[hole] = a[left];hole = left;}a[hole] = key;// [begin, key-1]  key [key+1, end]QuickSort(a, begin, key - 1);QuickSort(a, key + 1, end);}
}
//快慢指针法
void PointQuickSort(int* a, int begin, int end)
{if (begin > end){return;}//小区间优化if ((end - begin + 1) < 10){// 小区间用直接插入替代，减少递归调用次数InsertSort(a + begin, end - begin + 1);}else{//三数选中间优化int mid = GetMidIndex(a, begin, end);Swap(&a[begin], &a[mid]);int prev = begin, cur = begin + 1;int key = prev;while (cur <= end){if (a[cur] < a[key] && ++prev != cur)//++prev和cur的下标如果相等，就不要进行交换{Swap(&a[prev], &a[cur]); //一定是先++prev，在用prev }cur++;}Swap(&a[prev], &a[key]);PointQuickSort(a, begin, key);PointQuickSort(a, key + 1, end);}
}//快速排序（非递归）
//利用堆实现的叫做深度优先
void QuickSortNonR(int* a, int begin, int end)
{ST st;StackInit(&st);StackPush(&st, begin);StackPush(&st, end);while (!StackEmpty(&st)){int right = StackTop(&st);StackPop(&st);int left = StackTop(&st);StackPop(&st);//进行一次快排int prev = left, cur = left + 1;int key = left;while (cur <= right){if (a[cur] < a[key] && ++prev != cur)//++prev和cur的下标如果相等，就不要进行交换{Swap(&a[prev], &a[cur]); }cur++;}Swap(&a[prev], &a[key]);key = prev;// [left, key-1] keyi [key+1, right]if (key + 1 < right){StackPush(&st, key + 1);StackPush(&st, right);}if (left < key - 1){StackPush(&st, left);StackPush(&st, key - 1);}}StackDestroy(&st);
}//主函数测试void printArray(int* a, int n)
{for (int i = 0;i < n;i++){printf("%d ", a[i]);}printf("\\n");
}void TestInsertSort()
{int a[] = { 6,1,2,7,9,3,4,5,10,8 };//InsertSort(a, sizeof(a) / sizeof(int));//printArray(a, sizeof(a) / sizeof(int));//shellSort(a, sizeof(a) / sizeof(int));//printArray(a, sizeof(a) / sizeof(int));//HeapSort(a, sizeof(a) / sizeof(int));//printArray(a, sizeof(a) / sizeof(int));//BubbleSort(a, sizeof(a) / sizeof(int));//printArray(a, sizeof(a) / sizeof(int));//快排传的是：数组地址、开始下标、数组结尾下标HoleQuickSort(a, 0, sizeof(a) / sizeof(int) - 1);printArray(a, sizeof(a) / sizeof(int));QuickSortNonR(a, 0, sizeof(a) / sizeof(int)-1);printArray(a, sizeof(a) / sizeof(int));
}void functionText()
{srand(time(0));const int N = 1000000;int* a1 = (int*)malloc(sizeof(int) * N);int* a2 = (int*)malloc(sizeof(int) * N);int* a3 = (int*)malloc(sizeof(int) * N);int* a4 = (int*)malloc(sizeof(int) * N);int* a5 = (int*)malloc(sizeof(int) * N);int* a6 = (int*)malloc(sizeof(int) * N);int* a7 = (int*)malloc(sizeof(int) * N);for (int i = 0; i < N; ++i){a1[i] = rand() + i;a2[i] = a1[i];a3[i] = a1[i];a4[i] = a1[i];a5[i] = a1[i];a6[i] = a1[i];a7[i] = a7[i];}//int begin1 = clock();//InsertSort(a1, N);//int end1 = clock();int begin2 = clock();ShellSort(a2, N);int end2 = clock();//int begin3 = clock();//SelectSort(a3, N);//int end3 = clock();int begin4 = clock();HeapSort(a4, N);int end4 = clock();/*int begin7 = clock();BubbleSort(a7, N);int end7 = clock();*/int begin5 = clock();MidQuickSort(a5, 0, N - 1);int end5 = clock();// //int begin6 = clock();//MergeSort(a6, N);//int end6 = clock();printf("数据量为%d，以下时间单位为毫秒（ms）\\n",N);//printf("InsertSort:	%d\\n", end1 - begin1);printf("ShellSort:	%d\\n", end2 - begin2);//printf("SelectSort:	%d\\n", end3 - begin3);printf("HeapSort:	%d\\n", end4 - begin4);//printf("BubbleSort:	%d\\n", end7 - begin7);printf("QuickSort:	%d\\n",end5 - begin5);//printf("MergeSort:%d\\n", end6 - begin6);free(a1);free(a2);free(a3);free(a4);free(a5);free(a6);free(a7);
}int main()
{//TestInsertSort();//性能测试：functionText();return 0;
}
网络标签：

相关问题