冒泡、选择、插入、希尔排序算法详解

1 冒泡排序 (Bubble Sort)

冒泡排序算法是一种简单的排序算法,它重复地遍历要排序的列表,比较相邻的两个元素,并按照大小顺序交换它们。这样,每一次遍历都会将最大(或最小)的元素移动到列表的末尾。重复这个过程,直到整个列表都是有序的。冒泡排序算法的实现代码如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
public void bubbleSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // 交换 arr[j] 和 arr[j+1]
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

冒泡排序算法的时间复杂度为 $O(n^2)$,其中 $n$ 是要排序的元素个数。

下面是冒泡排序过程的示意图:

冒泡排序示意图

2 选择排序 (Selection Sort)

选择排序算法也是一种简单的排序算法,它将列表分为已排序和未排序两部分。每次从未排序部分选择最小(或最大)的元素,并将其放到已排序部分的末尾。重复这个过程,直到整个列表都是有序的。选择排序算法的实现代码如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
public void selectionSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        // 交换 arr[i] 和 arr[minIndex]
        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}

选择排序算法的时间复杂度为 $O(n^2)$,其中 $n$ 是要排序的元素个数。

下面是选择排序过程的示意图:

选择排序示意图

3 插入排序 (Insertion Sort)

插入排序算法也是一种简单的排序算法,它也将列表分为已排序和未排序两部分。每次从未排序部分选择一个元素(往往选择第一个),并将其插入到已排序部分的正确位置。重复这个过程,直到整个列表都是有序的。插入排序算法的实现代码如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
public void insertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int key = arr[i];
        int j = i - 1;
        // 如果已排序的序列中存在比 key 大的,
        //  则整体往后挪动
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        // 然后把 key 插入有序序列中合适的位置
        arr[j + 1] = key;
    }
}

插入排序算法的时间复杂度为 $O(n^2)$,其中 $n$ 是要排序的元素个数。

下面是插入排序过程的示意图:

插入排序示意图

4 希尔排序 (Shell Sort)

希尔排序算法是一种改进的插入排序算法,它利用间隙 (gap) 将列表分为多个子列表,并对每个子列表进行插入排序。每次排序时,子列表的元素间隙逐渐减小,直到间隙为 1,完成最后一次插入排序。希尔排序算法的实现代码如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
public void shellSort(int[] arr) {
    int n = arr.length;
    for (int gap = n / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; i++) {
            int temp = arr[i];
            int j = i;
            while (j >= gap && arr[j - gap] > temp) {
                arr[j] = arr[j - gap];
                j -= gap;
            }
            arr[j] = temp;
        }
    }
}

希尔排序算法的时间复杂度取决于间隔序列的选择,最坏情况下为 $O(n^2)$,平均情况下为 $O(n \log n)$。其中 $n$ 是要排序的元素个数。

下面是希尔排序过程的示意图:

插入排序示意图