Shallow Dream

Keep It Simple and Stupid!

0%

排序

发表于 更新于 分类于 ，
本文字数： 1.4k 阅读时长 ≈ 5 分钟

语言：Java

数组未说明时默认升序

一个很好的网站：https://visualgo.net/zh

这东西还没完...我先整个框而已

几个基本的认识

  1. 一个数是天然有序的

  2. 有序数组的最大值和最小值很好找，给定目标值在O(\(log_n\))的时间内都可以完成查找。

  3. 在有序数组中，对于任何一个数，都有

    \(左边的所有数 \le 这个数 \le 右边的所有数\)

  4. 两个有序数组很容易合成一个有序数组

选择排序

对于一个长度为 n 的数组来说

在0~n-1的范围内，找到最小值，放在当前范围的第一位

此时0位置上的数已经确定，剩余的1~n-1为无序数组，接下来

在1~n-1的范围内，找到最小值，放在当前范围的第一位...

在2~n-1的范围内，找到最小值，放在当前范围的第一位...

...

在k~n-1的范围内，找到最小值，放在当前范围的第一位...

...

在n-1~n-1的范围内，找到最小值，放在当前范围的第一位...

之后完成排序，结束算法

每次找出当前范围数组中的最小值，然后缩小范围

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 选择排序
public static void selectSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;					
    }
    
    int N = arr.length;
    for (int i = 0; i < N; i++) {
        int minValueIndex = i;
        for (int j = i + 1; j < N; j++) {
            minValueIndex = arr[minValueIndex] < arr[j] ? minValueIndex : j;
        }
        swap(arr, minValueIndex, i);
    }
}

先写边界条件，当数组为空或者数组长度小于2时，不需要排序，直接退出

然后对于上面的方法，首先用一层循环枚举左边界，从0到n-1

然后利用minValueIndex记录当前最小值位置，开始时默认当前位置为最小值

然后依次枚举后面的数，当后面的数大于当前最小值时不变，当后面的数小于当前最小值时更新最小值位置

最后交换 i 位置的数和记录位置的最小值

然后重复执行上述操作，直至排序结束

冒泡排序

对于一个长度为 n 的数组来说

在0~n-1的范围上，如果后一个数小于前一个数，交换两个数...

上述操作完成后，第一大的数在n-1位

在0~n-2的范围上，如果后一个数小于前一个数，交换两个数...

上述操作完成后，第二大的数在n-2位

...

在0~n-k的范围上，如果后一个数小于前一个数，交换两个数...

上述操作完成后，第k大的数在n-k位

...

在0~1的范围上，如果后一个数小于前一个数，交换两个数...

上述操作完成后，第n-1大的数在1位

之后完成排序，结束算法

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static void bubbleSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }

    int N = arr.length;
    for (int end = N - 1; end >= 0; end--) {
        for (int second = 1; second <= end; second++) {
            if (arr[second - 1] > arr[second]) {
                swap(arr, second - 1, second);
            }
        }
    }
}

先写边界条件，当数组为空或者数组长度小于 2 时，不需要排序，直接退出

对于上述算法，枚举最后一位(end)，从 n-1 到 0，内层再从 1 到当前的最后一位，枚举当前数(second)

比较当前数和前一个数（从 1 枚举保证当前位置 -1 是前一个数的位置存在），若前一个数大于当前数，交换

然后重复执行上述操作，直至排序结束

插入排序

打过扑克牌嘛？想象一下你正在把一副杂乱的牌按顺序理好，拿出一张，依次比较，找到一个位置，左边的比他小，右边的比他大，然后你就把牌插进去

插入排序思想类似

对于一个长度为 n 的数组来说

在0~1的范围上，把 1 位置上的数和前一个数交换，直到前一个数小于当前数，或者当前数已经到 0 位置（前一个数越界）...

在0~2的范围上，把 2 位置上的数和前一个数交换，直到前一个数小于当前数，或者当前数已经到 0 位置（前一个数越界）...

...

在0~k的范围上，把 k 位置上的数和前一个数交换，直到前一个数小于当前数，或者当前数已经到 0 位置（前一个数越界）...

...

在0~n-1的范围上，把 n-1 位置上的数和前一个数交换，直到前一个数小于当前数，或者当前数已经到 0 位置（前一个数越界）...

原数组排好序

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static void insertSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;					
    }
    
    int N = arr.length;
    for (int end = 1; end < N; end++) {
        int curNumIndex = end;
        while (curNumIndex - 1 >= 0 && arr[curNumIndex - 1] > arr[curNumIndex]) {
            swap(arr, curNumIndex, curNumIndex - 1);
            curNumIndex--;
        }
    }
}

优化后代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
public static void insertSort2(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;					
    }
    
    int N = arr.length;
    for (int end = 1; end < N; end++) {
        for (int pre = end - 1; pre >= 0 && arr[pre] > arr[pre + 1]; pre--) {
            swap(arr, pre + 1, pre);
        }
    }
}

归并排序

代码如下：

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
//归并排序
public static void mergeSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    process(arr, 0, arr.length - 1);
}

public static void process(int[] arr, int L, int R) {
    if (L == R) {
        return;
    }
    int mid = L + ((R - L) >> 1);
    process(arr, L, mid);
    process(arr, mid + 1, R);
    merge(arr, L, mid, R);
}

public static void merge(int[] arr, int L, int M, int R) {
    int helpLen = R - L + 1;
    int[] help = new int[helpLen];
    int i = 0;
    int p1 = L;
    int p2 = M + 1;
    
    while (p1 <= M && p2 <= R) {
        help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
    }
    while (p1 <= M) {
        help[i++] = arr[p1++];
    }
    while (p2 <= R) {
        help[i++] = arr[p2++];
    }
    for (i = 0; i < helpLen; i++) {
        arr[L + i] = help[i];
    }
}