《算法第4版》第2章排序—学习笔记
程序员文章站
2022-05-07 17:22:46
...
排序算法
- 大多数排序算法的性能和输入模型有很大的关系,不同的算法适用于不同应用场景中的不同输入
- 操作抽象:抽象less()和exch()等排序共同操作,有利于代码理解和程序的可移植性
排序算法的共同操作
/*比较方法*/
static bool less(T a, T b) {
return a < b; //调用比较方法
}
/*交换方法*/
static void exchange(T a[], int i, int j) {
T temp = a[i];
a[i] = a[j];
a[j] = temp;
}
/*打印方法*/
static void show(T a[], int Len) {
cout << "数组元素:";
for (int i = 0; i < Len; i++) {
cout << a[i] << " ";
}
cout << endl;
}
/*判断有序方法*/
static bool isSorted(T a[], int Len) {
for (int i = 1; i < Len; i++) {
if (less(a[i], a[i - 1]))
return false;
}
return true;
}
初级排序算法
选择排序
思想
- 找到数组中最小的元素,然后与未排序数组中的第一个元素交换
- 交换N-1次之后,排序完成
实现代码
void SelectSort(T a[], int Len) {
int min;
for (int i = 0; i < Len - 1; i++) {
min = i;
for (int j = i + 1; j < Len; j++) {
if (less(a[j], a[min]))//比较函数
min = j;
}
exchange(a, i, min);//交换函数
}
}
特点
- 运行时间与输入无关,即时间复杂度均是O(N*N)
- 在所有算法中,数据移动是最少的(交换次数与数组大小是线性关系)
- 比较次数:(N-1,N-2,N-3,…,1)==N*N/2
- 交换次数:N
插入排序
思想
- 将数组分为已排序部分和未排序部分,每次从未排序部分中选择第1个元素与已排序部分的元素比较,若比末尾元素大,就添加到已排序部分末尾,否则交换两元素位置,继续向前比较,直到比前一个元素大为止。
实现代码
//插入排序
void InsertSort(T a[],int Len){
int j;
for(int i=1;i<Len;i++){
j=i;
while(less(a[j],a[j-1])&&j>0){//比较操作
exchange(a,j, j-1);//交换操作
j--;
}
}
}
特点
- 运行时间与输入元素的初始顺序有关
- 面对部分有序或基本有序数组十分高效(利用算法的最好情况),也适合小规模数据
- 数组中每个元素离最终位置都不远
- 一个有序的大数组+一个小数组
- 数组中只有几个元素位置不确定
- 比较次数:最好:N-1;最坏:N*N/2;平均:N*N/4
- 交换次数:最好:0;最坏:N*N/2;平均:N*N/4
- 倒置很少时,排序效率可能是算法中最好的
选择排序与插入排序的比较
- 在随机排序的无重复主键的数组中,插入排序比选择排序大约快1倍
高级排序算法
希尔排序
思想
- 是一种基于插入排序的增量排序算法
- 对任意间隔为k的子数组进行排序,当所有间隔为k的子数组有序之后,对k进行增量缩小,继续进行增量为k的插入排序,直到k为1。k=1时,数组现在已经变得基本有序,最后进行一次插入排序,排序完成
代码实现
//希尔排序
void ShellSort(T a[],int Len){
int gap=1;//增量
while(gap<Len/3) gap=3*gap+1;//采用1,4,13,40,121,......的增量序列
while(gap>=1){
//按增量进行的插入排序
for(int i=gap;i<Len;i++){
for(int j=i;j>0&&less(a[j], a[j-gap]);j-=gap){
exchange(a, j, j-gap);
}
}
gap=gap/3;
}
}
特点
- 希尔排序的时间复杂度难以估量,大概在N^(3/2)
- 希尔排序是最简单的高级排序算法
- 希尔排序的效率依赖于增量序列(可以选择3*k+1,足以胜任大部分应用问题)
- 会破坏数组的稳定性
- 不需要额外的内存空间
归并排序
思想
- 基于分治思想的递归算法
- 分治核心:将1个大数组划分为2个小数组处理
- 递归核心:将2个有序数组合并成1个更大的有序数组
- 将数组不停地2分为小数组,直到分为2^n个仅含有1个元素的数组,然后对小数组依次进行合并成更大的有序数组
- 1/1合并为2,2/2合并为4,4/4合并为8,直到合并为N为止
实现代码
//归并有序数组
static void Merge(T a[],T aux[],int lo,int mid,int hi){
//复制数据到辅助数组
for(int i=lo;i<=hi;i++){
aux[i]=a[i];
}
//归并
int i=lo,j=mid+1;
for(int k=lo;k<=hi;k++){
if(i>mid) a[k]=aux[j++];
else if(j>hi) a[k]=aux[i++];
else if(less(aux[i], aux[j])) a[k]=aux[i++];
else a[k]=aux[j++];
}
}
/**
* 自顶向下的归并排序
*/
static void MergeSort(T a[],T aux[],int lo,int hi){
if(hi<=lo) return ;
int mid=(lo+hi)/2;
MergeSort(a,aux, lo, mid);
MergeSort(a, aux,mid+1, hi);
if(a[mid]>a[mid+1]){
Merge(a, aux,lo, mid, hi);
}
}
/**
* 自底向上的归并排序
* 效率:与自顶向下的归并排序效率相当
*/
static void MergeSortBU(T a[],T aux[],int Len){
for(int aSize=1;aSize<Len;aSize*=2){
for(int lo=0;lo<Len;lo+=2*aSize){
int hi=lo+2*aSize-1,mid=lo+aSize-1;
hi=hi>(Len-1)? Len-1:hi;
Merge(a, aux, lo, mid, hi);
}
}
}
特点
- 归并排序算法的时间复杂度NlgN,空间复杂度是N
- 是一个稳定的排序算法
- 是一种渐进最优的基于比较的算法
- 自底向上的归并排序比较适合用链表组织的数据
算法改进
对小规模数组使用插入排序
- 一般数组中元素个数在5-15之间使用插入排序比较合适
- 效率大概能够提升1个数量级
/*在指定区间上的插入排序*/
static void InsertSortLimit(T a[],int lo,int hi){
for(int i=lo+1;i<=hi;i++){
for(int j=i;less(a[j],a[j-1])&&j>lo;j--){
exchange(a, j-1, j);
}
}
}
//归并·排序
static void MergeSort(T a[],T aux[],int lo,int hi){
if(hi<=lo+15){
InsertSortLimit(a,lo,hi);
return;//如果没有return,程序就不会退出,陷入死循环
}
int mid=(lo+hi)/2;
MergeSort(a,aux, lo, mid);
MergeSort(a, aux,mid+1, hi);
if(a[mid]>a[mid+1]){
Merge(a, aux,lo, mid, hi);
}
}
归并前判断数组是否已经有序
- 对于有序数组,时间复杂度是N
- 修改判断归并数组1右端小与数组2左端及直接返回
- 改进效率:处理任意有序数组变为线性时间
static void MergeSortBU(T a[],T aux[],int Len){
for(int aSize=1;aSize<Len;aSize*=2){
for(int lo=0;lo<Len;lo+=2*aSize){
int hi=lo+2*aSize-1,mid=lo+aSize-1;
hi=hi>(Len-1)? Len-1:hi;
if(a[mid]>a[mid+1]){
Merge(a, aux, lo, mid, hi);
}
}
}
}
快速排序
思想
- 一种基于分治思想的递归算法
- 分治核心:将1个大数组划分为2个小数组,减小处理的问题规模
- 递归核心:将大数组划分为2个小数组,不断迭代至数组规模小到可以直接处理
- 每次迭代:选定一个切分元素v,以v将数组划分为2个子数组,num1均为小于v的元素,num2均为大于等于v的元素
- 对子数组继续进行上面的划分操作,直到数组不能再划分
代码实现
//切分方法
static int partition(T a[],int lo,int hi){
int i=lo,j=hi+1;//扫描指针
T part=a[lo];//切分元素
while(1){
while(less(a[++i],part)){
if(i==hi) break;
}
while(less(part, a[--j])){
}
if(i>=j) break;
exchange(a, i, j);
}
exchange(a, lo, j);
return j;
}
//快速排序递归
static void QuickSort(T a[],int lo,int hi){
if(lo>=hi) return;
int part=partition(a, lo, hi);
QuickSort(a, lo,part-1);
QuickSort(a, part+1, hi);
}
//快速排序调用
static void QuickSort(T a[],int Len){
QuickSort(a,0,Len-1);
}
特点
- 快速排序是原地排序,空间复杂度是1,时间复杂度是NlgN
- 但是快速排序的最差性能是N*N,关键在于如何选取切分元素
- 随着数组规模增大,快排的运行时间会趋于平均运行时间NlgN
- 快速排序的内循环比较小,所以运行速度快
- 排序不稳定
- 快速排序一般比归并排序,希尔排序都要快
算法改进
小数组切换成插入排序
- 改进效率:快了10倍以上,提升一个数量级
/*在指定区间上的插入排序*/
static void InsertSortLimit(T a[],int lo,int hi){
for(int i=lo+1;i<=hi;i++){
for(int j=i;less(a[j],a[j-1])&&j>lo;j--){
exchange(a, j-1, j);
}
}
}
static void QuickSort(T a[],int lo,int hi){
if(hi<=lo+15){
InsertSortLimit(a, lo, hi);
return;//需要返回,不然会无穷递归
}
int part=partition(a, lo, hi);
QuickSort(a, lo,part-1);
QuickSort(a, part+1, hi);
}
采用三取样切分选取切分元素
- 改进效率:相比于原始快排,使用三取样切分快了10倍以上
static void QuickSortSub3(T a[],int lo,int hi){
if(lo>=hi) return;
int part=partition3(a, lo, hi);
QuickSortSub3(a, lo,part-1);
QuickSortSub3(a, part+1, hi);
}
//三取样切分
static T sub3partition(T a[],int lo,int hi){
T part;
if(hi-lo<2){
return a[lo];
}
T v1=a[lo],v2=a[lo+1],v3=a[lo+2];
int index;
//获取中位数:2次比较
if( (v1-v2)*(v2-v3)>0 )
index=lo+1;
else if( (v2-v1)*(v1-v3)>0 )
index=lo;
else index=lo+2;
part=a[index];
exchange(a,lo, index);
return part;
}
static int partition3(T a[],int lo,int hi){
int i=lo,j=hi+1;//扫描指针
T part=sub3partition(a, lo,hi);
while(1){
while(less(a[++i],part)){
if(i==hi) break;
}
while(less(part,a[--j])){ }
if(i>=j) break;
exchange(a,i,j);
}
exchange(a,lo,j);
return j;
}
- 取3个数字的中位数代码
//选取中位数:一行代码
//index= v1 > v2 ? (v2 > v3 ? lo+1 : (v1>v3? lo+2:lo)) : (v1 > v3 ? lo: (v2>v3? lo+2:lo+1));
//获取中位数:2次比较
if( (v1-v2)*(v2-v3)>0 )
index=lo+1;
else if( (v2-v1)*(v1-v3)>0 )
index=lo;
else index=lo+2;
采用三向切分
- 适用于存在大量重复的数据
- 改进效率:对于包含大量重复元素的输入,时间复杂度可以达到N
void QuickSortManyRepeat(T a[],int lo,int hi){
if(hi<=lo) return;
int lt=lo,i=lo+1,gt=hi;
T v=a[lo];
while(i<=gt){
if(a[i]<v) exchange(a,lt++,i++);
else if(a[i]>v) exchange(a,gt--,i);
else i++;
}
QuickSortManyRepeat(a, lo, lt-1);
QuickSortManyRepeat(a, gt+1, hi);
}
优先队列
API
class PriorityQueue{
private:
//队列最大长度
int maxSize;
//队列长度
int N=0;
//优先队列
T* pq;
//元素比较
bool less(int i,int j){}
//元素交换
void exchange(int i,int j){}
//上浮操作
void swim(int k){}
//下沉操作
void sink(int k){}
//动态调整队列长度
void reSize(int Len){}
public:
//创建最大容量为max的优先队列
MaxPQ(int max){}
//向优先队列中插入一个元素
void insert(T v){}
//返回最大元素
T max(){}
//删除并返回最大元素
T delMax(){}
//返回队列是否是空
bool isEmpty(){}
//返回优先队列中元素的数目
int size(){}
}
实现堆的操作
//上浮:
void swim(int k){
while(k>1&&less(k/2,k)){
exchange(k/2,k);
k=k/2;
}
}
//下沉:
void sink(int k){
while(2*k<=N){
int j=2*k;
if(j<N&&less(j,j+1)) j++;
if(!less(k,j)) break;
exchange(k,j);
k=j;
}
}
基于堆的优先队列的实现
- 对于插入元素和删除元素都是lgN的时间
template <class T>
class MaxPQ{
private:
//队列最大长度
int maxSize;
//队列长度
int N=0;
//优先队列
T* pq;
//元素比较
bool less(int i,int j){
return pq[i]<pq[j];
}
//元素交换
void exchange(int i,int j){
T temp = pq[i];
pq[i] = pq[j];
pq[j] = temp;
}
//上浮操作
void swim(int k){
while(k>1&&less(k/2,k)){
exchange(k/2,k);
k=k/2;
}
}
//下沉操作
void sink(int k){
while(2*k<=N){
int j=2*k;
if(j<N&&less(j,j+1)) j++;
if(!less(k,j)) break;
exchange(k,j);
k=j;
}
}
//动态调整队列长度
void reSize(int Len){
T* temp=new T[N+1];
for(int i=1;i<=N;i++){
temp[i]=pq[i];
}
pq=new T[Len];
for(int i=1;i<=N;i++){
pq[i]=temp[i];
}
delete [] temp;
}
public:
//创建最大容量为max的优先队列
MaxPQ(int max){
pq=new T[max];
maxSize=max;
}
//向优先队列中插入一个元素
void insert(T v){
pq[++N]=v;
swim(N);
//动态调整数组大小
if(N==maxSize){
reSize(2*N);
}
}
//返回最大元素
T max(){
T *result=NULL;
if(N!=0){
return pq[1];
}
return *result;
}
//删除并返回最大元素
T delMax(){
T max=pq[1];
exchange(1,N--);
pq[N+1]=NULL;//防止越界
sink(1);
//动态调整数组大小
if(N<=maxSize/4){
reSize(2*N);
}
return max;
}
//返回队列是否是空
bool isEmpty(){
return N==0;
}
//返回优先队列中元素的数目
int size(){
return N;
}
};
优先队列的应用场景
- 任务调度问题
- TopM问题:从输入流中找到最大的M个元素
- Multiway问题:将M个输入流归并为有序的输入流
堆排序
堆排序的实现
- 主要分为两个阶段:1.构造堆阶段 2.依次下沉排序阶段
/**
* 堆排序
*/
template <class T>
class HeapSort{
private:
//元素比较
bool less(T a,T b){
return a<b;
}
//元素交换
void exchange(T pq[],int i,int j){
T temp = pq[i];
pq[i] = pq[j];
pq[j] = temp;
}
//下沉操作
void sink(T a[],int k,int N){
//从根节点开始向下寻找最大的元素
while(2*k<=N){
int j=2*k;
//找到左右子节点的最大值
if(j<N&&less(a[j-1],a[j])) j++;
//如果父节点大于叶子节点的最大值就退出,否则就交换
if(!less(a[k-1],a[j-1])) break;
exchange(a,k-1,j-1);
//以最大的叶节点继续向下找
k=j;
}
}
public:
HeapSort(T a[],int Len){
int N=Len;
//构造堆
for(int k=N/2;k>=1;k--){
sink(a,k,N);
}
while(N>1){
exchange(a,1-1,N-1);
N--;
sink(a,1,N);
}
}
};
堆排序的特点
- 时间复杂度是NlgN,空间复杂度是常数
- 堆排序是唯一能够同时最优地利用时间和空间的算法
- 缺点是:无法利用缓存,因为不是在相邻元素之间进行比较
排序算法之间的比较
初级排序之间的比较
插入排序与选择排序的比较
- 一般情况下,插入排序比选择排序快1倍左右
- 而且插入排序是稳定排序算法
简单插入排序与优化的插入排序之间的比较
- inert:简单插入排序
- insertNoCheck:不用进行边界检测的插入排序
- insertNoExchange:不用进行元素交换的插入排序
- insertNoCheck与insert效率相当
- insertNoExchange比insert快大概1倍
高级排序算法之间的比较
快速排序与归并排序,希尔排序,堆排序之间的比较
- 一般情况下,快速排序比归并排序、希尔排序要快
- 虽然都是NlgN级别算法,但是快排的常数c往往要小一些,因为它的内循环比较小
- 相比于堆排序和希尔排序,快排是顺序访问元素,可以利用缓存
- 快速排序是最快的通用排序算法
- 如果需要稳定性排序,一般选择归并排序
总结
- 排序算法一般是所有应用的基础
- 不同的应用场景需要选择不同的排序算法
感兴趣的可以看我的github仓库,关于《算法第四版》的学习笔记
下一篇: Win2003 安全设置大全
推荐阅读