交换排序基本思想：两两比较，如果发生逆序则交换，直到所有记录都排好序为止。

冒泡排序

冒泡排序：每趟不断将记录两两比较，并按“前小后大”规则交换。

  • 事件复杂度=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
internal class Program
{
    private static void Main(string[] args)
    {
        int[] list = { 1, 5, 9, 7, 3 };
        Console.WriteLine("未排序前的数组：");
        for (int i = 0; i < list.Length; i++)
        {
            Console.Write(list[i] + " ");
        }
        Console.WriteLine();
        Bubble_sort(list);
        Console.WriteLine("排序后的数组：");
        for (int i = 0; i < list.Length; i++)
        {
            Console.Write(list[i] + " ");
        }
    }

    public static void Bubble_sort(int[] list)
    {
        int temp;
        // 比较 length - 1 趟
        for (int i = 0; i < list.Length - 1; i++)
        {
            // 每趟比较次数比前一趟少一次
            for (int j = 0; j < list.Length - 1 - i; j++)
            {
                // 两两比较元素，小的前移，大的后移
                if (list[j] > list[j + 1])
                {
                    temp = list[j];
                    list[j] = list[j + 1];
                    list[j + 1] = temp;
                }
            }
        }
    }
}

输出：

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

快速排序

快速排序（分治算法思想）：任取一个元素为中心，所有比它小的元素一律前放，大的后放，形成左右两个子表。

  • 最坏情况，时间复杂度=O(n2)。理想状态，时间复杂度=O(nlog2n)，空间复杂度=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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
// 挖坑法：用一个临时变量存储基准元素
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();
        quick_sort(arr, 0, arr.Length - 1);
        Console.WriteLine("排序后的数组：");
        for (int i = 0; i < arr.Length; i++)
        {
            Console.Write(arr[i] + " ");
        }
    }

    private static void quick_sort(int[] arr, int left, int right)
    {
        int l = left; // 记录左指针元素
        int r = right; // 记录右指针元素
        if (left >= right)
        {
            return; // 递归退出条件：左指针 >= 右指针
        }
        int pivot = arr[left]; // 以数组左边第一个元素为基准元素
        while (left < right)
        {
            // 从数组最右开始，找到第一个比基准元素小的元素
            while (arr[right] > pivot && left < right)
            {
                right--;
            }
            if (left < right)
            {
                // 把右边第一个比基准小的元素，放到数组左边
                arr[left++] = arr[right];
            }
            // 从最左边找到第一个比基准元素大的元素
            while (arr[left] < pivot && left < right)
            {
                left++;
            }
            if (left < right)
            {
                // 把左边第一个比基准大的元素，放到数组右边
                arr[right--] = arr[left];
            }
        }
        // 当左右指针重合退出 while 后，把基准元素放到当前 left 位置
        arr[left] = pivot;
        quick_sort(arr, l, left - 1); // 递归调用快速排序，排好基准元素左边的元素
        quick_sort(arr, left + 1, r); // 递归调用快速排序，排好基准元素右边的元素
    }
}
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
// Hoare版：基本思想就是用两个指针分别指向待排序数组的开头和结尾。
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();
        Hoare_quick_sort(arr, 0, arr.Length - 1);
        Console.WriteLine("排序后的数组：");
        for (int i = 0; i < arr.Length; i++)
        {
            Console.Write(arr[i] + " ");
        }
    }
    
    private static void Hoare_quick_sort(int[] arr, int left, int right)
    {
        if (left >= right)
        {
            return;
        }
        int pivot = left; // 存储基准元素的下标
        int l = left;
        int r = right;
        while (left < right)
        {
            while (left < right && arr[right] >= arr[pivot])
            {
                right--;
            }
            while (left < right && arr[left] <= arr[pivot])
            {
                left++;
            }
            swap(arr, left, right);
        }
        swap(arr, pivot, left);
        Hoare_quick_sort(arr, l, left - 1);
        Hoare_quick_sort(arr, left + 1, r);
    }

    private static void swap(int[] arr, int left, int right)
    {
        int temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
    }
}

输出：

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