CS2L13——选择排序

选择排序

选择排序（selection sort）的工作原理非常简单：开启一个循环，每轮从未排序区间选择最小的元素，将其放到已排序区间的末尾。

设数组的长度为 nn，选择排序的步骤为：

  1. 初始状态下，所有元素未排序，即未排序（索引）区间为 [0,n−1][0,n−1] 。
  2. 选取区间 [0,n−1][0,n−1] 中的最小元素，将其与索引 0 处的元素交换。完成后，数组前 1 个元素已排序。
  3. 选取区间 [1,n−1][1,n−1] 中的最小元素，将其与索引 1 处的元素交换。完成后，数组前 2 个元素已排序。
  4. 以此类推。经过 n−1n−1 轮选择与交换后，数组前 n−1n−1 个元素已排序。
  5. 仅剩的一个元素必定是最大元素，无须排序，因此数组排序完成。

步骤简记为：新建中间变量、依次比较、找出极值(最大或最小)、放入目标位置、比较 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
static void SelectionSort(int[] arr)
{
    for (int m = 0; m < arr.Length; m++)
    {
        //第一步 申明一个中间商 来记录索引
        //每一轮开始默认第一个都是极值
        int index = 0;
        //第二步 依次比较 -m的目的是排除上一轮已经放好的位置
        for (int n = 1; n < arr.Length - m; n++)
        {
            //第三步 找出极值
            if (arr[index] < arr[n])
            {
                index = n;
            }
        }
        //第四步 放入目标位置 Length - 1 - 轮数 如果当前所在极值位置就是目标位置就没必要交换
        if (index != arr.Length - 1)
        {
            int temp = arr[index];
            arr[index] = arr[arr.Length - 1 - m];
            arr[arr.Length - 1 - m] = temp;
        }
        //第五步 复制m轮
    }
}

static void Main(string[] args)
{
    int[] arr = new int[] { 8, 7, 1, 5, 4, 2, 6, 3, 9 };
    SelectionSort(arr);
    for (int i = 0; i < arr.Length; i++)
    {
        Console.Write(arr[i] + " ");
    }
}

输出：

1
1 2 3 4 5 6 7 8 9