By

Contents
  1. 1. 不同算法之间的比较
    1. 1.1. 总则：
    2. 1.2. 性能可视化
    3. 1.3. 源码下载
  2. 2. 经典排序算法概要分析
    1. 2.1. 选择排序
    2. 2.2. 冒泡排序
    3. 2.3. 插入排序
    4. 2.4. 希尔排序
    5. 2.5. 快速排序
    6. 2.6. 归并排序
    7. 2.7. 堆排序
    8. 2.8. 优先队列
  3. 3. 关键代码实现
    1. 3.1. 选择排序代码
    2. 3.2. 冒泡排序代码
    3. 3.3. 插入排序代码
    4. 3.4. 希尔排序代码
    5. 3.5. 快速排序代码
    6. 3.6. 归并排序代码
    7. 3.7. 堆排序代码
    8. 3.8. 优先队列代码

不同算法之间的比较

总则：

1）结合实际数据的情况

  • 数组的数量不大的情况下，其实比较算法的优劣根本没有意义,相对来说，数量不大的情况下，插入排序比快排 归并排序 堆排序更快
  • 内存非常充裕的时候，最佳的算法又不同了,归并排序就有意义了；
  • 如果数组已经是一个接近有序的数组，插入排序就是最快的。

2）结合计算机的实际情况
排序的性能消耗包括：

  • 查找的成本
    例如取arr[3] 和从链表中 取Node[3]的消耗完全不同，当查找的性能不重要的时候，通过链表来实现排序，可能算法非常不同（例如基于二分查找的插入排序 会比用数组的普通插入排序要快的多）
  • 交换的成本 ，当交换的成本变得很高的时候，选择排序或许就是最佳的排序方式
  • 比较的成本

性能可视化

在JDK 1.6 环境下，一个数组数量初始为1000，按照1000递增到10000大小，排序所耗费的毫秒数，见下图。 其中希尔排序使因为性能远远高于插入和冒泡，图像是灰色靠近X轴

冒泡、插入、希尔排序性能比较

源码下载

https://github.com/huangzhenshi/Algorithms_Fourth

经典排序算法概要分析

选择排序

1）原理：遍历所有的元素，min作为指针找到最小的元素的下标，结束后，替换第i个元素和最小的元素交换位置,一直到最后一个元素为止。
2）特点：

  • 不需要额外的内存空间
  • 交换的次数是所有的排序算法里面最少的，当交换的成本很高的时候，冒泡排序就是最高效的排序算法
  • 缺点是比较的次数太多了，每次排序了一个元素之后，第二次查询未用到第一次查询累计的结果
  • 时间复杂度是平方级别的。

冒泡排序

1）原理：在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。

2）特点：就是选择排序的糟糕版本，需要和选择排序相同的比较次数，和比较次数相同的交换次数，原本可以用一个下标标识最大值元素就可以避免大量的交换，可谓是糟糕的算法

插入排序

1）原理：桥牌打发，从二个元素开始，维护一个递增的数组，如果某元素小于 最大值，就和最大值互换位置，与次大值比较

2）特点：

  • 最适合已经有序或者基本有序的数组（数组中只有几个元素的位置不正确，每个元素距离它的最终位置都不远）
  • 数组的数量较少时，插入排序最优，一般JDK1.7 认定数量小于47的时候默认就用插入排序了。
  • 时间复杂度 N平方级别，但是比冒泡排序要快，但是交换的次数更多

希尔排序

1）原理：基于插入排序的加强版，先大跨度的做插入排序（先13调，调完再按4来调），基本接近最后位置，再按照1的一次完整插入排序.任意相隔 H 的元素都是有序的，由许许多个独立的有序的小数组组成

2）特点：

  • 小小的一个改进，让时间复杂度变成 N 1<X<2次方级别

3）备注：
网上的版本不一样，有的是按照size/2 的递减，不是按照 h=h*3+1 这种递增。

快速排序

1）原理：获取一个随机且不重复的数组（如果不随机的话，需要随机打乱）；每次把首位元素作为哨兵，通过遍历，找到该哨兵在这个数组中的准确位置，交换位置后；把数组拦截成3部分: 所有的比哨兵小的数组、哨兵、所有的比哨兵大的数组；然后递归，直至全部有序。

2）特点：

  • 需要该数组的分布是随机的，每次的哨兵才能更好的把大数组变成两个小数组
  • 时间复杂度 N*LOG(N)

3）改进算法：

  • 三向快速排序，可以实现含有重复值的快速排序，更能适应实际问题
  • 当递归后数组的长度小于某个常数的时候，改用插入排序，会明显提升性能

归并排序

1）原理：把一个数组两两切分，直到变成只有1个元素为止，再把每个有序的数组（只有1个元素肯定是有序的），两两归并，最后的数组就是一个有序的数组了。核心是一个把2个有序的数组归并为一个有序的数组的merge() 方法，然后递归合并即可。

2）特点:

  • 每次都要new 一个长度一样的 aux[] 数组浪费内存
  • 性能不一定高才是关键
  • 不需要交换元素，直接重新赋值即可，从辅助数组中取数，赋值到原数组中
  • 加强版的归并排序，当数组长度小于10的时候用插入排序，可以大幅提升排序性能
  • 时间复杂度为O(nlog₂n) 这是该算法中最好、最坏和平均的时间性能。归并排序比较占用内存，但却是一种效率高且稳定的算法。

堆排序

1）原理：基于优先队列的实现(关键是sink方法)

  • 先把数组变成一个 首位是null， 后续挨个的数组，此时为无序堆
  • 从N/2的位置开始，挨个sink排序，使无序堆有序
  • 挨个获取到堆顶元素 ，获取最大值，交换到数组末位，然后缩小长度，轮询操作

2）特点：

  • 优先队列的引用，一个堆有序的结构，虽然不是数组有序，但是可以很小的成本找到最大值并且快速恢复堆有序。
  • 时间复杂度 N*LOG(N)

优先队列

优先队列解决的问题：
1）快速的找到数组中的最大值
2）插入一个值，可以以对数级别的成本构建堆有序
3）删除最大值，可以以较小的成本恢复堆有序

关键代码实现

选择排序代码

	//数据源是一个不重复的数组
	public void sort(int[] arr){
	//从第一个数组开始和后面 (n-1）个数据比较，但是当i=最后一个的时候  arr[max]的时候就不需要比较了
	for(int i=0;i<arr.length-1;i++){
		int min=i;
		for(int j=i+1;j<arr.length;j++){
			if(less(arr[j],arr[min])) min=j;
		}
		exch(arr,i,min);
	}
}

冒泡排序代码

public  void sort(int[] arr){
	for(int i=0;i<arr.length-1;i++){
		for(int j=1;j<=arr.length-i-1;j++){
			if(arr[j-1]>arr[j]){
				exch(arr,j,j-1);
			}
		}
	}
}

插入排序代码

//数据源是一个不重复的数组
//排序规则：桥牌打发，从二个元素开始，维护一个递增的数组，如果某元素小于 最大值，就和最大值互换位置，与次大值比较
public static void sort(int[] arr){
	count=0;
	exchCount=0;
	for(int i=1;i<arr.length;i++){
		int j=i;
			while(j>0&&less(arr[j],arr[j-1])){
				exch(arr,j,j-1);
				j--;
			}
	}
}

希尔排序代码

//排序规则：基于插入排序的加强版，先大跨度的做插入排序（先13调，调完再按4来调），基本接近最后位置，再按照1的一次完整插入排序
//特点1）任意相隔 H 的元素都是有序的    2）由许许多个独立的有序的小数组组成 
@Override
public  void sort(int[] arr){
	count=0;
	exchCount=0;
	int size=arr.length;
	int h=1;
	while(h<size/3) h=h*3+1;   // 1 4 13 40 grow with size ,多乘一次，就多一次跨度的希尔排序
	
	while(h>=1){
		for(int i=h;i<size;i++){
			for(int j=i;j>=h&&less(arr[j],arr[j-h]);j-=h){
				exch(arr,j,j-h);
			}
		}
		h=h/3;
	}
	
}

快速排序代码

	//递归按照切分段 给数组排序
public void sortPart(int[] arr,int lo,int hi){
	if(lo>=hi) return;
	int index=partition(arr,lo,hi);
	// 注意这里把数组分成3部分， 是 index-1 ； index；index+1 三部分
	sortPart(arr,lo,index-1);
	sortPart(arr,index+1,hi);
}
// 功能： 1）移动数组   2）返回切分后的切分下标
private static int partition(int[] arr,int lo,int hi){
	int i=lo,j=hi+1;
	int v=arr[lo];
	while(true){
		// 5  1 3 8 4 6 9 2 11   --> 1 3 8  i=2  arr[2]=8      
		
		//标杆值 从初始位置挨个和后续元素比较，直到后续元素比标杆元素大，或者是后续元素到了最后的位置
		//下标i 移动，直到找到比标杆元素大的下标为止，获取到i的值，要交换
		while(less(arr[++i],v)){
			if(i>=hi) break;
		}
		
		// 5  1 3 8 4 6 9 2 11  -->2 11 j=7 arr[7]=2 
		
		while(less(v,arr[--j])){
			if(j<=lo) break;
		}
		if(i>=j) break;
		//交换之后 因为i 和 j的值是在外面申明过的，所以不会重复比较之前比较过的对象 从 arr[i] -- arr[j] 区间继续比较
		// 5  1 3 2      4 6 9       8 11  --> 8  和 2 交换位置
		exch(arr,i,j);
	}
	//一定要记得 最后一次要把标杆值 和新的标杆值交换位置啊
	exch(arr,lo,j);
	return j;
}

归并排序代码

	@Override
public  void sort(int[] arr){
	sort(arr,0,arr.length-1);
}
//递归按照切分段 给数组排序
public void sort(int[] arr,int lo,int hi){
	if(lo>=hi) return;
    int mid=lo+(hi-lo)/2;
	sort(arr,lo,mid);
	sort(arr,mid+1,hi);
	merge(arr,lo,mid,hi);
}
// arr数组 arr[0] -- arr[mid] 是有序的数组； arr[mid+1] -- arr[hi] 也是有序的数组，当mid=0的时候，就只有一个元素的时候肯定就是有序的数组了
public void merge(int[] arr, int lo,int mid,int hi){
	//i 表示 arr1 的轮询到的下标位置， lo<=i<=mid  ； i++
	int i=lo;
	
	//j 表示 arr2 的轮询到的下标位置，mid+1<=j<=hi ； j++
	int j=mid+1;
	
	//申明一个数组作为辅助数组，拷贝出
	int[] aux =new int[arr.length];
	for(int k=lo;k<=hi;k++){
		aux[k]=arr[k];
	}
	for(int k=lo;k<=hi;k++){
		//当第一个数组元素用尽的时候，后续就不需要调整了，因为后面的数组本来就是有序的
		if(i>mid) 						return;
		//当第二个数组元素用尽的时候，就需要把前面的i之后的元素，填充到后面当中
		else if(j>hi)					arr[k]=aux[i++];
		//记住这里是 用不变数值的 aux数组进行比较啊，千万不能用 arr 原数组比较啊，坑爹
		else if(less(aux[j],aux[i]))    arr[k]=aux[j++];
		else 							arr[k]=aux[i++];
	}
}

堆排序代码

//不同于 MaxMQ，已知一个无序的堆，进行排序成 数组有序
public void sort(List<Integer> list){
	int N=list.size()-1;
	//先把数组构建成堆结构
	for(int k=N/2;k>=1;k--){
		sink(k,N);
	}
	int copySize=N;
	//需要重写 或者扩展 sink 方法，要让 sink 是根据 size大小进行下沉
	//这里递减的要用 copySize啊，因为要循环N 次，如果直接用N--的话， k每增加一次 ，N就减少1次，只能做到一半的数据排序了
	for(int k=1;k<=N;k++){
		exch(1,copySize);
		sink(1,--copySize);
	}
}

优先队列代码

public void swim(int index){
		while(index>1&&less(list.get(index/2),list.get(index))){
				exch(index/2,index);
			index=index/2;
		}
	}
	
	//递归的三个条件
	//1)如果有子节点的话，就继续比较，可以是1个子节点，也可以是2个子节点
	//2)如果有2个子节点且第二个子节点更大的话，最大子节点的下标就要++ ，也就是取第二个节点
	//3)判断 父节点 和最大的子节点的大小
	public void sink(int index){
		//如果有子节点的话，就继续比较，可以是1个子节点，也可以是2个子节点
		while(2*index<=size()){
			int childmax=2*index;
			//如果有2个子节点且第二个子节点更大的话，最大子节点的下标就要++ ，也就是取第二个节点
			if(childmax+1<=size()&&less(list.get(childmax),list.get(childmax+1))){
				childmax++;
			}
			
			if(less(list.get(childmax),list.get(index))) break;
			exch(childmax,index);
			index=childmax;
		}
	}
Contents
  1. 1. 不同算法之间的比较
    1. 1.1. 总则：
    2. 1.2. 性能可视化
    3. 1.3. 源码下载
  2. 2. 经典排序算法概要分析
    1. 2.1. 选择排序
    2. 2.2. 冒泡排序
    3. 2.3. 插入排序
    4. 2.4. 希尔排序
    5. 2.5. 快速排序
    6. 2.6. 归并排序
    7. 2.7. 堆排序
    8. 2.8. 优先队列
  3. 3. 关键代码实现
    1. 3.1. 选择排序代码
    2. 3.2. 冒泡排序代码
    3. 3.3. 插入排序代码
    4. 3.4. 希尔排序代码
    5. 3.5. 快速排序代码
    6. 3.6. 归并排序代码
    7. 3.7. 堆排序代码
    8. 3.8. 优先队列代码