数据结构与算法之一排序算法

发表于 阅读次数： 评论数： 本文字数： 555 阅读时长 ≈ 1 分钟

前言

排序算法有很多种，常见的包括：

  • 冒泡排序（Bubble Sort）
  • 选择排序（Selection Sort）
  • 插入排序（Insertion Sort）
  • 归并排序（Merge Sort）
  • 快速排序（Quick Sort）
  • 堆排序（Heap Sort）
  • 希尔排序（Shell Sort）
  • 计数排序（Counting Sort）
  • 桶排序（Bucket Sort）
  • 基数排序（Radix Sort）

提示

  • 编程四大基础：数据结构与算法、计算机网络、操作系统、设计模式。

插入排序

插入排序的介绍

插入排序类似于大多数人整理扑克牌的方式，如下图所示：

  • (1) 手里只拿一张牌
  • (2) 拿到下一张牌，并将其插入到正确的排序位置
  • (3) 对所有牌重复上一步

尝试在示例数组 [6, 2, 10, 7] 上使用插入排序，其中排序动作执行的动画如下：

插入排序的实现

伪代码实现

1
2
3
4
5
6
7
8
9
method insertionSort(array A[], integer N)
  for i in [1..N-1] // O(N)
    let X be A[i] // X is the next item to be inserted into A[0..i-1]
    for j from i-1 down to 0 // this loop can be fast or slow
      if A[j] > X
        A[j+1] = A[j] // make a place for X
      else
        break
    A[j+1] = X // insert X at index j+1
  • 外循环执行 N-1 次，这很明显。
  • 但内循环执行的次数取决于输入：
    • 在最好的情况下，数组已经排序并且 (a[j]> X) 总是为假。所以不需要移位数据，并且内部循环在 O (1) 时间内运行。
    • 在最坏的情况下，数组被反向排序并且 (a[j]> X) 总是为真。插入始终发生在数组的前端，并且内部循环在 O (N) 时间内运行。
  • 因此，最佳情况的时间复杂度是 O (N × 1) = O (N) ，最坏情况的时间复杂度是 O (N × N) = O (N2)。

第一种写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class InsertSortDemo {

    /**
     * 效率高的写法（两次循环）
     */
    public static void insertionSort(int[] array) {
        // 从数组的第二个元素开始，依次将其插入已排序的子数组中
        for (int i = 1; i < array.length; i++) {
            // 当前要插入的元素
            int key = array[i];
            // 已排序的子数组的最后一个元素的索引
            int j = i - 1;

            // 将所有比当前元素大的元素向右移动一个位置，直到找到比当前元素小的元素或者已经到达子数组的开头
            while (j >= 0 && array[j] > key) {
                array[j + 1] = array[j];
                j--;
            }
            // 将当前元素插入到合适的位置
            array[j + 1] = key;
        }
    }

}

第二种写法

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
public class InsertSortDemo {

    /**
     * 效率低的写法（三次循环），但代码比较容易理解
     */
    public static void insertionSort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            // 找到要重新排序的元素
            if (array[i] < array[i - 1]) {
                for (int j = 0; j < i; j++) {
                    // 找到元素要插入的位置
                    if (array[i] < array[j]) {
                        int tmp = array[i];
                        // 向后移动数组的元素
                        for (int k = i; k > j; k--) {
                            array[k] = array[k - 1];
                        }
                        array[j] = tmp;
                    }
                }
            }
        }
    }

}