数据结构算法学习总结-慕课网（九）快速排序（从小到大）
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.意见与建议
如果博友有任何问题或者建议，欢迎留言讨论
