常见排序算法（2）

发表于 | 更新于 | 分类于 | 阅读次数： | 字数： 3,288 | 阅读时长： 15

冒泡排序，插入排序，选择排序，快速排序，希尔排序，归并排序等可参考： 排序算法（1）

快速排序优化及分区扫描法：

该篇文章主要记录了堆排序，计数排序，桶排序，基数排序等。

堆排序

堆排序的概念：

堆排序（英语：Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。（百度百科）

堆的概念：

堆（英语：heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质：

  • 堆中某个节点的值总是不大于或不小于其父节点的值；
  • 堆总是一棵完全二叉树。

将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。

算法描述：

因为堆是有大根堆和小根堆，利用堆的性质，可以对数组排序。具体做法：

  1. 首先将无序数组建立大根堆。(建立大根堆的过程运用了递归，从最后将每个根元素与左右孩子比较，将较大的放到根位置，递归执行每个节点。最后根元素就是最大值。)
  2. 然后数组第一个肯定为最大数，将第一个与数组最后一个数交换。
  3. 缩小堆的范围，将堆总长度减1，不用管最后一个，最后一个肯定是最大数。此时，在缩小堆的基础上继续建立大根堆。然后第一个为此堆的最大，与倒数第二个数互换。
  4. 循环这个2-3过程，就从小到大排好了序。

动图演示：

堆排序

堆排序2

图：堆排序过程示意图

## java代码示例：

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
50
51
52
53
54
55
56
57
58
59
public class HeapSort {

	public static void main(String[] args) {
		int[] arr = {13, 91, 52, 66, 95, 89, 62, 75, 61, 6};
		util.ArrayUtil.printArr(arr);
		heapSort(arr);
		util.ArrayUtil.printArr(arr);
	}
	
	public static void heapSort(int[] arr) {
		//先进行堆化
		bigHeap(arr);
		//把堆顶元素和最后一个元素对调
		int n = arr.length;
		for(int x = n - 1; x > 0; x--) {
			util.Swap.swap(arr, 0, x);
			//缩小堆的范围，对堆顶元素进行向下调整
			bigHeapFixUp(arr, 0, x - 1);
		}
	}
	
    //制作大根堆
	public static void bigHeap(int[] arr) {
		int n = arr.length;
		for(int i = n / 2 - 1; i >= 0; i--) {
			bigHeapFixUp(arr, i, n);
		}
	}
	
    //大根上浮调整
	public static void bigHeapFixUp(int[] arr, int i, int n){
		//找到左右两孩子
		int left = 2 * i + 1;
		int right = 2 * i + 2;
		//左孩子已经越界，i就是叶子节点
		if(left >= n) {
			return;
		}
		//找出左孩子和有孩子中较大的一个
		int max = left;
		//右孩子已经越界
		if(right >= n ) {
			 max = left;
		}else {
			if(arr[left] < arr[right]) {
				max = right;
			}
		}
		//如果arr[i]大于两个数不用调整
		if(arr[i] >= arr[max]) {
			return;
		}
		//否则，与两个孩子中较大的值，交换
		int tmp = arr[i];
		arr[i] = arr[max];
		arr[max] = tmp;
		bigHeapFixUp(arr, max, n);
	}
}


程序运行结果：

1
2
84 36 57 94 75 22 28 86 17 68 
17 22 28 36 57 68 75 84 86 94


## 算法分析：

- 时间复杂度： 堆化：一半的元素修复，修复是单分支的，所以整体堆化为nlgn/2
- 排序：n个元素都要取出，因此调整n次，每次调整修复同上是lgn的，整体为nlgn
- 空间复杂度：不需要开辟辅助空间

# 计数排序

计数排序：用辅助数组对数组中出现的数字计数，元素转下标，下标转元素。

## 算法描述：

1. 假设元素均大于等于0，依次扫描原数组，将元素值K记录在辅助数组的k位上。
2. 依次扫描辅助数组，如果为1，将其插入目标数组的空白处。

## 动图演示：

计数排序


图：计数排序动图演示

java示例代码：

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
public class CountSort {

	public static void main(String[] args) {
		int[] arr = util.ArrayUtil.arr(10);
		util.ArrayUtil.printArr(arr);
		countSort(arr);
		util.ArrayUtil.printArr(arr);
	}

	public static void countSort(int[] arr) {
		int[] helper = new int[maxOf(arr) + 1];
		for(int e : arr) {
			helper[e]++;
		}
		int current = 0; //数据回填的位置
		for(int i = 1; i < helper.length; i++) {
			//打印出重复的数据
			while (helper[i] > 0) {
				arr[current++] = i;
				helper[i]--;
			}
		}
	}
	//找出数组中最大的数值，用来开辟辅助空间
	public static int maxOf(int[] arr) {
		int max = arr[0];
		for(int i = 1; i < arr.length; i++) {
			if(max < arr[i]) {
				max = arr[i];
			}
		}
		return max;
	}
}

程序运行结果：

1
2
5 1 94 66 64 12 68 70 90 32 
1 5 12 32 64 66 68 70 90 94

上面的代码只能排都是正数的数组，当有负数时，不能用。

对于有负数的情况，我的思路是重新开辟一个空间，专门用来存放负数，当恢复的时候，倒着恢复即可。

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
public class CountSort {

	public static void main(String[] args) {
		//int[] arr = util.ArrayUtil.arr(10);
		int[] arr = {1, 3, -3, 6, -2, 1, 0, -5, 2};
		util.ArrayUtil.printArr(arr);
		countSort1(arr);
		util.ArrayUtil.printArr(arr);
	

	public static int maxOf1(int[] arr) {
		int max = Math.abs(arr[0]);
		for(int i = 0; i < arr.length; i++) {
			if(max < Math.abs(arr[i])) {
				max = Math.abs(arr[i]);
			}
		}
		return max;
	}
	
	public static void countSort1(int[] arr) {
		int[] helper1 = new int[maxOf1(arr) + 1];
		int[] helper2 = new int[maxOf1(arr) + 1];
		for(int e : arr) {
			if(e < 0) {
				helper2[-e]++;
			}else {
				helper1[e]++;
			}
		}
		int current = 0; //数据回填的位置
		//先恢复负数序列
		for(int i = helper2.length - 1; i > 0; i--) {
			while (helper2[i] > 0) {
				arr[current++] = -i;
				helper2[i]--;
			}
		}
		//先恢复正数序列
		for(int i = 0; i < helper1.length; i++) {
			//打印出重复的数据
			while (helper1[i] > 0) {
				arr[current++] = i;
				helper1[i]--;
			}
		}
	}
}

程序运行结果：

1
2
1 3 -3 6 -2 1 0 -5 2 
-5 -3 -2 0 1 1 2 3 6

性能分析：

优点：速度快。

缺点：数据范围很大，比较稀疏，会导致辅助空间很大，也稀疏，造成空间的浪费。

时间复杂度： 扫描一次原数组，扫描一次helper，复杂度为N+k

  • 空间复杂度：辅助空间k，k=maxOf(arr)
  • 非原址排序
  • 稳定性：相同元素不会出现交叉，非原址都是拷来拷去
  • 如果要优化一下空间，可以求minOf(arr)，helper的长度位max-min+1，这样能短点
  • 计数有缺陷，数据较为密集或范围较小时，适用。

桶排序

桶排序（BucketSort）：一句话概括为，通过“分配”和“收集”过程来实现排序。

  1. 工作的原理是将数组分到有限数量的桶子里
  2. 每个桶子再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）
  3. 桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间

算法思想：

设计k个桶（bucket），编号0~k-1，然后将n个输入数分布到各个桶中去，对各个桶中的数进行排序，然后按照次序把各个桶中的元素罗从小到大列出来即可。

动图演示：

桶排序

图：桶数排序动图演示

java代码示例：

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
import java.util.ArrayList;
import java.util.Collections;

public class BucketSort {

	public static void main(String[] args) {
		int[] arr = util.ArrayUtil.arr(10);
		util.ArrayUtil.printArr(arr);
		bucketSort(arr);
		util.ArrayUtil.printArr(arr);
	}

	// hash函数，用来往桶里分配数据。此时桶的个数等于数组元素个数
	public static int hash(int element, int max, int length) {
		return (element * length) / (max + 1);
	}

	public static void bucketSort(int[] arr) {
		int length = arr.length;
		@SuppressWarnings("unchecked")
		//初始化每个桶
		ArrayList<Integer>[] bucket = new ArrayList[length];// 桶的个数=length
		for(int i = 0; i < length; i++) {
			bucket[i] = new ArrayList<Integer>();
		}
		int max = maxOf(arr);
		//入桶
		for(int i = 0; i < length; i++) {
			//扫描每个元素
			int value = arr[i];
			int hash = hash(value, max, length);
			//如果是桶为空，则直接添加到桶中
			if(bucket[hash] == null) {
				bucket[hash].add(value);
			}else {//否则，以从小到大的排序插入桶的元素中
				bucket[hash].add(value);
				Collections.sort(bucket[hash]);
			}
		}
		
		//出桶
		int k = 0;//记录数组下标，回填数据
		for(int i = 0; i < length; i++) {
			//如果桶内不为空，从小到大回填到数组
			if(!bucket[i].isEmpty()) {
				for(int j = 0; j < bucket[i].size(); j++) {
					arr[k++] = bucket[i].get(j);
				}
			}
		}
	}

	//找出数组中最大的数值
	public static int maxOf(int[] arr) {
		int max = arr[0];
		for(int i = 1; i < arr.length; i++) {
			if(max < arr[i]) {
				max = arr[i];
			}
		}
		return max;
	}
}

程序运行结果：

1
2
15 52 72 45 83 54 35 14 54 61 
14 15 35 45 52 54 54 61 72 83

算法分析：

时间复杂度： O(N+C)，其中C=N*(logN-logM)

空间复杂度：N+M，M为桶的个数

非原址排序

稳定性：稳定

桶排序假设数据会均匀入桶，在这个前提下，桶排序很快！

基数排序

基数排序(Radix Sort)：是一种特殊的桶排序。通过位数来分配和收集。

算法思想：

先初始化0-9号十个桶，按个位数字，将关键字入桶，入完后，依次遍历10个桶，按检出顺序回填到数组中，如：

​ 321 322 331 500 423 476 926

​ 0:500

​ 1:321 331

​ 2:322

​ 3:423

​ 4:无

​ 5:无

​ 6:476 926

检出后数组序列为： 500 321 331 423 476 926，然后取十位数字重复过程一，得到

​ 0:500

​ 1:无

​ 2:321 423 926

​ 3:331

​ 4:无

​ 5:无

​ 7:476

检出后数组序列为： 500 321 423 926 331 476，然后取百位数字重复过程一，得到

​ 0:无

​ 1:无

​ 2:无

​ 3:321 331

​ 4:423 476

​ 5:500

​ 9:926

检出后数组序列为： 321 331 423 476 500 926，已然有序

但是我们应该继续入桶，不过因为再高位全部是0了，这些元素会按顺序全部进入0号桶，这时0号桶的size==数组的size，这时结束标志

最后再回填到数组，数组就是升序排列的了

动图演示：

基数排序

图：基数排序原理动图演示

java代码示例：

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
import java.util.ArrayList;

public class RadixSort {

	// 10个桶，每个桶装的数个数不定，适合用数组加ArrayList
	@SuppressWarnings("unchecked")
	private static ArrayList<Integer>[] bucket = new ArrayList[10];

	// 初始化桶
	static {
		for (int i = 0; i < bucket.length; i++) {
			bucket[i] = new ArrayList<Integer>();
		}
	}

	public static void main(String[] args) {
		int[] arr = util.ArrayUtil.arr(10);
		util.ArrayUtil.printArr(arr);
		radixSort(arr);
		util.ArrayUtil.printArr(arr);
	}

	public static void radixSort(int[] arr) {
		//找出数组中的最大值
		int max = maxOf(arr);
		int d = 1; //入桶依据位初始为1
		int dNum = 1; //最大数据的位数
		while(max/10 != 0) {
			dNum++;
			max/=10;
		}
		while(d <= dNum) {
			BucketSort(arr, d++);
		}
	}

	public static void BucketSort(int[] arr, int d) {
		//入桶
		for(int i = 0; i < arr.length; i++) {
			inputBucket(arr[i], d);
		}

		//出桶
		int k = 0;//记录数组下标，回填数据
		for(int i = 0; i < bucket.length; i++) {
			//如果桶内不为空，从小到大回填到数组
			if(!bucket[i].isEmpty()) {
				for(int j = 0; j < bucket[i].size(); j++) {
					arr[k++] = bucket[i].get(j);
				}
			}
		}

		//清空桶
		for(ArrayList<Integer> b : bucket) {
			b.clear();
		}

	}

	public static void inputBucket(int value, int d) {
		int pos = (int) (value / Math.pow(10, d - 1) % 10);
		switch (pos) {
		case 0:
			bucket[0].add(value);
			break;
		case 1:
			bucket[1].add(value);
			break;
		case 2:
			bucket[2].add(value);
			break;
		case 3:
			bucket[3].add(value);
			break;
		case 4:
			bucket[4].add(value);
			break;
		case 5:
			bucket[5].add(value);
			break;
		case 6:
			bucket[6].add(value);
			break;
		case 7:
			bucket[7].add(value);
			break;
		case 8:
			bucket[8].add(value);
			break;
		default:
			bucket[9].add(value);
			break;
		}
	}

	//找出数组中最大的数值
	public static int maxOf(int[] arr) {
		int max = arr[0];
		for(int i = 1; i < arr.length; i++) {
			if(max < arr[i]) {
				max = arr[i];
			}
		}
		return max;
	}
}

程序运行结果：

1
2
4 49 56 16 67 36 3 27 88 89 
3 4 16 27 36 49 56 67 88 89

算法分析：

时间复杂度： 假设最大的数有k位，就要进行k次入桶和回填，每次入桶和回填是线性的，所以整体复杂度为kN,其中k为最大数的10进制位数

空间复杂度：桶是10个，10个桶里面存n个元素，这些空间都是额外开辟的，所以额外的空间是N+k，k是进制

肯定是非原址排序

稳定性：假设有相等的元素，它们会次第入桶，次第回数组，不会交叉，所以是稳定的

坚持原创技术分享，您的支持将鼓励我继续创作！