Content Table
2019-01-18

常用排序

下面列举常用的排序算法的实现:

  • 冒泡排序
  • 插入排序
  • 选择排序
  • 快速排序
  • 归并排序
  • 堆排序

排序的时候, 需要大量的交换数组中的 2 个元素, 使用下面的函数 swap() 进行交换:

1
2
3
4
5
6
7
8
/**
 * 交换数组中指定下标的 2 个元素的值
 */
public static void swap(int[] a, int indexA, int indexB) {
    int temp  = a[indexA];
    a[indexA] = a[indexB];
    a[indexB] = temp;
}

冒泡排序

原理:

  1. 比较相邻的元素，如果第一个比第二个大，就交换他们两个，把大的交换到后面。
  2. 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对，最后的元素应该会是最大的数。
  3. 针对所有的元素重复以上的步骤，除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
  5. 有 n 个元素的数组需要进行 n-1 轮
1
2
3
4
5
6
7
8
9
10
11
12
13
/**
 * 冒泡排序
 */
public static void bubbleSort(int[] a) {
    for (int r = 1; r < a.length; ++r) { // r: round
        for (int i = 0; i < a.length-r; ++i) {
            // 如果 a[i] 大于 a[i+1], 则把大的交换到后面
            if (a[i] > a[i+1]) {
                swap(a, i, i+1);
            }
        }
    }
}

插入排序

从整个待排序列中选出一个元素插入到已经有序的子序列中去，得到一个有序的、长度加一的子序列，直到整个序列的待插入元素为 0，则整个序列全部有序。

实现时选择数组的第一个元素作为有序序列 (因为一个元素肯定是有序的)，然后逐渐将后面的元素插入到前面的有序序列中，直到整个序列有序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * 插入排序
 */
public static void insertSort(int[] a) {
    for (int i = 1; i < a.length; ++i) {
        int current = a[i];
        int j = i;

        while (j>0 && current<a[j-1]) {
            a[j] = a[j-1];
            j--;
        }

        a[j] = current;
    }
}
1
2
3
4
5
6
7
8
// 使用冒泡的方式交换元素，简化代码，但是效率相对低一些
public static void insertSort(int[] a) {
    for (int i = 1; i < a.length; ++i) {
        for (int j = i; j>0 && a[j]<a[j-1]; --j) {
            swap(a, j, j-1);
        }
    }
}

希尔排序 (Shell’s Sort) 是插入排序的一种又称缩小增量排序 (Diminishing Increment Sort)，是直接插入排序算法的一种更高效的改进版本，希尔排序是非稳定排序算法，该方法因 D.L.Shell 于 1959 年提出而得名。

希尔排序是把元素按下标的一定增量分组 (可选 n/2)，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个数组恰被分成一组，算法便终止。

1
2
3
4
5
6
7
8
9
10
11
12
/**
 * 希尔排序
 */
public static void shellSort(int[] a) {
    for (int gap = a.length / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < a.length; ++i) {
            for (int j = i; j-gap>=0 && a[j]<a[j-gap]; j -= gap) {
                swap(a, j, j-gap);
            }
        }
    }
}

选择排序

选择排序 (Selection sort) 是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小 (或最大) 的一个元素，存放在序列的末尾，然后，再从剩余待排序元素中继续寻找最小 (大) 元素，然后放到此待排序序列的末尾。以此类推，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * 选择排序
 */
public static void selectionSort(int[] a) {
    for (int i = a.length - 1; i > 0; i--) {
        int max = 0;
        for (int j = 1; j <= i; j++) {
            // 找到最大值的下表
            if (a[j] > a[max]) {
                max = j;
            }
        }

        swap(a, max, i);
    }
}

快速排序

快速排序的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

一趟快速排序的具体过程可描述为：从待排序列中任意选取一个元素 (通常选取第一个记录) 作为基准值，然后将记录中关键字比它小的记录都放置在它的位置之前，将记录中关键字比它大的记录都安置在它的位置之后。这样，以该基准值为分界线，将待排序列分成的两个子序列。

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
/**
 * 使用快速排序对数组进行排序
 */
public static void quickSort(int[] a) {
    quickSort(a, 0, a.length-1);
}

/**
 * 使用快速排序对数组 a 中 low 到 high 之间的元素进行排序
 */
public static void quickSort(int[] a, int low, int high) {
    if (low < high) {
        int pivot = partition(a, low, high);

        quickSort(a, low, pivot-1);
        quickSort(a, pivot+1, high);
    }
}

/**
 * 分区: 把数组中小于 a[pivot] 的数放到 pivot 的左边, 大于 a[pivot] 的数放到 pivot 的右边
 *
 * @return 返回分区的下标 pivot
 */
public static int partition(int[] a, int low, int high) {
    int pivotValue = a[low]; // pivotValue 作为参考值缓存起来，a[low] 空出来了

    // 数组右边的数大于等于 pivotValue
    // 数组左边的数小于等于 pivotValue
    while (low < high) {
        // 提示: low 和 high 的 ++ 与 -- 没有在赋值的时候进行, 而是在循环内执行,
        // 避免 while 中 low == high 时外部进行 ++, --, 导致 low > high

        // 从右向左找到第一个小于 pivotValue 的数，放到 a[low]，此时则 a[high] 空出来
        while (low < high && a[high]>=pivotValue) {
            --high;
        }
        a[low] = a[high];

        // 从左向右找到第一个大于 pivotValue 的数，放到 a[high]，此时则 a[low] 空出来
        while (low < high && a[low]<=pivotValue) {
            ++low;
        }
        a[high] = a[low];
    }

    // 循环结束时 low == high, pivot 的左边的数都小于 pivotValue, pivot 右边的数都大于 pivotValue
    int pivot = low;
    a[pivot] = pivotValue;

    return pivot;
}

还有一种常见的做法是一趟中找到适合的 2 个数后一次性交换的逻辑

  • 数组右边的数大于 pivotValue
  • 数组左边的数小于等于 pivotValue (因为左边第一个数作为 pivotValue，需要跳过它进行比较)

测试数据: 5, 2, 6, 7, 5, 4, 8, 5

上面的方法是双边循环法进行分区，下面使用单边循环法进行分区:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * 单边循环法分区
 *
 * @return 返回分区的下标 pivot
 */
public static int partition(int[] a, int low, int high) {
    int pivot = a[low];
    int mark  = low; // mark 以及它前面的数据小于等于 pivot

    for (int i = mark+1; i <= high; ++i) {
        if (a[i] <= pivot) {
            swap(a, ++mark, i); // 找到合适的数 a[i]，区域 mark 扩大 1 个范围，然后交换 a[i] 和 a[mark]
        }
    }

    swap(a, low, mark); // 把 pivot 放到中间

    return mark;
}

归并排序

原理:

  1. 将待排序的数列分成若干个长度为 1 的子数列，然后将这些数列两两合并
  2. 得到若干个长度为 2 的有序数列，再将这些数列两两合并
  3. 得到若干个长度为 4 的有序数列，再将它们两两合并
  4. 直接合并成一个数列为止

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
/**
 * 归并排序
 */
public static void mergeSort(int[] a) {
    int[] o = a;
    int[] t = new int[a.length];

    for (int chunk = 1; chunk < a.length; chunk *= 2) {
        for (int l = 0; l < a.length; l += 2*chunk) {
            // 前 chunk 个元素和后续 chunk 个元素作为一组进行归并 (有序数组合并): [l,m) ~ [m,h)
            int m = Math.min(l+chunk, a.length);
            int h = Math.min(m+chunk, a.length);
            merge(a, l, m, h, t);
        }

        // 一轮归并结束后, t 是此轮归并后的数组, 新一轮归并需要在前一轮归并的基础上进行
        // 交互 a 和 t, 使得 a 是归并后的数组
        int[] x = a;
        a = t;
        t = x;
    }

    // 归并结束时, a 的数据是有序的, 但是此时 a 不一定指向传入进来的数组, 也就是说 a 不一定等于 o,
    // 需要复制数组 a 到原来的数组 o 中，这样函数外访问传入的数组才是排序后的有序数组 (引用使用传值传递)
    System.arraycopy(a, 0, o, 0, a.length);
}

/**
 * 有序数组合并
 * 把数组 a 中的 [l, m) 到 [m, h) 部分合并为有序数列到 t 的 [l, h) 中
 */
public static void merge(int[] a, int l, int m, int h, int[] t) {
    int i = l;
    int j = m;
    int k = l;

    while (i < m && j < h) {
        if (a[i] < a[j]) {
            t[k++] = a[i++];
        } else {
            t[k++] = a[j++];
        }
    }

    while (i < m) {
        t[k++] = a[i++];
    }

    while (j < h) {
        t[k++] = a[j++];
    }
}

堆排序

堆排序 (Heap Sort) 是利用堆进行排序的方法，其基本思想为：将待排序列构造成一个大顶堆 (或小顶堆)，整个序列的最大值 (或最小值) 就是堆顶的根结点，将根节点的值和堆数组的末尾元素交换，此时末尾元素就是最大值 (或最小值)，然后将剩余的 n-1 个序列重新构造成一个堆，这样就会得到 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
37
38
39
/**
 * 使用堆排序对数组进行排序
 */
public static void heapSort(int[] a) {
    // 把整个数组调整为大顶堆
    for (int parent = a.length/2-1; parent>=0; --parent) {
        adjustHeap(a, parent, a.length);
    }

    // a[0] 为最大的数，和最后一个交换，再把数组调整为大顶堆
    for (int end = a.length-1; end > 0; --end) {
        swap(a, 0, end);
        adjustHeap(a, 0, end);
    }
}

/**
 * 调整 a 为大顶堆, parent 的左右子树已经是大顶堆
 */
public static void adjustHeap(int[] a, int parent, final int end) {
    int temp = a[parent];

    for (int left = parent*2+1; left < end; left = parent*2+1) {
        // max   存储左右节点中最大数的下标
        // left  存储左子节点的下标
        // right 存储右子节点的下标
        int max   = left;
        int right = left + 1;

        if (right<end && a[left]<a[right]) max = right; // 左右子节点中最大的数
        if (temp >= a[max]) break; // parent 已经是最大值, 说明已经是大顶堆, 不需要再进行调整了

        // a[parent] 存储左右子节点中的最大值, 并把 parent 指向此节点
        a[parent] = a[max];
        parent = max;
    }

    a[parent] = temp;
}