简单选择排序与堆排序——Java语言描述

发表于 | 分类于 | 阅读次数

选择排序的主要思想是每一趟从待排序列中选取一个关键字值最小的记录，也即第一趟从n个记录中选取关键字值最小的记录，在第二趟中，从剩下的n-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
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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
import java.util.Arrays;

public class SelectionSort {

	/**
	 * 直接选择排序：又称简单选择排序。在第一趟中，从n个记录中找出关键字值最小的记录与第一个记录交换；在第二趟中，
	 * 			从第二个记录开始的n-1个记录中在选出关键字值最小的记录与第二个记录交换；以此
	 * 			类推，在第i趟中，从第i个记录开始的n-i+1个记录中选出关键字值最小的记录与第i个
	 * 			记录交换，直到整个序列按关键字值有序
	 * 空间复杂度为O(1)
	 * 时间复杂度为O(n^2)
	 * 算法稳定性：简单选择排序是一种不稳定的排序算法
	 * */
	/**
	 * 主要步骤：
	 * 	1.设置i的初始值为0；
	 * 	2.当i<n-1时，重复下列步骤；
	 * 		2.1.在无序子序列{s[i+1],...s[n-1]}中选出一个关键字值最小的记录s[min];
	 * 		2.2.若s[min]不是s[i]，（min != i）,则交换s[i]和s[min]的位置，否则不进行任何交换;
	 * 		2.3.将i的值加1.
	 * */
	
	public static void StraightSelectionSort(int straight[]) {
		int temp;
		int i,j;
		for(i=0;i<straight.length-1;i++){
			int min = i;  //设第i条记录的关键字值最小
			for(j=i+1;j<straight.length;j++){ 	//在子序列中选择关键字值最小的记录
				if(straight[j]<straight[min]){
					min=j;	//记住关键字值最小的下标
				}
			}
			if(min != i){	//将本趟关键字值最小的记录与第i条记录交换
				temp=straight[i];
				straight[i]=straight[min];
				straight[min]=temp;
			}
//			else{
//				continue;
//			}
			System.out.println("第"+(i+1)+"趟: "+Arrays.toString(straight));
		}
	}
	
	/**
	 * 堆排序：对一组待排序记录的关键字，首先按堆的定义排成一个序列（即建立初始堆，大根堆或小根堆），
	 * 		从而可以输出堆顶的最大关键字（对于大根堆而言）然后将剩余的关键字在调整成新堆，便得到次大的关键字，
	 * 		如此反复，直到全部关键字排成有序序列为止。
	 * 空间复杂度为O(1)
	 * 时间复杂度为O(nlogn)
	 * 算法稳定性：堆排序算法是一种不稳定的排序算法
	 * */
	/**
	 * 调整堆主要步骤：待调整成堆的完全二叉树存放在h[low...high]
	 * 	1.设置初始值temp=h[low]
	 * 	2.当i<=high时重复下列操作
	 * 		2.1.若i<high且h[i]>h[i+1]，则i++;
	 * 		2.2.若temp>h[i]则h[low]=h[i],low=i;
	 * 	3.h[low]=temp.
	 * 
	 * */
	
	/** 筛选法将一个数组中的元素调整成大根堆 */
	public static void HeapAdjust(int heap[],int low,int high) {
		int temp=heap[low];
		int i;
		for(i=2*low+1;i<=high;i=i*2+1){  //沿值较大的孩子结点向下筛选
			if(i<high && heap[i]<heap[i+1]){ //i是值较大的元素的下标
				i++;
			}
			if(!(temp<heap[i])){
				break;
			}
			heap[low]=heap[i];
			low=i;	//用low记录待插入元素的下标
		}
		heap[low]=temp;		
		System.out.println(Arrays.toString(heap));
	}
	/** 筛选法将一个数组中的元素调整成小根堆 */
	public static void HeapAdjust2(int heap[],int low,int high) {
		int temp=heap[low];
		int i;
		for(i=2*low+1;i<=high;i=i*2+1){  //沿值较小的孩子结点向下筛选
			if(i<high && heap[i]>heap[i+1]){ //i是值较小的元素的下标
				i++;
			}
			if(temp>heap[i]){
				heap[low]=heap[i];
				low=i;	//用low记录待插入元素的下标
			}
			else{
				i=high+2;
			}
		}
		heap[low]=temp;		
		System.out.println(Arrays.toString(heap));
	}
	
	/**
	 * 堆排序主要步骤：
	 * 	1.将待排序记录{h[0],h[1],...,h[n-1]}建成一个完全二叉树；
	 * 	2.将下标为[n/2]-1的记录作为开始调整的子树的根节点
	 * 	3.找出此结点的两个孩子结点中的关键字值较小者，将其与父结点比较，若父结点的关键字值大则交换
	 * 	  然后以交换后的子结点作为新的父结点，重复此步骤，直到没有子结点为止。
	 * 	4.以步骤3中原来的父结点所在的位置向前推进一个位置，作为新的调整的子树的根结点。继续重复步骤3直到调整到树根
	 * 	5.堆建成后，将树根与二叉树的最后一个结点交换后，再将最后一个结点输出（即输出的是原本的树根）；
	 * 	 然后比较根结点的两个子结点，若做子节点的关键字较小，则调整左子树；反之，调整右子树。使它成堆；
	 * 	6.重复步骤5直到二叉树仅剩一个结点为止。
	 * */
	
	/** 堆排序算法 **/
	public static void HeapSort(int heap[]) {
		int len=heap.length;
		int temp,i;
		for(i=len/2-1; i>=0; i--){	//创建堆
			HeapAdjust(heap, i, len-1);
		}
		for(i=len-1; i>0; i--){ //将堆顶元素heap[0]与序列的最后元素heap[i]交换
			temp = heap[0];
			heap[0] = heap[i];
			heap[i] = temp;
			HeapAdjust(heap, 0, i-1); //待排元素减1,剩余元素重新调整为大根堆
		}
		
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int straight[]={35,57,48,5,29,87,17,35,66,92};
		int heap[]={33,25,46,13,58,95,18,63,78,80};
		StraightSelectionSort(straight);
		System.out.println("--------------------分割线--------------------");
		HeapSort(heap);
	}

}

测试结果（大根堆）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
第1趟: [5, 57, 48, 35, 29, 87, 17, 35, 66, 92]
第2趟: [5, 17, 48, 35, 29, 87, 57, 35, 66, 92]
第3趟: [5, 17, 29, 35, 48, 87, 57, 35, 66, 92]
第4趟: [5, 17, 29, 35, 48, 87, 57, 35, 66, 92]
第5趟: [5, 17, 29, 35, 35, 87, 57, 48, 66, 92]
第6趟: [5, 17, 29, 35, 35, 48, 57, 87, 66, 92]
第7趟: [5, 17, 29, 35, 35, 48, 57, 87, 66, 92]
第8趟: [5, 17, 29, 35, 35, 48, 57, 66, 87, 92]
第9趟: [5, 17, 29, 35, 35, 48, 57, 66, 87, 92]
--------------------分割线--------------------
[33, 25, 46, 13, 80, 95, 18, 63, 78, 58]
[33, 25, 46, 78, 80, 95, 18, 63, 13, 58]
[33, 25, 95, 78, 80, 46, 18, 63, 13, 58]
[33, 80, 95, 78, 58, 46, 18, 63, 13, 25]
[95, 80, 46, 78, 58, 33, 18, 63, 13, 25]
[80, 78, 46, 63, 58, 33, 18, 25, 13, 95]
[78, 63, 46, 25, 58, 33, 18, 13, 80, 95]
[63, 58, 46, 25, 13, 33, 18, 78, 80, 95]
[58, 25, 46, 18, 13, 33, 63, 78, 80, 95]
[46, 25, 33, 18, 13, 58, 63, 78, 80, 95]
[33, 25, 13, 18, 46, 58, 63, 78, 80, 95]
[25, 18, 13, 33, 46, 58, 63, 78, 80, 95]
[18, 13, 25, 33, 46, 58, 63, 78, 80, 95]
[13, 18, 25, 33, 46, 58, 63, 78, 80, 95]