笔记

常用排序算法总结

张天宇 on 2020-07-28

十大排序算法总结和实现，头疼的堆排序。

排序算法

稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

1. 直接插入

对于未排序的元素，在已排序的元素中从后向前扫描，找到合适的位置后插入。

稳定， 因为未排序的元素在向前扫描过程中遇到相同的元素就不会继续向前扫描了，更不会插在它的前面。

平均和最差情况都是O(n2)，最佳情况为O(n)，如果这个数组本身就是有序的，那么只需要比较 n - 1 次，不需要移动，所以最好的情况下时间复杂度是 n。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*直接插入排序*/
public static int[] InsertSort(int[] arr) {
    if (arr == null || arr.length <= 1) {
        return arr;
    }
    for (int i = 0; i < arr.length - 1; i++) {
        // 将 i + 1 位置的数插入到 0 到 i 之间的数组，从后往前遍历
        // current 指 i + 1 的位置元素，pre 指从 0 到 i 依次向前遍历的指针
        int current = arr[i + 1];
        int pre = i;
        while (pre >= 0 && current < arr[pre]) {
            arr[pre + 1] = arr[pre];
            pre--;
        }
        // 最后将原来 i + 1 位置的元素放入现在 0 到 i + 1 之间数组中正确的位置上
        // pre + 1 是因为刚才结束的时候自减了一次
        arr[pre + 1] = current;
        System.out.println(Arrays.toString(arr));
    }
    return arr;
}

2. 希尔排序

将一组数据分成了不同的组，只有同组元素才能比较和排序，随着排序的进行，组数会慢慢减少，组中的元素也会慢慢增多，数组整体也会慢慢有序。

不稳定，元素间远距离的交换一般都很那保证相同元素的相对位置。

最差情况O(n2)，平均O(nlogn)，最佳情况O(n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/*希尔排序*/
public static int[] ShellSort(int[] arr) {
    if (arr == null || arr.length <= 1) {
        return arr;
    }
    int current, gap = arr.length / 2;
    while (gap > 0) {
        for (int i = gap; i < arr.length; i++) {
            // 将 pre + gap 的数组插入到 0 到 pre 之间同组的数组，从后往前遍历
            // current 指 pre + gap 的位置元素
            current = arr[i];
            int pre = i - gap;
            while (pre >= 0 && arr[pre] > current) {
                arr[pre + gap] = arr[pre];
                pre -= gap;
            }
            arr[pre + gap] = current;
            System.out.println(Arrays.toString(arr));
        }
        gap /= 2;
    }
    return arr;
}

3. 简单选择

时间复杂度上最稳定的算法之一，O(n2)，每次都从未排序的数组中找到最小的元素，然后放在最前端。

不稳定，每趟选择最小元素，但是选哪个不一定，所以没办法保证两个相同元素的相对位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/*简单选择*/
public static int[] SelectionSort(int[] arr) {
    if (arr == null || arr.length <= 1) {
        return arr;
    }
    for (int i = 0; i < arr.length - 1; i++) {
        // 每一轮挑出一个最小的元素，依次与不断增长的 i 位置的元素交换
        int minIndex = i;
        for (int j = i; i < arr.length; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        arr = swap(arr, minIndex, i);
        System.out.println(Arrays.toString(arr));
    }
    return arr;
}

4. 堆排序

老硬骨头了，利用了最大堆的数据结构进行排序，因为每次将堆调整为最大堆之后，堆的根节点一定是堆中最大的元素，通过不停的取出最大堆的根节点和重新调整为最大堆，就可以一直得到未排序数组的最大值。

不稳定，远距离元素交换无法保证相同元素的相对位置。

任何情况下，都是O(nlogn)。

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
/*堆排序*/
public static int[] HeapSort(int[] arr) {
    if (arr == null || arr.length <= 1) return arr;
    // 1. 构建大顶堆
    for (int i = arr.length / 2 - 1; i >= 0; i--) {
        // 从第一个非叶子节点从下至上，从右往左调整结构
        adjustHeap(arr, i, arr.length);
    }
    // 2. 调整堆结构，交换栈顶和末尾元素
    for (int i = arr.length - 1; i > 0; i--) {
        swap(arr, 0, i);
        adjustHeap(arr, 0, i);
    }
    return arr;
}

/*调整堆过程*/
private static void adjustHeap(int[] arr, int i, int length) {
    // 先取出当前元素 i
    int temp = arr[i];
    // 从 i 结点的左子节点开始，因为数组从 0 开始，所以左孩子节点是 2 * i + 1
    for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {
        // 如果左孩子节点小于右孩子节点，k 指向右孩子节点
        if (k + 1 < length && arr[k] < arr[k + 1]) {
            k++;
        }
        // 如果子节点大于父节点，则将子节点赋值给父节点
        if (arr[k] > temp) {
            arr[i] = arr[k];
            i = k;
        } else {
            break;
        }
    }
    // 将 temp 放到最终的位置
    arr[i] = temp;
}

5. 冒泡排序

通过元素的两两交换，将队列中最大的元素移动到队列的末尾。

稳定，因为两两交换，遇到相等的元素不会交换，保证了相同元素的相对位置不变。

平均和最差情况为O(n2)，最佳情况为O(n)，因为平均和最差情况下，每次遍历长度为 n 的数组都只能确定一个元素，所以想要确定全部 n 个元素的位置，时间复杂度就是 n * n，最佳情况下，如果数组是有序的，那么只需要遍历一次就够了，所以时间复杂度是 n。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/*冒泡排序*/
public static int[] BubbleSort(int[] arr) {
    if (arr == null || arr.length <= 1) {
        return arr;
    }
    for (int i = arr.length - 1; i > 0; i--) {
        for (int j = 1; j <= i; j++) {
            if (arr[j] < arr[j - 1]) {
                swap(arr, j, j - 1);
            }
        }
        System.out.println(Arrays.toString(arr));
    }
    return arr;
}

6. 快速排序

通过一趟排序将排序的数组分为独立的两部分，前半部分比关键元素小，后半部分比关键元素大，从而确定了中间元素的位置。

不稳定。

平均O(nlogn)，最差情况下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
25
26
/*快速排序*/
private static int[] QuickSort(int[] arr, int start, int last) {
    if (arr == null || arr.length <= 1 || start >= last) {
        return arr;
    }
    // benchmark 基准数，即这一轮需要确定的数
    int benchmark = arr[start];
    int left = start;
    int right = last;
    while (left < right) {
        // 必须右指针先走，分别找右边比 benchmark 小的
        while (arr[right] >= benchmark && left < right) right--;
        // 左边比 benchmark 大的
        while (arr[left] <= benchmark && left < right) left++;
        if (left < right) {
            swap(arr, left, right);
        }
    }
    // 基准数归位，即
    arr[start] = arr[left];
    arr[left] = benchmark;
    System.out.println(Arrays.toString(arr));
    arr = QuickSort(arr, start, left - 1);
    arr = QuickSort(arr, left + 1, last);
    return arr;
}

7. 归并排序

需要额外空间作为代价，两两排序，然后两个区域一起排序，以此类推。

稳定，因为在使用额外空间的时候，靠前区域的元素只要小于等于靠后元素就可以被放进额外空间。

任何情况下都是O(nlogn)，每一层的时间代价都是 n 相关，一共有 logn 层。

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
/*归并排序*/
public static int[] Merge(int[] arr, int start, int last) {
    if (arr == null || arr.length <= 1 || start >= last) {
        return arr;
    }
    if (start < last) {
        int mid = start + (last - start) / 2;
        // 左右分别递归
        arr = Merge(arr, start, mid);
        arr = Merge(arr, mid + 1, last);
        // 从里到外将左右整合为一部分
        arr = mergeSort(arr, start, mid, last);
    }
    return arr;
}
public static int[] mergeSort(int[] arr, int start, int mid, int last) {
    // tempArr 用来临时给 arr 中同一区域元素排序
    int[] tempArr = new int[arr.length];
    // p1 指 arr 指定区域的左半部分的指针，p2 指指定区域右半部分的指针，p 指额外数组 tempArr 的指针
    int p1 = start, p2 = mid + 1, p = start;
    while (p1 <= mid && p2 <= last) {
        if (arr[p1] <= arr[p2]) {
            tempArr[p++] = arr[p1++];
        } else {
            tempArr[p++] = arr[p2++];
        }
    }
    while (p1 <= mid) tempArr[p++] = arr[p1++];
    while (p2 <= last) tempArr[p++] = arr[p2++];
    for (int i = start; i <= last; i++) {
        arr[i] = tempArr[i];
    }
    System.out.println(Arrays.toString(arr));
    return arr;
}

8. 基数排序

基数排序非比较排序，主要思想是对数组中所有元素根据个位进行排序，再根据十位进行排序，之后是百位，千位，以此类推，直到最高位。

稳定，因为非比较排序，元素之间的顺序不依赖于元素之间的比较。

O(nk)，其中 k 是桶的个数。

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
/*基数排序*/
public static int[] RadixSort(int[] arr) {
    if (arr == null || arr.length <= 1) {
        return arr;
    }
    // max 指数组中最大数，maxDigit 指这个最大的数是几位数
    int max = arr[0];
    for (int a : arr) {
        max = Math.max(max, a);
    }
    int maxDigit = 0;
    while (max != 0) {
        max /= 10;
        maxDigit++;
    }
    // mod 用于为数组中的数取余数，div 用于通过 mod 取余变为个位数
    int mod = 10;
    int div = 1;
    ArrayList<ArrayList<Integer>> bucket = new ArrayList<ArrayList<Integer>>();
    for (int i = 0; i < 10; i++) {
        bucket.add(new ArrayList<>());
    }
    for (int i = 0; i < maxDigit; i++, mod *= 10, div *= 10) {
        System.out.println(Arrays.toString(arr));
        for (int j = 0; j < arr.length; j++) {
            // num 表示当前元素的个/十/百位是几
            int num = (arr[j] % mod) / div;
            bucket.get(num).add(arr[j]);
        }
        int index = 0;
        for (int j = 0; j < 10; j++) {
            if (bucket.get(j).size() != 0) {
                for (int x : bucket.get(j)) {
                    arr[index++] = x;
                }
                bucket.get(j).clear();
            }
        }
    }
    return arr;
}

9. 计数排序

将数组中的元素值转换为键存储在额外空间中。主要思想是额外创建一个数组，额外数组中元素下标是待排序数组中元素的值，而额外数组中的值是其下标的值在待排序数组中作为元素的值出现的次数。

稳定，非比较排序。

O(n + k)，k 是桶的个数。

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
/*计数排序*/
public static int[] CountingSort(int[] arr) {
    if (arr == null || arr.length <= 1) {
        return arr;
    }
    // 因为值的个数和最大最小值都不固定，无法用固定数组来初始化，因此利用最大最小值的差值作为数组个数
    int min, max;
    min = max = arr[0];
    for (int a : arr) {
        min = Math.min(min, a);
        max = Math.max(max, a);
    }
    // 储存每个元素出现次数
    int[] bucket = new int[max - min + 1];
    // 初始化为 0
    // Arrays.fill(arr, 0);
    for (int a : arr) {
        bucket[a - min]++;
    }
    int index = 0;
    for (int i = 0; i < bucket.length; i++) {
        while (bucket[i] != 0) {
            arr[index++] = i + min;
            bucket[i]--;
        }
    }
    return arr;
}

10. 桶排序

计数排序升级版，也是非比较排序，对数组中数值范围进行划分，数组中的每个元素根据其数值的所在范围，进入不同的“桶”。然后在不同的桶中分别对这些元素进行排序（直接插入排序），再依次输出。

桶排序是稳定的。因为它是非比较排序，元素之间的顺序不依赖元素之间的比较。

最好和平均情况下 T(n) = O(n+k)，最差情况下 T(n) = O(n2)，其中 k 是桶的个数。

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
/*桶排序，bucketSize表示桶的容量*/
public static int[] BucketSort(int[] arr, int bucketSize) {
    if (arr == null || arr.length <= 1) {
        return arr;
    }
    int min, max;
    min = max = arr[0];
    for (int a : arr) {
        min = Math.min(min, a);
        max = Math.max(max, a);
    }
    // 桶的个数
    int bucketCount = (max - min) / bucketSize + 1;
    ArrayList<ArrayList<Integer>> bucket = new ArrayList<ArrayList<Integer>>();
    for (int i = 0; i < bucketCount; i++) {
        bucket.add(new ArrayList<Integer>());
    }
    for (int a : arr) {
        // 遍历每个桶
        for (int bucketIndex = 0; bucketIndex < bucketCount; bucketIndex++) {
            // 如果 arr 当前元素在该桶的范围内，则将该元素放桶内，并结束桶的循环
            if (a >= min + bucketIndex * bucketSize && a < min + (bucketIndex + 1) * bucketSize) {
                bucket.get(bucketIndex).add(a);
                break;
            }
        }
    }
    int index = 0;
    for (int i = 0; i < bucketCount; i++) {
        // 对于桶内使用直接插入排序来调整桶内元素的相对顺序
        bucket.set(i, InsertSortOfArrayList(bucket.get(i)));
        for (int x : bucket.get(i)) {
            arr[index++] = x;
        }
    }
    return arr;
}
/*桶排序的直接插入排序*/
private static ArrayList<Integer> InsertSortOfArrayList(ArrayList<Integer> arrayList) {
    if (arrayList == null || arrayList.size() <= 1) return arrayList;
    int current, pre;
    for (int i = 0; i < arrayList.size() - 1; i++) {
        pre = i;
        current = arrayList.get(i + 1);
        while (arrayList.get(pre) > current && pre >= 0) {
            arrayList.set(pre + 1, arrayList.get(pre));
            pre--;
        }
        arrayList.set(pre + 1, current);
    }
    return arrayList;
}



标签
笔记