算法经典重读之经典排序

Posted by Sinsy on September 24, 2020 About 6 k words and Need 18 min

经典排序算法

引言

最近参加了 Datawhale 的算法打卡活动,感觉自己还是很多不足。决定翻开吃灰的《算法3》。重新学习下算法,加深下记忆。

导航

冒泡排序

冒泡排序(Bubble Sort)是一种简单的排序算法。由于在算法的执行过程中,较小的元素像汽包般慢慢 到数列的顶端,故称为冒泡排序。

工作原理

每次检查相邻两个元素,如果前面的元素与后面的元素满足给定的排序条件,就将相邻两个元素交换,当没有相邻的元素需要交换时,排序就完成了。

经过 i 次扫描后,数列的末尾 i 项必定是最大的 i 项,因此冒泡排序最多需要扫描 n - 1 遍数组就能完成排序。

性质

稳定的排序方法。(稳定排序意思就是排序之前和排序之后位置不变。比如 1 3 3 1 这样的数组,位置 i = 2 时,3 怎么交换都在原来位置)

时间复杂度

  • 序列完全有序,时间复杂度 O(n)
  • 最坏情况下需要执行 (n - 1) * n / 2 次交换,时间复杂度 O(n²)
  • 平均情况下,时间复杂度 O(n²)

空间复杂度

在原来的数列完成,需要一个辅助空间,故空间复杂度 O(1)

代码实现

实现一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
private static void bubbleSort(int[] arr) {
    int temp;
    for (int i = 0; i < arr.length - 1; i++) {
        boolean flag = false;
        for (int j = 0; j < arr.length - 1 - i; j++) {

            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                flag = true;
            }
        }
        if (!flag) {
            break;
        }
    }

}

实现二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
private static void bubbleSort(int[] arr) {
    int temp;
    for (int i = 0; i < arr.length; i++) {
        for (int j = 0; j < arr.length; j++) {

            if (arr[i] < arr[j]) {
                temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }

        }
    }

}

效果

bubble-sort

选择排序

选择排序是一种简单直观的排序算法,无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候,数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

工作原理

首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。

性质

由于 swap(交换两个元素)操作的存在,选择排序是一个不稳定排序。

时间复杂度

  • 平均时间复杂度 О(n²)
  • 最坏时间复杂度 О(n²)
  • 最优时间复杂度 О(n²)

空间复杂度

和冒泡排序一样,都是在同一个序列完成,需要一个辅助空间,故空间复杂度 O(1)

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
private static void selectionSort(int[] arr) {
    int min;
    for (int i = 0; i < arr.length - 1; i++) {
        min = i;
        // 找到比当前更小的值,如果想从大到小,则找最大值
        for (int j = i; j < arr.length; j++) {

            if (arr[min] > arr[j]) {
                // 记录下标
                min = j;
            }
        }
        if (i != min) {
            int temp = arr[i];
            arr[i] = arr[min];
            arr[min] = temp;
        }
    }
}

效果

selection-sort

插入排序

插入排序不如前面两个排序简单,但是和扑克牌差不多,就是发下来是乱的,需要你直接插到对应位置。

工作原理

将待排列元素划分为“已排序”和“未排序”两部分,每次从“未排序的”元素中选择一个插入到“已排序的”元素中的正确位置。

一个与插入排序相同的操作是打扑克牌时,从牌桌上抓一张牌,按牌面大小插到手牌后,再抓下一张牌。

性质

是一个稳定排序。

时间复杂度

  • 平均时间复杂度 О(n²)
  • 最坏时间复杂度 О(n²)
  • 最优时间复杂度 О(n)

空间复杂度

需要辅助空间 O(1)

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
private static void insertSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {

        int temp = arr[i];
        int j = i;
        while (j > 0 && temp < arr[j - 1]) {
            // 往后一位
            arr[j] = arr[j - 1];
            // 找到合适位置
            j--;
        }
        if (j != i) {
            // 交换位置
            arr[j] = temp;
        }
    }
}

效果

insert-sort

归并排序

归并排序是一种采用了分治思想的排序算法。

工作原理

采用分治法:

  • 分割:递归地把当前序列平均分割成两半。
  • 集成:在保持元素顺序的同时将上一步得到的子序列集成到一起(归并)。

性质

稳定排序

时间复杂度

  • 平均时间复杂度 O(nlog n)
  • 最坏时间复杂度 O(nlog n)
  • 最优时间复杂度 O(nlog n)

空间复杂度

需要额外的数组空间,故 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
24
25
26
27
28
29
30
31
32
33
34
35
36
private static void sort(int[] arr, int low, int high) {
    int mid = (low + high) / 2;
    if (low < high) {
        sort(arr, low, mid);
        sort(arr, mid + 1, high);
        merge(arr,low, mid, high);
    }
}

private static void merge(int[] arr, int low, int mid, int high) {
    int[] temp = new int[high + 1 - low];

    int i = low;
    int j = mid + 1;
    int k = 0;

    while (i <= mid && j <= high) {
        if (arr[i] < arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }
    while (i <= mid) {
        temp[k++] = arr[i++];
    }

    while (j <= high) {
        temp[k++] = arr[j++];
    }

    if (temp.length >= 0) {
        System.arraycopy(temp, 0, arr, low, temp.length);
    }

}

效果

merge-sort




快速排序

快速排序(英语:Quicksort),又称分区交换排序(partition-exchange sort),简称快排,是一种被广泛运用的排序算法。

工作原理

快速排序的工作原理是通过 分治 的方式来将一个数组排序。

快速排序分为三个过程:

  1. 将数列划分为两部分(要求保证相对大小关系);
  2. 递归到两个子序列中分别进行快速排序;
  3. 不用合并,因为此时数列已经完全有序。

和归并排序不同,第一步并不是直接分成前后两个序列,而是在分的过程中要保证相对大小关系。具体来说,第一步要是要把数列分成两个部分,然后保证前一个子数列中的数都小于后一个子数列中的数。为了保证平均时间复杂度,一般是随机选择一个数 来当做两个子数列的分界。

之后,维护一前一后两个指针 和 ,依次考虑当前的数是否放在了应该放的位置(前还是后)。如果当前的数没放对,比如说如果后面的指针 遇到了一个比 小的数,那么可以交换 和 位置上的数,再把 向后移一位。当前的数的位置全放对后,再移动指针继续处理,直到两个指针相遇。

其实,快速排序没有指定应如何具体实现第一步,不论是选择 的过程还是划分的过程,都有不止一种实现方法。

第三步中的序列已经分别有序且第一个序列中的数都小于第二个数,所以直接拼接起来就好了。

性质

不稳定排序

时间复杂度

  • 平均时间复杂度 O(nlogn)
  • 最坏时间复杂度 O(n²)
  • 最优时间复杂度 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
private static void quickSort(int[] arr, int low, int high) {

    if (low >= high) {
        return;
    }
    int p = arr[low];
    int i = low;
    int j = high;
    int temp;
    while (i < j) {
        while (arr[j] >= p && i < j) {
            j--;
        }
        while (arr[i] <= p && i < j){
            i++;
        }
        temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }
    arr[low] = arr[i];
    arr[i] = p;
    quickSort(arr, low, j-1);
    quickSort(arr, j+1, high);
}

效果

quick-sort

基数排序

基数排序(Radix Sort)是一种非比较型的排序算法,最早用于解决卡片排序的问题。

工作原理

将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序也不是只能使用于整数。

性质

稳定排序

时间复杂度

  • 最坏时间复杂度 O(kN)

空间复杂度

需要 k 个 桶,故需要 O(k + O)

实现代码

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
private static void radixSort(int[] arr) {

    int max = arr[0];
    int exp;
    for (int anArr : arr) {
        if (anArr > max) {
            max = anArr;
        }
    }

    for (exp = 1; max / exp > 0; exp *= 10) {
        int[] temp = new int[arr.length];
        int[] buckets = new int[10];
        for (int value : arr) {
            buckets[(value / exp) % 10]++;

        }
        for (int i = 1; i < buckets.length; i++) {

            buckets[i] += buckets[i - 1];
        }
        for (int i = arr.length - 1; i >= 0; i--) {
            temp[buckets[(arr[i] / exp) % 10] - 1] = arr[i];
            buckets[(arr[i] / exp) % 10]--;
        }

        System.arraycopy(temp, 0, arr,0, arr.length);
    }
}

效果

radix-sort

总结

排序算法 平均时间复杂度 最坏时间复杂度 最好时间复杂度 空间复杂度 稳定性
冒泡排序 O(n²) O(n²) O(n) O(1) 稳定
基数排序 O(kN) O(kN) O(kN) O(k + O) 稳定
归并排序 O(nlog n) O(nlog n) O(nlog n) O(n) 稳定
快速排序 O(nlog n O(n²) O(nlog n 根据具体实现不同 不稳定
插入排序 O(n²) O(n²) O(n) O(1) 稳定
选择排序 O(n²) O(n²) O(n²) O(1) 不稳定

声明

作者: Sinsy
本文链接:https://blog.sincehub.cn/2020/09/24/classic-sort/
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文声明。
如您有任何商业合作或者授权方面的协商,请给我留言:550569627@qq.com

引用