欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

《算法第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仓库,关于《算法第四版》的学习笔记