简单选择排序

简单选择排序：在待排序的数据中选出最大（小）的元素放在其最终的位置。

  • 时间复杂度=O(n2)，空间复杂度=O(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
internal class Program
{
    private static void Main(string[] args)
    {
        int[] arr = { 5, 7, 3, 8, 6, 9 };
        Console.WriteLine("未排序前的数组：");
        for (int i = 0; i < arr.Length; i++)
        {
            Console.Write(arr[i] + " ");
        }
        Console.WriteLine();
        selection_sort(arr);
        Console.WriteLine("排序后的数组：");
        for (int i = 0; i < arr.Length; i++)
        {
            Console.Write(arr[i] + " ");
        }
    }

    private static void selection_sort(int[] arr)
    {
        int length = arr.Length;
        int i, j, min;
        for (i = 0; i < length - 1; i++)
        {
            min = i; // 把第一个元素假设为最小
            for (j = i + 1; j < length; j++)
            {
                // 从第二个元素开始遍历到最后一个
                if (arr[j] < arr[min])
                {
                    // 如果期间出现小于最小元素的值，则交换位置
                    min = j;
                }
            }
            if (min != i)
            {
                int temp = arr[i];
                arr[i] = arr[min];
                arr[min] = temp;
            }
        }
    }
}

输出：

未排序前的数组：
5 7 3 8 6 9
排序后的数组：
3 5 6 7 8 9

堆排序

堆排序：堆的是指就是满足二叉树中任一非叶子结点均小于（大于）它的孩子结点的完全二叉树。

  • 时间复杂度=O(nlog2n)，空间复杂度=O(1)。不稳定排序。
  • 小根堆：若n个元素的序列{a1a2…an}满足ai ≤ a2i和ai ≤ a2i+1。
  • 大根堆：若n个元素的序列{a1a2…an}满足ai ≥ a2i和ai ≥ a2i+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
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
96
97
98
99
100
101
102
103
104
105
106
107
internal class Program
{
    private static void Main(string[] args)
    {
        int[] arr = { 5, 7, 3, 8, 6, 9 };
        Console.WriteLine("未排序前的数组：");
        for (int i = 0; i < arr.Length; i++)
        {
            Console.Write(arr[i] + " ");
        }
        Console.WriteLine();
        //big_heap_sort(arr);
        small_heap_sort(arr);
        Console.WriteLine("排序后的数组：");
        for (int i = 0; i < arr.Length; i++)
        {
            Console.Write(arr[i] + " ");
        }
    }

    private static void big_heap_sort(int[] arr)
    {
        // 从树的第arr.Length / 2 - 1个结点开始建立大根堆
        for (int i = arr.Length / 2 - 1; i >= 0; i--)
        {
            big_heap_adjust(arr, i, arr.Length);
        }
        for (int i = arr.Length - 1; i > 0; i--)
        {
            // 把根结点与最后一个结点进行交换，把最大值放到最后
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            // 交换后，以根结点开始，重新调整为大根堆
            big_heap_adjust(arr, 0, i);
        }
    }

    // 建立大根堆：升序，最大值（根结点）与最后一个结点交换位置
    private static void big_heap_adjust(int[] arr, int parent, int length)
    {
        // 临时存储根结点数值
        int temp = arr[parent];
        // 找到根结点的左孩子
        int child = parent * 2 + 1;
        // 孩子结点不大于数组长度
        while (child < length)
        {
            // 如果右孩子在数组长度内 && 右孩子 > 左孩子
            if (child + 1 < length && arr[child + 1] > arr[child])
            {
                // 设置为右孩子
                child++;
            }
            // 如果根结点 > 孩子结点
            if (temp > arr[child])
            {
                break; // 退出+
            }
            // 否则，根结点与最大的孩子结点交换位置
            arr[parent] = arr[child];
            // 根结点设置为交换后的孩子结点下标
            parent = child;
            // 找到新的左孩子下标
            child = parent * 2 + 1;
        }
        // 此时parent已为最小的孩子结点，把temp放到此位置上
        arr[parent] = temp;
    }

    private static void small_heap_sort(int[] arr)
    {
        for (int i = arr.Length / 2 - 1; i >= 0; i--)
        {
            small_heap_sort(arr, i, arr.Length);
        }
        for (int i = arr.Length - 1; i >= 0; i--)
        {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            small_heap_sort(arr, 0, i);
        }
    }

    // 小根堆:降序，最小值（根结点）与最后一个结点交换位置
    private static void small_heap_sort(int[] arr, int parent, int length)
    {
        int temp = arr[parent];
        int child = parent * 2 + 1;
        while (child < length)
        {
            if (child + 1 < length && arr[child + 1] < arr[child])
            {
                child++;
            }
            if (temp < arr[child])
            {
                break;
            }
            arr[parent] = arr[child];
            parent = child;
            child = parent * 2 + 1;
        }
        arr[parent] = temp;
    }
}