数据结构算法学习总结-慕课网(九)快速排序(从小到大)

xiaoxiao2021-02-28  6

数据结构算法学习总结-慕课网(九)快速排序(从小到大)

1.回顾

上一节降到了自底向上的归并排序

这一节将讲一个性能很高的排序,快速排序

2.分析

快速排序的思想是首先取数组的第一个元素,记为v,找到一个合适的位置p,满足p位置之前的元素都小于v,p之后的元素都大于或者等于v,然后对小于v和大于或者等于v的元素再分别递归排序

对于数组{4,5,1,3},4记为v,比较5和4,5比4大,继续下一个元素1;1和4比较,发现1比4小,那么交换5和1的位置,现在数组变为{4,1,5,3};比较3和4,发现3比4小,交换5和3的位置,现在数组变为{4,1,3,5},最后交换3和4的位置,数组变为{3,1,4,5},满足4之前的元素小于4,4之后的元素大于或者等于4,然后再对3,1排序即可

3.实战

QuickSort.h

#ifndef QUICKSORT_H_ #define QUICKSORT_H_ #include <iostream> using namespace std; /** * 对[l...r]部分进行partition操作 * 返回p,使得arr[l...p-1]<arr[p],arr[p+1,r]>=arr[p] */ template<typename T> int __partition(T arr[],int l,int r){ T v = arr[l]; //arr[l+1...j] < v ,arr[j+1...i] >= v int j = l; for(int i = l+1;i<=r;i++){ if(arr[i] < v){ swap(arr[j+1],arr[i]); j++; } } swap(arr[l],arr[j]); return j; } /** *对arr[l...r]部分进行快速排序 */ template<typename T> void __quickSort(T arr[],int l,int r){ if(l >= r) return; int p = __partition(arr,l,r); __quickSort(arr,l,p-1); __quickSort(arr,p+1,r); } template<typename T> void quickSort(T arr[],int n){ __quickSort(arr,0,n-1); } #endif /* QUICKSORT_H_ */

4.思考

对于一个近乎有序或者有很多重复键值的数组,这样的快速排序实际上效率很低,虽然理论上时间复杂度为nlogn级别的,但是此时的时间复杂度可能退化为最坏的n^2级别

5.优化

对于近乎有序的数组

#ifndef QUICKSORT_H_ #define QUICKSORT_H_ #include <iostream> #include "InsertSort.h" using namespace std; /** * 对[l...r]部分进行partition操作 * 返回p,使得arr[l...p-1]<arr[p],arr[p+1,r]>=arr[p] */ template<typename T> int __partition(T arr[],int l,int r){ swap(arr[l],arr[rand()%(r - l +1)+l]); T v = arr[l]; //arr[l+1...j] < v ,arr[j+1...i] >= v int j = l; for(int i = l+1;i<=r;i++){ if(arr[i] < v){ swap(arr[j+1],arr[i]); j++; } } swap(arr[l],arr[j]); return j; } /** *对arr[l...r]部分进行快速排序 */ template<typename T> void __quickSort(T arr[],int l,int r){ // if(l >= r) // return; if(r - l<= 15){ insertSort(arr,l,r); return; } int p = __partition(arr,l,r); __quickSort(arr,l,p-1); __quickSort(arr,p+1,r); } template<typename T> void quickSort(T arr[],int n){ __quickSort(arr,0,n-1); srand(time(NULL)); } #endif /* QUICKSORT_H_ */

对于有很多重复键值得数组

其他不变,修改partition

/** * 优化的partition,避免有很多重复的键值导致极度不平衡 */ template<typename T> int __partition2(T arr[],int l,int r){ swap(arr[l],arr[rand()%(r - l +1)+l]); T v = arr[l]; //arr[l+1...i)<=v,arr[j...r]>=v int i = l+1,j = r; while(true){ while(i<=r && arr[i] < v) i++; while(j>=l+1 && arr[j] > v) j--; if(i > j) break; swap(arr[i],arr[j]); i++; j--; } swap(arr[l],arr[j]); return j; }

6.意见与建议

如果博友有任何问题或者建议,欢迎留言讨论

转载请注明原文地址: https://www.6miu.com/read-1600389.html

最新回复(0)