排序(1) 选择排序

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

选择排序是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。 遍历数组，遍历到i时，a0,a1,…,ai-1是已经排好序的，然后从i到n选择出最小的，记录下位置，如果不是第i个，则和第i个元素交换。此时第i个元素可能会排到相等元素之后，造成排序的不稳定。

选择排序（最小元素）

分析

假设要按照升序排列一个数列 {2, 9, 5, 4, 8, 1, 6}。
选择排序法首先找到数列中最小的数，然后将它和第一个元素交换。接下来，在剩下的数中找到最小数，将它和第二个元素交换，以此类推，直到数列中仅剩一个数为止。

可以在纸上模拟一下具体选择排序过程。

开始编写第一次迭代的代码，找出数列中的最大数，将其与最后一个元素互换，然后观察第二次迭代与第一次的不同之处，接着是第三次，以此类推。通过这样的观察可以写出推广到所有迭代的循环。

解决方案伪代码
1
2
3
4
5
6
7
for (int i = 0; i < arr.length - 1; i++) {
	select the smallest element in arr[i ... arr.length-1];
	swap the smallest with arr[i], if necessary;

	// arr[i] is in its correct position
	// the next iteration applies on arr[i+1 ... arr.length-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
public class SelectionSort {
	//  选择排序
    public static void selectionSort(int[] arr) {
        if (arr == null || arr.length < = 1) {
            return;
        }

        int currentMin;
        int currentMinIndex;

        for (int i = 0; i < arr.length - 1; i++) {
            //  找到最小值和最小值下标位置，在范围arr[i  ... arr.length-1]
            currentMin = arr[i];
            currentMinIndex = i;

            for (int j = i + 1; j < arr.length; j++) {
                if (currentMin > arr[j]) {
                    currentMin = arr[j];
                    currentMindIndex = j;
                }
            }

            if (currentMinIndex != i) {
                arr[currentMinIndex] = arr[i];
                arr[i] = currentMin;
            }
        }
    }

    public static void main(String[] args) {
        int[] list = {2, 32, 3, 34, 45, 8, 89, 20, 23};        
        selectionSort(list);

        for (int i: list)
            System.out.print(i + " ");
    }
}

选择排序（最大值）

上面的选择排序法重复地在当前数组中找到最小值，然后将这个最小值与该数组中的第一个数进行交换。
修改成：
重复地选取当前数组中最大值，然后将这个最大值与该数组中的最后一个数进行交换，直到数组中的第一个元素。

选择最大值的选择排序
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
public class SelectionSort{
	// 选择排序
    public static void selectionSort(int[] arr) {
        int currentMax;
        int currentMaxIndex;

        for (int i = list.length - 1; i >= 0; i--) {
            currentMax = list[i];
            currentMaxIndex = i;

            for (int j = i - 1; j >= 0; j--) {
                if (currentMax < arr[j]) {
                    currentMax = arr[j];
                    currentMaxIndex = j;
                }
            }

            if (currentMaxIndex != i) {
                arr[currentMaxIndex] = arr[i];
                arr[i] = currentMax;
            }
        }
    }

    // ========测试用例略=========

}

算法复杂度

选择排序复杂度：
时间复杂度（平均）： O(n^2)
时间复杂度（最坏）： O(n^2)
时间复杂度（最好）： O(n^2)

空间复杂度： O(1)

选择排序稳定性

选择排序是不稳定的算法。

算法稳定性定义

在待排序的数据中，存在多个相同的数据，经过排序之后，他们的对相对顺序依旧保持不变，实际上就是说 array[i] = array[j], i < j
就是array[i]在array[j]之前，那么经过排序之后array[i]依旧在array[j]之前，那么这个排序算法稳定，否则，这个排序算法不稳定

也就是说，只要能举出一个反例来说明这个算法不稳定，那么这个算法就是不稳定的

针对选择排序算法，如下反例：
数列 {5, 8, 5, 2, 9}

这个在执行选择排序的时候，第一遍，肯定会将array[0]=5，交换到2所在的位置:
也就是 {2, 8, 5, 5, 9}

那么很显然，之后的排序我们就会发现，array[2]中的5会出现在原先的array[0]之前，所以选择排序不是一个稳定的排序。

0%