数据结构-选择排序

选择排序算法理解与实现

选择排序

选择排序的基本思想,每一趟从待排序的记录中选出关键字最小(或最大)的记录,顺序放在已排好序的记录序列的最后,直到全部记录排序完毕。

直接选择排序

基本思想

直接选择排序是指从待排序的记录序列中选择关键码最小(或最大)的记录并将它与序列中的第一个记录交换位置;然后从不包含第一个位置的记录序列中选择关键码最小(或最大)的记录并将它与序列中第二个记录交换位置;如此重复,直到序列中只剩下一个记录为止。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int[] selectSort(int[] data){
int k,temp;
for(int i=0;i<data.length;i++){
k=i;
for(int j=i+1;j<data.length;j++){
if(data[j]<data[k]){
k = j; //始终保持k = j为最小值
}
}
if(k!=i){
temp = data[k];
data[k] = data[i];
data[i] = temp;
}
}
return data;
}

时间复杂度

在直接选择排序中,第一次排序要进行n-1次比较,第二次排序要进行n-2次比较,…,第n-1次排序要进行1次比较,所以总的比较次数是n(n-1)/2,在各次排序时,记录的移动次数最好0次,最坏为3次,所以总的最坏为3(n-1)。因此,其复杂度为O(n2)。

堆排序

堆排序是在直接选择排序法的基础上借助于完全二叉树结构而形成的一种排序方法,堆排序是完全二叉树的顺序存储结构的应用。在直接选择排序中每次排序中除了找到当前关键字最小的记录外,还产生了许多比较结果的信息,这些信息在直接选择排序算法中会被直接忽略,但在堆排序中,这些信息会被保存下来。

基本思想

关于堆、最大堆、最小堆的概念这里就不做介绍了,不懂的可自行百度。这里说一下堆排序的基本思想:设有n个记录,首先将这n个记录按关键码建成堆,将堆顶记录输出,得到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
package com.x1aolin.test;
public class Main{
//创建堆
public void createHeap(int[] data,int low,int high){
if((low<high)&&(high<data.length)){
int j=0;
int k=0;
int tmp = 0;
for(int i = high/2;i>=low;i--){
tmp = data[i];
k = i;
j = 2 * k + 1;
//从上面换下来的顶点要继续向下看,直到最后
while(j<=high){
//选择当前结点的两个子节点中的大值
if((j<high)&&(j+1<=high)&&(data[j]<data[j+1])){
j++;
}
if(tmp<data[j]){
data[k] = data[j];
k = j;
j = 2 * k + 1;
}
else break;
}
data[k] = tmp;
}
}
}
//堆排序算法
public int[] heapSort(int[] data){
int tmp = 0;
createHeap(data,0,data.length-1);
//这样能够保证从小到大的顺序
for(int i= data.length - 1;i>0;i--){
tmp = data[0];
data[0] = data[i];
data[i] = tmp;
createHeap(data,0,i-1);
}
return data;
}
public static void main(String[] args){
Main a = new Main();
int data[] = {1,5,9,7,4,6,3,2,8};
a.heapSort(data);
for(int i=0;i<data.length;i++)
System.out.print(data[i]+" ");
}
}

时间复杂度

对深度为k的堆,“筛选”所需进行的关键字比较的次数之多为2(k-1);

n个关键字,建成深度为 h=log2 + 1 的堆,所需进行的关键字比较的次数至多为4n

调整“堆顶”n-1次,共进行的关键字比较的次数不超过 2*(log2(n-1) + log2(n-2) + … + log22) < 2n(log2n)。

因此,堆排序的最坏的情况下,时间复杂度为O(nlog2n),所以在记录较少的情况下不适用。

您的每一份支持将鼓励我继续创作!
-------------本文结束感谢您的阅读-------------