选择排序

发表于 | 分类于

选择排序的基本思想是：每一趟在剩余未排序的若干记录中选取关键字最小的（也可以是最大的，本文中均考虑排升序）记录作为有序序列中下一个记录。

如第i趟选择排序就是在n-i+1个记录中选取关键字最小的记录作为有序序列中第i个记录。

这样，整个序列共需要n-1趟排序。

简单的选择排序

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法。 选择排序的思想：选出最小的一个和第一个位置交换，选出其次小的和第二个位置交换 …… 直到从第N个和第N-1个元素中选出最小的放在第N-1个位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
data_set = [12, 1, 24, 45, 61, 21, 6, 32]  # 8

data_set_smellest = 0 # 列表中最小的值，默认是第一个，后边通过比较进行更新

for j in range(len(data_set)):
    for i in range(j, len(data_set)): # 迭代 j 到 lenght(8) 之间的数字
        if(data_set[i]<data_set[data_set_smellest]):
            data_set_smellest = i
    else:
        print("Smellest num is :", data_set[data_set_smellest])
        tmp = data_set[j]
        data_set[j] = data_set[data_set_smellest]
        data_set[data_set_smellest] = tmp

    print(data_set)
print("----------------------")

print(data_set)

输出结果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Smellest num is : 1
[1, 12, 24, 45, 61, 21, 6, 32]
Smellest num is : 6
[1, 6, 24, 45, 61, 21, 12, 32]
Smellest num is : 12
[1, 6, 12, 45, 61, 21, 24, 32]
Smellest num is : 21
[1, 6, 12, 21, 61, 45, 24, 32]
Smellest num is : 24
[1, 6, 12, 21, 24, 45, 61, 32]
Smellest num is : 32
[1, 6, 12, 21, 24, 32, 61, 45]
Smellest num is : 45
[1, 6, 12, 21, 24, 32, 45, 61]
Smellest num is : 61
[1, 6, 12, 21, 24, 32, 45, 61]
----------------------
[1, 6, 12, 21, 24, 32, 45, 61]

容易看出，简单选择排序中，所需进行记录移动的操作次数较少，其最小值为“0”，最大值为3(n-1)。

　　然而，无论记录的初始序列如何，所需进行的关键字间的比较次数相同，均为n(n-1)/2，因此，总的时间复杂度为O(n²)。

　　因为简单选择排序没有利用上次选择时比较的结果，所以造成了比较次数多，速度慢。如果能够加以改进，将会提高排序的速度，所以出现了后面的树形选择排序和堆排序。

树形选择排序

树形选择排序（Tree Selection Sort），又称锦标赛排序（Tournament Sort），是一种按照锦标赛思想进行选择排序的方法。

为了减少简单选择排序，我们利用前n-1次比较信息，减少下次选择。类似于锦标赛。根据锦标赛传递关系。亚军只能从被冠军击败的人中选出。

selectionSort1.png

实际算法中，我们把需要比较的记录全部作为叶子，然后从叶子开始两两比较，从底向上最后形成一棵完全二叉树。在我们选择出最小关键字后，根据关系的传递，只需要将最小关键字的叶子节点改成无穷大，重新从底到上比较一次就能够得出次小关键字。

selectionSort.png

　　首先对n个记录的关键字进行两两比较，然后在其中[n/2]（向上取整）个较小者之间再进行两两比较，如此重复，直至选出最小关键字的记录为止。

这个过程可以用一棵有n个叶子结点的完全二叉树表示。如图中的二叉树表示从8个关键字中选出最小关键字的过程：

selectionSort2.png

个叶子结点中依次存放排序之前的8个关键字，每个非终端结点中的关键字均等于其左、右孩子结点中较小的那个关键字，则根结点中的关键字为叶子结点中的最小关键字。

　　在输出最小关键字之后，根据关系的可传递性，欲选出次小关键字，仅需将叶子结点中的最小关键字（13）改为“最大值”，然后从该叶子结点开始，和其左右兄弟的关键字进行比较，修改从叶子结点到根结点的路径上各结点的关键字，则根结点的关键字即为次小值。

selectionSort3.png

同理，可依次选出从小到大的所有关键字。

　　由于含有n个叶子结点的完全二叉树的深度为[log2n]+1，则在树形选择排序中，除了最小关键字以外，每选择一个次小关键字仅需进行[log2n]次比较，因此，它的时间复杂度为O(nlogn)。

　　但是，这种排序方法也有一些缺点，比如辅助存储空间较多，并且需要和“最大值”进行多余的比较。

　　为了弥补，另一种选择排序被提出——堆排序。 　　

堆排序（Heap Sort）

参考书目：《java程序语言程序设计（进阶篇）》《数据结构与算法分析——C语言描述》

堆排序使用的是二叉堆。它首先将所有的元素添加到一个堆上，然后不断移除最大的元素来获得一个排好序的线性表。（也可以用小顶堆）

二叉堆（binary heap）是一颗具有一下属性的二叉树：

  • 形状属性：它是一颗完全二叉树
  • 堆属性：每个结点大于或等于它的任意一个孩子

B站有一个很好的视频用来理解：

https://www.bilibili.com/video/av18980178?from=search&seid=9854766405077394358

书中有一段我感觉很好，摘抄下来：

“避免使用第二个数组的聪明做法是利用这样的事实：在每次DeleteMin之后，堆缩小了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
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

public class HeapSort {
	public static void main(String[] args) {
		int[] array = new int[] { 2, 1, 4, 3, 6, 5, 8, 7 };
		// 接下来就是排序的主体逻辑
		sort(array);
		System.out.println(Arrays.toString(array));
	}
 
	/**
	 * 
	 * @description 本方法只有一个参数，那就是待排序的array
	 * @author yuzhao.yang
	 * @param
	 * @return
	 * @time 2018年3月9日 下午2:24:45
	 */
	public static void sort(int[] array) {
		// 按照完全二叉树的特点，从最后一个非叶子节点开始，对于整棵树进行大根堆的调整
		// 也就是说，是按照自下而上，每一层都是自右向左来进行调整的
		// 注意，这里元素的索引是从0开始的
		// 另一件需要注意的事情，这里的建堆，是用堆调整的方式来做的
		// 堆调整的逻辑在建堆和后续排序过程中复用的
		for (int i = array.length / 2 - 1; i >= 0; i--) {
			adjustHeap(array, i, array.length);
		}
 
		// 上述逻辑，建堆结束
		// 下面，开始排序逻辑
		for (int j = array.length - 1; j > 0; j--) {
			// 元素交换
			// 说是交换，其实质就是把大顶堆的根元素，放到数组的最后；换句话说，就是每一次的堆调整之后，都会有一个元素到达自己的最终位置
			swap(array, 0, j);
			// 元素交换之后，毫无疑问，最后一个元素无需再考虑排序问题了。
			// 接下来我们需要排序的，就是已经去掉了部分元素的堆了，这也是为什么此方法放在循环里的原因
			// 而这里，实质上是自上而下，自左向右进行调整的
			adjustHeap(array, 0, j);
		}
	}
 
	/**
	 * 
	 * @description 这里，是整个堆排序最关键的地方，正是因为把这个方法抽取出来，才更好理解了堆排序的精髓，会尽可能仔细讲解
	 * @author yuzhao.yang
	 * @param
	 * @return
	 * @time 2018年3月9日 下午2:54:38
	 */
	public static void adjustHeap(int[] array, int i, int length) {
		// 先把当前元素取出来，因为当前元素可能要一直移动
		int temp = array[i];
		// 可以参照sort中的调用逻辑，在堆建成，且完成第一次交换之后，实质上i=0；也就是说，是从根所在的最小子树开始调整的
		// 接下来的讲解，都是按照i的初始值为0来讲述的
		// 这一段很好理解，如果i=0；则k=1；k+1=2
		// 实质上，就是根节点和其左右子节点记性比较，让k指向这个不超过三个节点的子树中最大的值
		// 这里，必须要说下为什么k值是跳跃性的。
		// 首先，举个例子，如果a[0] > a[1]&&a[0]>a[2],说明0,1,2这棵树不需要调整，那么，下一步该到哪个节点了呢？肯定是a[1]所在的子树了，
		// 也就是说，是以本节点的左子节点为根的那棵小的子树
		// 而如果a[0}<a[2]呢，那就调整a[0]和a[2]的位置，然后继续调整以a[2]为根节点的那棵子树，而且肯定是从左子树开始调整的
		// 所以，这里面的用意就在于，自上而下，自左向右一点点调整整棵树的部分，直到每一颗小子树都满足大根堆的规律为止
		for (int k = 2 * i + 1; k < length; k = 2 * k + 1) {
			// 让k先指向子节点中最大的节点
			if (k + 1 < length && array[k] < array[k + 1]) {
				k++;
			}
 
			// 如果发现子节点更大，则进行值的交换
			if (array[k] > temp) {
				swap(array, i, k);
				// 下面就是非常关键的一步了
				// 如果子节点更换了，那么，以子节点为根的子树会不会受到影响呢？
				// 所以，循环对子节点所在的树继续进行判断
				i = k;
				// 如果不用交换，那么，就直接终止循环了
			} else {
				break;
			}
		}
	}
 
	/**
	 * 交换元素
	 * 
	 * @param arr
	 * @param a
	 *            元素的下标
	 * @param b
	 *            元素的下标
	 */
	public static void swap(int[] arr, int a, int b) {
		int temp = arr[a];
		arr[a] = arr[b];
		arr[b] = temp;
	}
}

python的：

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
class SQList:
    def __init__(self, lis=None):
        self.r = lis

    def swap(self, i, j):
        """定义一个交换元素的方法，方便后面调用。"""
        temp = self.r[i]
        self.r[i] = self.r[j]
        self.r[j] = temp

    def heap_sort(self):
        length = len(self.r)
        i = int(length/2)
        # 将原始序列构造成一个大顶堆
        # 遍历从中间开始，到0结束，其实这些是堆的分支节点。
        while i >= 0:
            self.heap_adjust(i, length-1)
            i -= 1
        # 逆序遍历整个序列，不断取出根节点的值，完成实际的排序。
        j = length-1
        while j > 0:
            # 将当前根节点，也就是列表最开头，下标为0的值，交换到最后面j处
            self.swap(0, j)
            # 将发生变化的序列重新构造成大顶堆
            self.heap_adjust(0, j-1)
            j -= 1

    def heap_adjust(self, s, m):
        """核心的大顶堆构造方法，维持序列的堆结构。"""
        lis = self.r
        temp = lis[s]
        i = 2*s
        while i <= m:
            if i < m and lis[i] < lis[i+1]:
                i += 1
            if temp >= lis[i]:
                break
            lis[s] = lis[i]
            s = i
            i *= 2
        lis[s] = temp

    def __str__(self):
        ret = ""
        for i in self.r:
            ret += " %s" % i
        return ret

if __name__ == '__main__':
    sqlist = SQList([4, 1, 7, 3, 8, 5, 9, 2, 6, 0, 123, 22])
    sqlist.heap_sort()
    print(sqlist)

参考博客：

简单选择排序 Selection Sort 和树形选择排序 Tree Selection Sort

选择排序之树形选择排序（TreeSelectionSort）

Python常用算法学习

基于python的七种经典排序算法

白话讲排序系列（六） 堆排序（绝对让你明白堆排序！）