数据结构与算法(7)_排序

发表于 | 分类于

如何分析排序算法

排序算法的执行效率

最好情况,最坏情况,平均情况时间复杂度

在分析排序算法的时间复杂度时,要分别给出,最坏,最好,平均情况下的时间复杂度.初次之外还要说出,最好,最坏时间复杂度对应要排序的原始数据是什么样.

这么区分的原因是:

  • 有些排序算法会区分,为了好对比,所以我们最好都区分
  • 对于要排序的数据,有的接近有序,有的完全无序.有序度不同的数据,对于排序的执行时间肯定是有影响的,我们要知道排序算法在不同数据下的性能表现

时间复杂度的系数,常数,低阶

时间复杂度是反应数据规模n很大的时候的一个增长趋势,所以她表示的时候会忽略系数,常数,低阶.但是实际开发中,我们实际的排序数据可能是10个,100个,1000个.所以对同一阶时间复杂度排序算法性能比较的时候,我们就要把系数,常数,低阶也考虑进来.

比较次数和交换(移动)

基于比较的排序算法的执行过程,会涉及两种操作,一种是元素比较大小,另一种事元素交换或移动.所以我们在分析排序算法的执行效率的时候,应该把比较次数和交换(移动)次数也考虑进去.

排序算法的内存消耗

算法的内存消耗可以通过空间复杂度来衡量,排序算法也不例外.针对排序算法的空间复杂度,我们还引入一个新的概念,原地排序.原地排序算法就是特指空间复杂度是O(1)的排序算法.

排序算法的稳定性

针对排序算法,我们还有一个重要的度量指标,稳定性.这个概念是说,如果排序的序列中存在值相等的元素,经过排序之后,相等元素之间原有的先后顺序不变.

比如我们有一组数据2,9,3,4,8,3.按照大小排序之后是2,3,3,4,8,9.这组数据里有两个3.经过某种排序算法之后,如果两个3的前后顺序没有改变,那么我们就把这种排序算法叫做稳定的排序算法;如果前后顺序发生变化,那对应的排序算法就叫做不稳定排序算法.

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public void bubbleSort(int[] arr){
	int n = arr.length;
	if(n<=1) return;
	for(int i=0;i<n;i++){
		//提前退出冒泡排序的标志
		boolean flag = false;
		for(int j=0;j<n-i-1;j++){
			if(a[j] > a[j+1]){
				int tmp = a[j];
				a[j] = a[j+1];
				a[j+1] = tmp;
				flag = true; //表示有数据交换
			}
		}
		if(!flag) break;	//没有数据交换,提前退出
	}
}
  • 冒泡排序的过程只涉及相邻数据的交换操作,只需要常量级的临时空间,所以它的空间复杂度为O(1),是原地排序算法
  • 在冒泡排序中,只有交换才可以改变两个元素的先后顺序.为了保证冒泡排序算法的稳定性,当有两个元素大小相等的时候,我们不做交换,相同大小的数据在排序前后不会改变顺序,所以冒泡排序是稳定的排序算法
  • 冒泡排序的时间复杂度是,最好情况,要排序的数据已经有序了,我们只需要进行一次排序就够了,所以最好情况时间复杂度是O(n).而最坏的情况是,要排序的数据刚好是倒序排列的,我们需要进行n次冒泡操作,所以最坏时间复杂度是O($$n^2$$).

平均时间复杂度

对于包含n个数据的数组,这n个数据就有n!种排列方式.不同的排列方式,冒泡排序的执行时间肯定是不同的.如果用概率论方法定量分析平均时间复杂度,设计数学推理和计算会很复杂.我们通过有序度和逆序度,这两个概念来分析.

有序度是数组中具有关系元素对的个数.有序元素对用数学表达式就是: a[i] <= a[j], 如果i < j; 例如图:

同理,对于一个倒序排列的数组,比如6,5,4,3,2,1,有序度是0;对于一个完全有序的数组,比如1,2,3,4,5,6有序度就是n(n-1)/2,也就是15.我们把这种完全有序的数组的有序度叫做满有序度.

逆序度的定义正好跟有序度相反(默认从小到大为有序).即: a[i] > a[j], 其中i<j;

关于这三个概念,我们还可以得到一个公式: 逆序度=满有序度-有序度.我们排序的过程就是一种增加有序度,减少逆序度的过程,最后达到满有序度.

冒泡排序包含两个操作原子,比较和交换.每交换一次,有序度就加1.不管怎么改进算法,交换的次数总是确定的,即为逆序度,也就是n (n-1)/2–初始有序度.对于包含n个数据的数组进行冒泡排序,初始状态的有序度是0,所以要进行n (n-1)/2次交换.最好情况下有序度是n (n-1)/2.就不需要进行交换.所以平均情况下,需要n * (n-1)/4次交换操作,比较操作肯定要比交换操作多,而复杂度的上限是O($$n^2$$),所以平均情况时间复杂度为O($$n^2$$)

插入排序

首先我们将数组中的数据分为两个区间,已排序区间和未排序区间.初始已排序区间就是数组的第一个元素.插入算法的核心思想就是取未排序区间的元素,在已排序区间找到合适的位置插入,并保证已排序区间一直有序.重复这个过程,直到排序完成.

插入排序也包含两种操作,一种是元素比较,一种是元素移动.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public void insertionSort(int[] arr){
	int n = arr.length;
	if(n<=1) return;
	for(int i=1;i<n;i++){
		int value = arr[i];
		int j = i-1;
		for(;j>=0;--j){
			if(a[j] > value){
				a[j+1] = a[j]; //数据移动
			}else{
				break;
			}
		}
		a[j+1] = value; //插入数据
	}
}
  • 插入排序算法并不需要额外存储空间,所以它的空间复杂度为O(1),是原地排序算法
  • 对于值相同的元素我们可以选择将后面出现的元素,插入到前面元素的后面,这样就可以保持原有的前后顺序不变,所以插入排序是稳定的排序算法
  • 插入排序的时间复杂度. 如果排序的数据是有序的,我们并不需要搬移任何数据.如果我们从尾到头在有序的数据组里查找插入位置,每次只要比较一个数据就能确定位置,所以这种情况下最好时间复杂度是O(n).注意是从尾到头遍历已经有序的数据.如果数组是倒序的,每次插入都相当于在数组的第一个位置插入新的数据.所以最坏情况时间复杂度为O($$n^2$$).数组中插入一个数据的平均时间复杂度是O(n),对于插入排序来说,每次插入操作都相当于在数组中插入一个数据,循环执行n次插入操作,所以平均时间复杂度为($$n^2$$).

选择排序

选择排序算法的实现思路类似插入排序,也分已排序区间和未排序区间.但是选择排序每次会从未排序区间找到最小的元素,将其放到已排序区间的末尾.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static void selectionSort(int[] arr){
	int n = arr.length;
	if(n<=1) return;
	for(int i=0;i<n;i++){
		//查找最小值
		int minIndex = i;
		for(int j=i+1;j<n;j++){
			if(arr[j] < arr[minIndex]){
				minIndex = j;
			}
		}
		//交换
		int tmp = arr[i];
		arr[i] = arr[minIndex];
		arr[minIndex] = tmp;
	}
}
  • 选择排序的空间复杂度为O(1),也是原地排序算法.
  • 选择排序是一种不稳定的排序算法
  • 选择排序最好,最坏,平均时间复杂度都是O($$n^2$$).

归并排序

归并排序的核心思想是分治思想.如果要排序一个数组,我们先把数组从中间分成前后两部分,然后对前后两部分分别排序,再将排好序的两部分合并在一起.这样整个数组就有序了.

分治思想.分治,顾名思义,就是分而治之,将一个大问题分解成小的子问题来解决.分治思想跟递归思想很像.分治算法一般都是用递归来实现的.分治是一种解决问题的处理思想,递归是一种编程技巧.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
    * @param a 待排序的数组
    * @param p  排序的起点
    * @param r  排序的终点
    */
public static void mergeSortInternally(int[] a,int p, int r){
	//递归终止条件
	if(p>=r) return;
	int q = (p + r)/2
	mergeSortInternally(a,p,q);
	mergeSortInternally(a,q+1,r);
	merge(a,p,q,r);
}

public static void merge(int[] a,int p, int q, int r){
	int i = p;
	int j = q+1;
	int k = 0;
	
	int[] tmp = new int[r-p+1];
	
	while(i<=q && j<=r){
		if(a[i] < a[j]){
			tmp[k++] = a[i++];
		}else{
			tmp[k++] = a[j++];
		}
	}
	int start = i;
	int end = q;
	if(j<=r){
		start = j;
		end = r;
	}
	while(start<=end){
		tmp[k++] = tmp[start++];
	}

	for(i=0;i<=r-p;i++){
		a[p+i] = tmp[i];
	}
}

归并排序性能分析

归并排序是稳定的排序算法吗

归并排序稳不稳定关键需要看merge方法.在合并过程中如果a[p….q]和a[q+1….r]之间有值相同的元素,那我们可以像代码中那样,先把a[p….q]中的元素放入tmp数组中.这样就保证了值相同的元素,在合并前后的先后顺序不变.所以,归并排序是一个稳定排序算法

归并排序的时间复杂度是多少

归并排序的时间复杂度,不管是最好情况,最坏情况,还是平均情况时间复杂度都是O(nlogn)

归并排序的空间复杂度

空间复杂度是O(n).

快速排序

快速排序算法,利用的也是分治思想.乍看起来,它有点想归并排序,但是思路其实是不一样的.

快速排序的思想:如果要排序数组中下标从p到r之间的一组数据,我们选择p到r之间的任意一个数据作为pivot(分区点).我们遍历p到r之间的数据,将小于pivot的放在左边,将大于pivot的放到右边,将pivot放到中间.

经过这么处理之后数据就被分成了3个部分,前面p到q-1之间都是小于pivot的.中间是pivot,后面的q+1到r之间是大于pivot的.

根据分治,递归处理思想,我们可以用递归排序下标从 p 到 q-1 之间的数据和下标从q+1 到 r 之间的数据，直到区间缩小为 1，就说明所有的数据有序了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
    * @param a 待排序的数组
    * @param p  排序的起点
    * @param r  排序的终点
    */
public static void quickSort(int[] a, int p, int r){
	if(p>=q) return;
	int q = partition(a,p,r);
	quickSort(a,p,q-1);
	quickSort(a,q+1,r);
}

public static int partition(int[] a, int p, int r){
	int pivot = a[r];
	int i = p;
	for(int j=p; j<r; j++){
		if(a[j] < pivot){
			int tmp = arr[i];
			arr[i] = arr[j];
			arr[j] = tmp;
			i++;
		}
	}
	int tmp = arr[i];
	arr[i] = arr[r];
	arr[r] = tmp;
	return i;
}

快速排序是一个不稳定排序算法,但是原地排序算法.

快速排序的时间复杂度也是O(nlogn),但是在极端状态下,比如1,3,5,6,8.如果我们每次都选择最后一个元素作为pivot,那每次分区得到的两个区间都是不均等的,我们需要进行大约n次操作,才能完成快排的整个过程,每次分区平均要扫码大约n/2个元素,这种情况下快排的时间复杂度就从O(nlogn)退化成了O($$n^2$$).

归并排序与快速排序的区别

//todo 图片7

归并排序处理过程是由下到上的,先处理子问题,最后再合并.而快速排序正好相反,它的处理过程是由上到下的,先区分,然后再处理子问题. 归并排序虽然是稳定的,时间复杂度为O(nlogn)的

## 线性排序
桶排序,计数排序,基数排序,这些排序算法的时间复杂度是线性的,我们把这类排序算法称为线性排序

桶排序

桶排序,顾名思义,会用到”桶”,核心思想是将要排序的数据分到几个有序的桶里,每个桶里的数据再单独进行排序.桶内排序之后,再把每个桶里的数据按照顺序依次取出,组成的序列就是有序的了

桶排序的时间复杂度是O(n).

桶排序特点及适用场景

桶排序对数据的要求非常苛刻.

首先要排序的数据需要很容易划分成m个桶,并且桶与桶之间有着天然的大小顺序

其次,数据在各个桶之间的分布是比较均匀的.如果分布不均,那时间复杂度就不是O(n)了.极端情况下,都分布到一个桶里,时间复杂度就退化到O(nlogn)了

桶排序比较适合用在外部排序中.所为的外部排序就是数据存储在外部磁盘中,数据量比较大,内存有限,无法将全部数据加载到内存中

计数排序

个人感觉,计数排序是桶排序的一种特殊情况.当要排序的n个数据,所处的范围并不大的时候,比如最大值k,我们就可以把数据化成k个桶,每个桶内的数据值都是相同的,省掉了桶内排序的时间.

假设有8个考生,分数在0~5之间.这个考生的分数放在一个数组A[8]中,分别是A[8]={2,5,3,0,2,3,0,3}.

考生的成绩从0到5,我们使用大小为6的数组C[6]表示桶,其中下标对应分数,存储对应分数的考生的个数,此时
C[6]={2,0,2,3,0,1}.

那我们如何快速计算出,每个分数的考生在有序数组R中对应的位置呢?

思路是这样的:我们对C[6]数组求和,计算出小于等于某个分数的人数.即C[k]里存储小于等于分数k的考生个数.此时C[6]={2,2,4,7,7,8}.

我们依次从后到前扫描数组A,比如当扫描到3时,我们可以从数组C中去除下标为3的值7,也就是说到目前未知,包括自己在内,分数小于等于3 的考生有7个,也就是说3是数组R中的第7个元素(也就是R数组下标为6的位置),当3放入到数组R中后,小于等于3的就只剩下6个了,所以相应的C(3)要减1,变成6.

一次类推,当我们扫描完整个数组A后,数组R内的数据就是安装分数从小到大的有序排列了.

//todo 如图8

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
public class CountingSort{
	/**
	* 计数排序
	* @param a 排序数组
	* @param n 数组大小,不需要减1
	* 假设数组中存储的都是非负整数
	*/
	public static void countingSort(int[] a, int n){
		if(n<=1) return;

		//查找数组中的数据范围
		int max = a[0];
		for(int i=1;i<n;i++){
			if(max<a[i]){
				max = 	a[i];
			}
		}
		
		//申请一个计数数组c,下标大小[0,max]
		int[] c = new int[max+1];
		for(int i=0;i<max+1;i++){
			c[i] = 0;
		}
		
		//计算每个元素的个数,放入数组C中
		for(int i=0;i<n;i++){
			c[a[i]]++;
		}	
	
		//依次累加
		for(int i=1;i<max+1;i++){
			c[i] = c[i-1]+c[i];
		}

		//临时数组r,存储排序之后的结果
		int[] r = new int[n];
		//计数排序的关键步骤
		for(int i= n-1;i>=0;i--){
			int index = c[a[i]] - 1;
			r[index] = a[i];
			c[a[i]]--;
		}
		
		//将结果拷贝回原数组
		for(int i=0;i<n;i++){
			a[i] = r[i];
		}
	}
}

计数排序只能用在数据防卫不大的数据当中,如果数据范围k比要排序的数据n大很多,就不适合用计数排序了.而且计数排序只能给非负整数排序,如果要排序的数据是其他类型的,要将其在不改变其大小的情况下,转化为非负整数.

基数排序

基数排序对要排序的数据是有要求的,需要可以分割出独立的”位”来比较,而且位之间有递进关系,如果a数据的高位比b数据大,那剩下的低位就不用比较了.除此之外每一位的数据范围不能太大,要可以用线性排序算法来排序,否则基数排序的算法时间复杂度就不会是O(n)了.

假如我们有10万个手机号码,从小到大排序,手机号码有11位,范围太大,显然不适合桶排序和计数排序.针对这个问题要使用基数排序.

借助稳定排序算法,先按照最后一位来排序手机号,然后再照倒数第二位来排序,以此类推经过11次排序后,手机号码就有序了

注意要按每位来排序的排序算法要稳定的.根据每一位来排序,我们可以根据桶排序或者计数排序,他们的时间复杂度可以做到O(n),如果要排序k次,总的时间复杂度就是O(k*n).k在这里最大就11,所以可以做到近似O(n).