作者：海鹰
本人才疏学浅，若有纰漏，虚心请教
本文讲述选择排序算法
版权所有，未经允许，请勿随意转载。
选择排序（Selection Sort）的基本思想是：每一趟在n-i+1（i=1,2,…,n-1）个记录中选择关键字最小的记录作为有序序列中第i个记录。
简单选择排序（Simple Selection Sort）
示例代码 [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/**
*
* @param nums
* @param begin
* @return
*/
public int selectMinLoc(int[] nums, int begin){
int index=begin, min=nums[begin];
for( int i=begin+1; i<nums.length; i++ ){
if( min > nums[i] ){
index = i;
min = nums[i];
}
}
return index;
}
/**
* 简单选择排序
* @param nums
* @return
*/
public int[] simpleSelectionSort(int[] nums){
for( int i=0, j, temple; i<nums.length; i++ ){
j = selectMinLoc(nums, i);
temple = nums[i];
nums[i] = nums[j];
nums[j] = temple;
}
return nums;
}
从上述代码可见，选择排序的主要操作是进行关键字间的比较，因此，改进简单选择排序应从如何减少“比较”出发考虑。
显然，在n个关键字中选出最小值，至少进行n-1次比较，然而，继续在剩余的n-1个关键字中选择次小值就并非一定要进行n-2次比较，若能利用前n-1次比较所得信息，则可减少以后各趟选择排序中所用的比较次数。
树形选择排序（Tree Selection Sort），又称锦标赛排序（Tournament Sort）
一种按照锦标赛的思想进行选择排序的方法。首先对n个记录的关键字进行两两比较，然后在n/2个较小者之间再进行两两比较，如此重复，直至选出最小关键字的记录为止。这个过程可用一棵有n个叶子结点的完全二叉树表示。
思考过程如下：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初始化过程，找出最小值
13
_____________|____________
| |
38 13
_______|______ _______|______
| | | |
38 65 13 27
____|____ ____|____ ____|____ ____|____
| | | | | | | |
49 38 65 97 76 13 27 49
输出13，二叉树调整如下，将13修改为∞（无穷大），找到次最小值
27
_____________|____________
| |
38 27
_______|______ _______|______
| | | |
38 65 76 27
____|____ ____|____ ____|____ ____|____
| | | | | | | |
49 38 65 97 76 ∞ 27 49
输出27，二叉树调整如下，将27修改为∞（无穷大）
38
_____________|____________
| |
38 49
_______|______ _______|______
| | | |
38 65 76 49
____|____ ____|____ ____|____ ____|____
| | | | | | | |
49 38 65 97 76 ∞ ∞ 49
以此类推
这种排序方法尚有辅助存储空间较多、“最大值”进行多余的比较等缺点。
堆排序（Heap Sort）
实现堆排序需要解决两个问题：
（1）如何由一个无序序列建成一个堆？
从一个无序序列建堆的过程就是一个反复“筛选”的过程。若将此序列看成是一个完全二叉树，则最后一个非终端结点是第n/2个元素，由此“筛选”只需从第n/2个元素开始。
（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/**
* 堆调整
* @param nums
* @param begin
* @param end
*/
public void heapAdjust(int[] nums, int begin, int end){
int temple = nums[begin];
for(int i=begin*2+1; i<end; i=2*i+1){
if( i<end-1 && nums[i] > nums[i+1] )
i++;
if( temple < nums[i] )
break;
nums[begin] = nums[i];
begin = i;
}
nums[begin] = temple;
}
/**
* 堆排序
* @param nums
* @return
*/
public int[] heapSort(int[] nums){
int[] result = new int[nums.length];
for( int i=nums.length/2-1; i>=0; i-- ){
heapAdjust(nums, i, nums.length);
}
for( int i=nums.length-1,j=0; i>=0; i--,j++ ){
result[j] = nums[0];
nums[0] = nums[i];
heapAdjust(nums, 0, i);
}
return result;
}
堆排序方法对记录较少的文件并不值得提倡，但对n较大的文件还是很有效的。因为其运行时间主要耗费在建初始堆时进行的反复“筛选”上。