al_09 十大排序算法


阅读数: 次   
如需转载，请根据 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 许可，附上本文作者及链接。
本文作者： 执笔成念
作者昵称： zbcn
本文链接： https://1363653611.github.io/zbcn.github.io/2021/01/02/al_09%E5%8D%81%E5%A4%A7%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95/

十大排序算法

image-20210117130713082

十大算法的复杂度

img

比较排序

交换类

冒泡排序

交换排序的典型，也是快排思想的基础，冒泡排序是一种稳定排序算法。

  • 时间复杂度：O(n^2).
  • 基本思想：循环遍历多次，每次从前往后把大元素往后调，每次确定一个最大（最小）元素，多次后达到排序序列。（或者从后往前把小元素往前调）

算法思想：

  1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
  2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
  3. 针对所有的元素重复以上的步骤，除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

Image

实现思路
  • 从第一个元素开始往后遍历，每一个位置判断是否比后面的元素大，如果比后面的元素大，那么就交换两者大小，然后继续向后，这样的话进行一轮之后就可以保证「最大的那个数被交换交换到最末的位置可以确定」。
  • 第二次同样从开始起向后判断着前进，如果当前位置比后面一个位置更大的那么就和他后面的那个数交换。但是有点注意的是，这次并不需要判断到最后，只需要判断到倒数第二个位置就行(因为第一次我们已经确定最大的在倒数第一，这次的目的是确定倒数第二)
  • 同理，后面的遍历长度每次减一，直到第一个元素使得整个元素有序。

image-20210117133433984

代码实现：

1
def bubble_sort(arr):
2
    """
3
    冒泡算法
4
    :return:
5
    """
6
    length = len(arr)
7
    # 第一层遍历(表示比较的次数)
8
    for i in range(length):
9
        # 数据处理
10
        for j in range(1, length - i):
11
            if arr[j - 1] > arr[j]:
12
                # 两者交换数据，这里没用temp，因为python 特性： 元组
13
                arr[j - 1], arr[j] = arr[j], arr[j - 1]
14
15
    return arr
16
17
18
def bubble_sort_flag(arr):
19
    """
20
    带标记的排序算法
21
    :param arr:
22
    :return:
23
    """
24
    length = len(arr)
25
    for index in range(length):
26
        flag = True
27
        for j in range(1,length-index):
28
            if arr[j-1] > arr[j]:
29
                arr[j],arr[j-1] = arr[j-1], arr[j]
30
                flag = False
31
        # 表示排序已经完成，则直接退出
32
        if flag:
33
            return arr
34
    return arr

快速排序

快速排序是对冒泡排序的一种改进，采用递归分制的方法进行求解。快速排序是一种不稳定的排序方法。

  • 时间复杂度：最坏是O(n^2)，平均时间复杂度为O(nlogn),最好情况的时间复杂度为O(nlogn)
基本思想
  • 从数列中挑出一个元素，称为”基准”（pivot），
  • 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
  • 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
算法思想：
  1. 选取第一个数为基准
  2. 将比基准小的数交换到前面，比基准大的数交换到后面
  3. 对左右区间重复第二步，直到各区间只有一个数

image-20210117142802201

img

代码实现
1
def quick_sort(arr):
2
    """
3
    快速排序
4
    1. 从数列中挑出一个元素，称为”基准”（pivot），
5
    2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
6
    3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
7
    :param arr:
8
    :param left:
9
    :param right:
10
    :return:
11
    """
12
    # 比基准小的数组
13
    less = []
14
    # 比基准大的数组
15
    more = []
16
    # 等于基准数据的集合
17
    pivotList = []
18
19
    # 跳出递归的节点
20
    if len(arr) <= 1:
21
        return arr
22
    else:
23
        # 将第一个值作为基准节点
24
        pivote = arr[0]
25
        for i in arr:
26
            # 将 比基准小的放到 less 数组
27
            if i < pivote:
28
                less.append(i)
29
            elif i > pivote:  # 比基准大的放到more 节点
30
                more.append(i)
31
            else:  # 等于基准的放到 pivoteList
32
                pivotList.append(i)
33
        # 对less数列和more数列继续进行排序
34
        less = quick_sort(less)
35
        more = quick_sort(more)
36
        #  最终结果拼接
37
        return less + pivotList + more
38
39
40
def quick_sort2(arr, left, right):
41
    """
42
    1. 快排需要将序列变成两个部分，就是「序列左边全部小于一个数」，「序列右面全部大于一个数」，
43
    然后利用递归的思想再将左序列当成一个完整的序列再进行排序，同样把序列的右侧也当成一个完整的序列进行排序。
44
    2. 其中这个数在这个序列中是可以随机取的，可以取最左边，可以取最右边，当然也可以取随机数。但是「通常」不优化情况我们取最左边的那个数
45
    :param arr:  原始数组
46
    :param left: 起始位置:默认 0
47
    :param right: 数组的长度 -1
48
    :return:
49
    """
50
    low = left
51
    high = right
52
    if low > high:  # 下面两句的顺序一定不能混，否则会产生数组越界！
53
        return
54
    # 额外空间temp，取最左侧的一个作为衡量，最后要求左侧都比它小，右侧都比它大。
55
    temp = arr[low]
56
    # 这一轮要求把左侧小于temp,右侧大于temp。
57
    while low < high:
58
        # 右侧找到第一个小于temp的停止
59
        while low < high and arr[high] > temp:
60
            high -= 1
61
        arr[low] = arr[high]
62
        # 左侧找到第一个大于 temp 的值停止
63
        while low < high and arr[low] < temp:
64
            low += 1
65
        arr[high] = arr[low]
66
67
    # 赋值然后左右递归分治求之
68
    arr[low] = temp
69
    quick_sort2(arr, left, low - 1)
70
    quick_sort2(arr, low + 1, right)

插入类

直接插入排序

直接插入排序在所有排序方法中是最简单的排序方法之一。

  • 时间复杂度：遍历比较时间复杂度是每次O(n),交换的时间复杂度每次也是O(n),那么n次总共的时间复杂度就是O(n^2)
  • 基本思想：从前往后，按照大小顺序排序，从第一个开始，如果前面有比自己大的，就继续寻找，直到前面的数据比自己小，插入改位置。直到最后一个元素插入完成。
具体步骤：

img

方式1:

  1. 从第一个元素开始，该元素可以认为已经被排序
  2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
  3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
  4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
  5. 将新元素插入到该位置后
  6. 重复步骤2~5

方式2:

image-20210118184718867

  • 选取当前位置(当前位置前面已经有序) 目标就是将当前位置数据插入到前面合适位置。
  • 向前枚举或者二分查找，找到待插入的位置。
  • 移动数组，赋值交换，达到插入效果。
1
def insert_sort(arr):
2
    """
3
    快速排序
4
    1. 选取当前位置(当前位置前面已经有序) 目标就是将当前位置数据插入到前面合适位置。
5
    2. 向前枚举或者二分查找，找到待插入的位置。
6
    3. 移动数组，赋值交换，达到插入效果。
7
    :param arr:
8
    :return:
9
    """
10
    if len(arr) == 0:
11
        return
12
    length = len(arr)
13
    for i in range(1, length):
14
        temp = arr[i]  # 取第二个值为当前值
15
        for j in range(i - 1, -1, -1):  # 循环 i-1 个元素
16
            if arr[j] > temp:  # 如果 比 temp 大，则 将arr[j] 赋值给 arr[j+1], arr[j] 赋值为temp
17
                arr[j + 1], arr[j] = arr[j], temp
18
                print(arr)  # 打印当前需要排序的数组
19
            else:  # j 前面的数据都是排好序的，所以，只要arr[j]比 temp小，则 j-- 都比 temp 小
20
                break
21
                
22
def insert_sort2(arr):
23
    """
24
    1. 从第一个元素开始，该元素可以认为已经被排序
25
    2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
26
    3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
27
    4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
28
    5. 将新元素插入到该位置后
29
    6. 重复步骤2~5
30
    :param arr:
31
    :return:
32
    """
33
    length = len(arr)
34
    if length == 0:
35
        return
36
    for i in range(1, length):
37
        # 后一个元素和前一个元素比较
38
        # 如果比前一个小
39
        if arr[i] < arr[i - 1]:
40
            # 将这个数取出
41
            temp = arr[i]
42
            index = 1  # 保存下标
43
            # 从后往前依次比较每个元素
44
            for j in range(i - 1, -1, -1):
45
                # 和比取出元素大的元素交换
46
                if arr[j] > temp:
47
                    arr[j + 1] = arr[j]
48
                    index = j
49
                else:
50
                    break
51
            # 插入元素
52
            arr[index] = temp

希尔排序

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序.

image-20210119194526042

算法思想
  1. 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
  2. 按增量序列个数k，对序列进行k 趟排序；
  3. 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

#####　原理

img

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

  1. 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率
  2. 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。
步骤

每次以一定步长(就是跳过等距的数)进行排序，直至步长为1.

步长使用的是Donald Shell的建议，另外步长还可以使用Sedgewick提出的(1, 5, 19, 41, 109,…)。
也可以使用斐波那契数列除去0和1将剩余的数以黄金分区比的两倍的幂进行运算得到的数列。

代码实现
1
def shell_sort(arr):
2
    """
3
    希尔排序:
4
    1. 计算初始步长 (arr的长度除于 2)
5
    2. 当步长 大于 1时,循环处理
6
    3. 以步长为初始值,结束值为数组的长度,循环arr
7
    4. 当 当前值 i - d 大于 等于 0时,按照插入法 排序 步长为 d 的数据
8
    5. 修改步长
9
    :param arr:
10
    :return:
11
    """
12
    length = len(arr)  # 数组的长度
13
    # 初始的步长 ('//' 整除,返回整数结果)
14
    d = length // 2
15
    while d >= 1:  # 当步长 大于等于 1 时
16
        for i in range(d, length, 1):
17
            temp = arr[i]
18
            j = i - d
19
            while j >= 0:  # 按照指定的步长将数据按照插入法排序
20
                if arr[j] > temp:
21
                    arr[j + d] = arr[j]
22
                    arr[j] = temp
23
                j -= d
24
        d //= 2  # 步长再次折半
25
      
26
def shell_sort2(arr):
27
    """
28
    1.选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
29
    2.按增量序列个数k，对序列进行k 趟排序；
30
    3.每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
31
    :param arr:
32
    :return:
33
    """
34
    length = len(arr)
35
    # 增量序列计算逻辑
36
    h = 1
37
    while h < length // 3:
38
        h = 3 * h + 1
39
    # 如果增量序列大于 1
40
    while h >= 1:
41
        # 以增量序列为开始，对数组进行排序
42
        for i in range(h, length - 1, 1):
43
            j = i
44
            # 对截取数据按照 步长 h 进行排序
45
            while j >= h:
46
                if arr[j] < arr[j - h]:
47
                    arr[j - h], arr[j] = arr[j], arr[j - h]
48
                j -= h
49
        # 调整增量大小
50
        h = h // 3

选择类

简单选择类排序

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理大致是将后面的元素最小元素一个个取出然后按顺序放置。

img

算法思想

  1. 在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
  2. 从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾
  3. 以此类推，直到所有元素均排序完毕

代码实现

1
def selection_sort(arr):
2
    """
3
    选择排序
4
    1. 在未排序序列中找到最小（最大）元素，存放到排序序列的起始位置
5
    2. 然后再从剩余的未排序序列中继续寻找最小（最大）元素，然后放到已排序序列的末尾
6
    3.重复第二步，直到所有元素排序完成
7
    :param arr:
8
    :return:
9
    """
10
    length = len(arr)
11
12
    for i in range(0, length):
13
        min = i
14
        for j in range(i + 1, length):
15
            if arr[j] < arr[min]:
16
                min = j
17
                arr[min], arr[i] = arr[i], arr[min]
18
    return arr
19
20
21
def selection_sort2(arr):
22
    length = len(arr)
23
    for i in range(0, length):
24
        min = i
25
        temp = arr[i]
26
        # 找出最小元素的 索引值
27
        for j in range(i + 1, length):
28
            if arr[j] < arr[min]:
29
                min = j
30
        # temp = arr[i]
31
        # arr[i] = arr[min]
32
        # arr[min] = temp
33
        arr[i], arr[min] = arr[min], temp
34
    return arr

堆排序

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

最大堆

假设有一个数组 int[] arr = {8,9,10,11,12,13,14};

用它来构建最大堆

基本思路
  1. 最大堆或最小堆都是完全二叉树，利用这个性质，先按照数组顺序构建最简单的完全二叉树
  2. 从 最后一个节点的父节点（arr.length / 2 - 1） 开始 逐次调整位置，开始构建最大堆
    1. 若父节点小于左节点，父节点与左节点互换，继续调整
    2. 若父节点小于右节点，父节点与右节点互换（注意是经过2.1），继续调整
构建示意图

image-20210121092704791

构建最大堆源代码
1
public static int[] buildHeap(int[] arr) {
2
        //最后一个非叶子节点： arr.length/2-1
3
        int index = arr.length / 2 - 1;
4
        for (int i = index; i >= 0; i--) {
5
            shiftDown(arr, i, arr.length);
6
        }
7
        System.out.println("输出最大堆："+ Arrays.toString(arr));
8
        return arr;
9
    }
10
11
    /**
12
     * 调整堆结构
13
     *
14
     * @param arr
15
     * @param index
16
     * @param size  size 的值必须大于1。 如果小于等于1 则 不会改变任何结构
17
     */
18
    public static void shiftDown(int[] arr, int index, int size) {
19
        //当前节点的左侧孩子节点
20
        int leftChild = index * 2 + 1;
21
        // 当前节点的右侧孩子节点
22
        int rightChild = index * 2 + 2;
23
        //临时变量，存储当前索引位置
24
        int temp = index;
25
        if (leftChild < size && arr[index] < arr[leftChild]) {
26
            index = leftChild;
27
        }
28
        if (rightChild < size && arr[index] < arr[rightChild]) {
29
            index = rightChild;
30
        }
31
        if (temp != index) { //说明父节点小于孩子节点，需要调换位置
32
            swap(arr, index, temp);
33
            // 交换后继续向下调整,以index为父节点，继续向下调整
34
            shiftDown(arr, index, size);
35
        }
36
    }
37
38
    /**
39
     * 交换 arr中 索引 i 和 j 位置对应的 值
40
     *
41
     * @param arr
42
     * @param i
43
     * @param j
44
     */
45
    private static void swap(int[] arr, int i, int j) {
46
        int temp = arr[i];
47
        arr[i] = arr[j];
48
        arr[j] = temp;
49
    }
50
51
   /**
52
     * 堆排序：
53
     * 1)将已经建立好的大顶堆，每次取出根节点，即最大值。
54
     * 2)将最后一个节点的值赋给根节点，重新构建大顶堆。
55
     * 3)删除最后节点的数据
56
     */
57
    public static int[] heapSort(int[] arr) {
58
        for (int i = arr.length - 1; i >= 1; i--) {
59
            swap(arr, 0, i);
60
            System.out.println("交换位置后：" + Arrays.toString(arr));
61
            // 从根节点向下调整，每次取出一个数值，集合长度逐渐减小
62
            shiftDown(arr, 0, i);
63
            System.out.println("调整后：" + Arrays.toString(arr));
64
        }
65
        return arr;
66
    }
67
68
static int[] arr = {8, 9, 7, 6, 5, 10, 11, 12, 13, 14};
69
70
    public static void main(String[] args) {
71
        //构建大顶堆
72
        int[] bigHeap = buildHeap(arr);
73
        heapSort(bigHeap);
74
        System.out.println("升序排列结果：");
75
        for (int i = 0; i < arr.length; i++) {
76
            System.out.print(arr[i] + " ");
77
        }
78
    }

堆排序

基本思路

1)将已经建立好的大顶堆，每次取根节点，即最大值，并与最后的节点交换。
2)重新构建大顶堆，注意索引是从 int i = arr.length - 1 开始的，重建大顶堆时，实际上相当于删除了最后一个元素，即删除了刚刚完成第一步交换的最大值。对于数组来说，刚好是将最大值，固定在最后的索引上。

算法思想：

  1. 将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
  2. 将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
  3. 由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。

步骤

  1. 创建最大堆:将堆所有数据重新排序，使其成为最大堆
  2. 最大堆调整:作用是保持最大堆的性质，是创建最大堆的核心子程序
  3. 堆排序:移除位在第一个数据的根节点，并做最大堆调整的递归运算
1
def heap_sort(arr):
2
    # 创建最大堆
3
    for start in range((len(arr) - 2) // 2, -1, -1):
4
        shift_down(arr, start, len(arr) - 1)
5
        print('第一次：%s' % arr)
6
    # 堆排序
7
    for end in range(len(arr) - 1, 0, -1):
8
        arr[0], arr[end] = arr[end], arr[0]
9
        print('排序后调整前：%s' % arr)
10
        shift_down(arr, 0, end - 1)
11
        print('堆排序后调整后：%s' % arr)
12
    return arr
13
14
15
def shift_down(arr, start, end):
16
    """
17
    最大堆调整
18
    :param arr:
19
    :param start:
20
    :param end:
21
    :return:
22
    """
23
    root = start
24
    while True:
25
        child = 2 * root + 1
26
        if child > end:
27
            break
28
        if child + 1 <= end and arr[child] < arr[child + 1]:
29
            child += 1
30
        if arr[root] < arr[child]:
31
            arr[root], arr[child] = arr[child], arr[root]
32
            root = child
33
        else:
34
            break

并归类

归并排序

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

img

  • 时间复杂度: O(nlogn)
  • 稳定的算法(排序过程中大小相同的元素能够保持排序前的顺序，3212升序排序结果是1223，排序前后两个2的顺序不变)
  • 归并排序需要O(n)的辅助空间，而与之效率相同的快排和堆排分别需要O(logn)和O(1)的辅助空间，在同类算法中归并排序的空间复杂度略高

(1）稳定性
　归并排序是一种稳定的排序。

（2）存储结构要求
　可用顺序存储结构。也易于在链表上实现。
（3）时间复杂度
　对长度为n的文件，需进行 lgn趟二路归并，每趟归并的时间为O(n)，故其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlgn)。
（4）空间复杂度
　 需要一个辅助向量来暂存两有序子文件归并的结果，故其辅助空间复杂度为O(n)，显然它不是就地排序。

算法思想

无序 -> 部分有序 -> 整体有序

  1. 把长度为n的输入序列分成两个长度为n/2的子序列；
  2. 对这两个子序列分别采用归并排序；
  3. 将两个排序好的子序列合并成一个最终的排序序列。
代码实现
1
def merger_sort(arr):
2
    """
3
    归并排序:
4
    ①进行两两归并使记录关键字有序，
5
    ②得到 n/2 个长度为 2 的有序子表；
6
    ③重复第②步直到所有记录归并成一个长度为 n 的有序表为止。
7
    此算法的实现不像图示那样简单，现分三步来讨论。首先从宏观上分析，首先让子表表长 L=1 进行处理；
8
    不断地使 L=2*L ，进行子表处理，直到 L>=n 为止，把这一过程写成一个主体框架函数 mergesort 。
9
    :param arr:
10
    :return:
11
    """
12
    # sort(arr, 0, len(arr) - 1)
13
    sort2(arr)
14
15
16
def sort2(arr):
17
    """
18
    非递归方式
19
    :param arr:
20
    :return:
21
    """
22
    length = len(arr)
23
    # 步长
24
    step = 2
25
    while step <= length:
26
        i = 0  # 起始位置
27
        while (step + i) <= length:
28
            # 需要合并的数组长度
29
            curr_length = i + step
30
            # 中间索引
31
            center = i + step // 2 - 1
32
            merge(arr, i, center, curr_length - 1)
33
            i += step
34
        # 处理末尾残余部分
35
        merge(arr, i, i + step // 2 - 1, length - 1)
36
        # 调整步长
37
        step *= 2
38
    # 最后再从头处理一遍
39
    merge(arr, 0, step // 2 - 1, length - 1)
40
41
42
def sort(arr, left, right):
43
    """
44
    采用递归方式排序
45
    :param arr:
46
    :param left:
47
    :param right:
48
    :return:
49
    """
50
    if left >= right:
51
        return
52
    # 找出中间索引
53
    center = (left + right) // 2
54
    # 对左边数组进行递归
55
    sort(arr, left, center)
56
    # 对右边数组进行递归
57
    sort(arr, center + 1, right)
58
    #  合并
59
    merge(arr, left, center, right)
60
61
62
def merge(arr, left, center, right):
63
    """
64
    合并操作
65
    :param arr: 数组对象
66
    :param left: 左数组的第一个元素的索引
67
    :param center: 左数组的最后一个元素的索引, center+1 是右数组的第一个元素的索引
68
    :param right: 右数组的最有一个元素的索引
69
    :return:
70
    """
71
    # 临时数组
72
    temp_arr = [None] * len(arr)
73
    # 右数组第一个元素的索引
74
    mid_new = center + 1
75
    # third 记录临时数组的索引
76
    third = left
77
    # 缓存左侧数组第一个元素的索引
78
    temp = left
79
    while left <= center and mid_new <= right:
80
        # 从两个数组中取出最小的放到临时数组中
81
        if arr[left] <= arr[mid_new]:
82
            temp_arr[third] = arr[left]
83
            left += 1
84
        else:
85
            temp_arr[third] = arr[mid_new]
86
            mid_new += 1
87
        third += 1
88
89
    # 剩余部分依次放入临时数组(以下两个 while 实际上只会执行一个)
90
    while mid_new <= right:
91
        temp_arr[third] = arr[mid_new]
92
        third += 1
93
        mid_new += 1
94
    while left <= center:
95
        temp_arr[third] = arr[left]
96
        left += 1
97
        third += 1
98
    # 将临时数组中的内容拷贝回原数组(原 left - right 范围内的内容被拷贝回原数组)
99
    while temp <= right:
100
        arr[temp] = temp_arr[temp]
101
        temp += 1
102
103
    print('合并后:%s' % arr)

非比较排序

桶排

计数排序

计数排序统计小于等于该元素值的元素的个数i，于是该元素就放在目标数组的索引i位（i≥0）。

计数排序基于一个假设，待排序数列的所有数均为整数，且出现在（0，k）的区间之内。

如果 k（待排数组的最大值） 过大则会引起较大的空间复杂度，一般是用来排序 0 到 100 之间的数字的最好的算法，但是它不适合按字母顺序排序人名。

计数排序不是比较排序，排序的速度快于任何比较排序算法。

算法思想
  1. 找出待排序的数组中最大和最小的元素；
  2. 统计数组中每个值为 i 的元素出现的次数，存入数组 C 的第 i 项；
  3. 对所有的计数累加（从 C 中的第一个元素开始，每一项和前一项相加）；
  4. 填充目标数组：将每个元素 i 放在新数组的第 C[i] 项，每放一个元素就将 C[i] 减去 1；

Image

算法步骤

第一步：找出原数组中元素值最大的，记为max。

第二步：创建一个新数组count，其长度是max加1，其元素默认值都为0。

第三步：遍历原数组中的元素，以原数组中的元素作为count数组的索引，以原数组中的元素出现次数作为count数组的元素值。

第四步：创建结果数组result，起始索引index。

第五步：遍历count数组，找出其中元素值大于0的元素，将其对应的索引作为元素值填充到result数组中去，每处理一次，count中的该元素值减1，直到该元素值不大于0，依次处理count中剩下的元素。

第六步：返回结果数组result

代码实现
1
def count_sort(arr):
2
    """
3
    计数排序:
4
    1. 找出待排序的数组中最大和最小的元素
5
    2. 统计数组中每个值为i的元素出现的次数，存入数组 C 的第 i 项
6
    3. 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
7
    4. 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1
8
    :param arr:
9
    :return:
10
    """
11
    max = 0
12
    min = 1000
13
    # 获取最大值和最小值
14
    for i in arr:
15
        if i < min:
16
            min = i
17
        if i > max:
18
            max = i
19
    # 创建数组C
20
    count_length = max - min + 1
21
    count = [0] * count_length
22
    for index in arr:
23
        count[index - min] += 1
24
    index = 0
25
    # 添值
26
    # 循环 max-min+ 1 次(即:count 的数组长度次)
27
    for a in range(count_length):
28
        for c in range(count[a]): # 填充 count[a] > 0 的值, 而且循环 count[a] 次
29
            # 值为  a + min
30
            arr[index] = a + min
31
            index += 1
32
    return arr

桶排序

将值为i的元素放入i号桶，最后依次把桶里的元素倒出来。

桶排序是计数排序的扩展版本，计数排序可以看成每个桶只存储相同元素，而桶排序每个桶存储一定范围的元素，通过映射函数，将待排序数组中的元素映射到各个对应的桶中，对每个桶中的元素进行排序，最后将非空桶中的元素逐个放入原序列中。

桶排序需要尽量保证元素分散均匀，否则当所有数据集中在同一个桶中时，桶排序失效。

img

复杂度分析

  • 时间复杂度: 时间复杂度：O(N + C)

  • 空间复杂度: 额外空间复杂度：O(N + M)

  • 稳定性:桶排序的稳定性取决于桶内排序使用的算法。

算法思想
  1. 设置一个定量的数组当作空桶子。
  2. 寻访序列，并且把项目一个一个放到对应的桶子去。
  3. 对每个不是空的桶子进行排序。
  4. 从不是空的桶子里把项目再放回原来的序列中。

Image

代码实现
1
def bucket_sort(arr, bucket_size):
2
    """
3
    桶排序
4
    1.设置一个定量的数组当作空桶子。
5
    2.寻访序列，并且把项目一个一个放到对应的桶子去。
6
    3.对每个不是空的桶子进行排序。
7
    4.从不是空的桶子里把项目再放回原来的序列中。
8
    :param arr:
9
    :param bucket_size:
10
    :return:
11
    """
12
    if len(arr) == 0:
13
        return arr
14
    min = arr[0]
15
    max = arr[0]
16
    # 获取原始数据中的最大值和最小值
17
    for item in arr:
18
        if item < min:
19
            min = item
20
        elif item > max:
21
            max = item
22
    # 初始化桶
23
    default_bucket_size = 5  # 桶的初始化大小为 5
24
    # 桶的最终大小
25
    bucket_size = bucket_size or default_bucket_size
26
    # 桶的数量
27
    bucket_count = (max - min) // bucket_size + 1
28
    # 创建空桶
29
    buckets = [[] * bucket_size for _ in range(bucket_count)]
30
    # 利用映射函数将数据分配到各个桶中
31
    for i in range(len(arr)):
32
        index = (arr[i] - min) // bucket_size
33
        buckets[index].append(arr[i])
34
35
    # 清空原始数组
36
    arr.clear()
37
    # 对每个桶进行插入排序
38
    for bucket in buckets:
39
        insert_sort(bucket)  # 插入排序
40
        # 将排序好的 数据插入到 arr中
41
        for item in bucket:
42
            arr.append(item)
43
    return arr
44
45
46
def bucket_sort2(arr):
47
    max_value = arr[0]
48
    min_value = arr[0]
49
    # 获取最大值和最小值
50
    for i in arr:
51
        min_value = min(i, min_value)
52
        max_value = max(i, max_value)
53
    print('最大值: %s' % max_value)
54
    print('最小值:%s' % min_value)
55
56
    # 计算 桶的数量
57
    bucket_num = (max_value - min_value) // len(arr) + 1
58
    # 创建桶
59
    buckets = [[] for _ in range(bucket_num)]
60
    # 将每个元素按照一定的规则放到对应的桶中
61
    for i in range(len(arr)):
62
        # 桶的位置 index = (当前值-最小值)除以 数组长度 求整
63
        index = (arr[i] - min_value) // len(arr)
64
        buckets[index].append(arr[i])
65
66
    # 将原始数组清空
67
    arr.clear()
68
    # 对每个桶中的元素排序
69
    # 将桶中的元素放到原始数组
70
    for bucket in buckets:
71
        bubble_sort(bucket)
72
        for item in bucket:
73
            arr.append(item)
74
    return arr

基数排序

一种多关键字的排序算法，可用桶排序实现

基数排序(Radix Sort)是在桶排序的基础上发展而来的，两种排序都是分配排序的高级实现。分配排序(Distributive Sort)的基本思想：排序过程无须比较关键字，而是通过“分配”和“收集”过程来实现排序。它们的时间复杂度可达到线性阶：O(n)。

Image

原理分析

image-20210122154759222

上面这幅图，或许你已经在其他的博客里见到过。这是一个很好的引导跟说明。在基数排序里，我们需要一个很大的二维数组，二维数组的大小是 （10 * n）。10 代表的是我们每个元素的每一位都有 10 种可能，也就是 10 进制数。在上图中，我们是以每个数的个位来代表这个数，于是，5428 就被填充到了第 8 个桶中了。下次再进行填充的时候，就是以十位进行填充，比如 5428 在此时，就会选择以 2 来代表它。

img

算法优化

在算法的原理中，我们是以一张二维数组的表来存储这些无序的元素。使用二维数组有一个很明显的不足就是二维数组太过稀疏。数组的利用率为 10%。
在寻求优化的路上，我们想到一种可以压缩空间的方法，且时间复杂度并没有偏离得太厉害。那就是设计了两个辅助数组，一个是 count[]，一个是 bucket[]。count 用于记录在某个桶中的最后一个元素的下标，然后再把原数组中的元素计算一下它应该属于哪个“桶”，并修改相应位置的 count 值。直到最大数的最高位也被添加到桶中，或者说，当所有的元素都被被在第 0 个桶中，基数排序就结束了。
优化后的原理图如下：

img

算法思想
  1. 取得数组中的最大数，并取得位数；
  2. arr为原始数组，从最低位开始取每个位组成radix数组；
  3. 对radix进行计数排序（利用计数排序适用于小范围数的特点）
代码实现
python 实现
1
def item_len(item):
2
    """
3
    计算一个数字共有多少位
4
    :param item:
5
    :return:
6
    """
7
    d = 1  # 位数,默认为1
8
    precision = 10  # 精度
9
    while item >= precision:
10
        item %= 10
11
        d += 1
12
    return d
13
14
15
def max_lenght(arr):
16
    """
17
    一个数组中,最大数的位数
18
    :param arr:
19
    :return:
20
    """
21
    max_len = 0
22
    length = len(arr)
23
    for i in range(length):
24
        current_len = item_len(arr[i])
25
        max_len = max(current_len, max_len)
26
    return  max_len
27
28
def get_digit(x, d):
29
    """
30
    获取 x 这个数的 d 位数上的数字
31
     比如获取 123 的 0 位数,结果返回 3
32
    :param x:
33
    :param d:
34
    :return:
35
    """
36
    a = [1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000]
37
    # 求商 取余
38
    return (x // a[d]) % 10
39
40
41
def do_radix_sort(arr, digit, max_len):
42
    """
43
    基数排序的核心算法
44
    :param arr:
45
    :param digit:
46
    :param max_len:
47
    :return:
48
    """
49
    if digit > max_len:
50
        return arr
51
    radix = 10  # 基数
52
    arr_len = len(arr)
53
    # 计数 arr中元素的个数(计数法)
54
    count = [0] * radix
55
    # 桶,存放元素
56
    bucket = [0] * arr_len
57
    #  统计将数组中的数字分配到桶中后，各个桶中的数字个数
58
    for i in range(arr_len):
59
        # 每一位的数字
60
        digit_data = get_digit(arr[i], digit)
61
        count[digit_data] += 1
62
    # 将各个桶中的数字个数，转化成各个桶中最后一个数字的下标索引
63
    for i in range(1, radix):
64
        count[i] = count[i] + count[i - 1]
65
    #  将原数组中的数字分配给辅助数组 bucket
66
    for j in range(arr_len - 1, 0, -1):
67
        num = arr[j]
68
        d = get_digit(num, digit)
69
        bucket[count[d] - 1] = num
70
        count[d] -= 1
71
72
    return do_radix_sort(bucket, digit + 1, max_len)
73
74
75
def radix_sort2(arr):
76
    """
77
    基数排序
78
    :param arr:
79
    :return:
80
    """
81
    length = len(arr)
82
    if length == 0:
83
        return arr
84
    # 数组中元素的最大位数
85
    max_len = max_lenght(arr)
86
    return do_radix_sort(arr, 0, max_len)
87
88
89
####################################################地二种 方式(非递归)####################################
90
def max_bit(arr, n):
91
    """
92
    辅助函数,求数数组中元素的最大位数
93
    :param arr:
94
    :param n: 数组的长度
95
    :return:
96
    """
97
    # 求出最大值
98
    max_value = arr[0]
99
    # 获取最大值和最小值
100
    for i in arr:
101
        max_value = max(i, max_value)
102
    # 求位数
103
    d = 1  # 位数,默认为1
104
    precision = 10  # 精度
105
    while max_value >= precision:
106
        max_value //= 10
107
        d += 1
108
    return d
109
110
111
def radix_sort(arr):
112
    """
113
    基数排序
114
    1. 取得数组中的最大数，并取得位数；
115
    2. arr为原始数组，从最低位开始取每个位组成radix数组；
116
    3. 对radix进行计数排序（利用计数排序适用于小范围数的特点）
117
    :param arr:
118
    :return:
119
    """
120
    length = len(arr)
121
    # 最大位数
122
    d = max_bit(arr, length)
123
    temp = [0] * length
124
    # count 为 10 的数组,原因是10进制
125
    count = [0] * 10  # 计数器
126
    radix = 1
127
    # 进行 d次排序
128
    for i in range(1, d + 1):
129
        # 每次分派前清空计数器
130
        for j in range(10):
131
            count[j] = 0
132
        for j in range(length):
133
            # 统计每个桶中的记录数
134
            k = (arr[j] // radix) % 10
135
            count[k] += 1
136
        # 将各个桶中的数字个数，转化成各个桶中最后一个数字的下标索引
137
        for j in range(1, 10):
138
            # 将temp 中的位置依次分配给每个桶
139
            count[j] = count[j - 1] + count[j]
140
        # 将所有桶中记录依次放到temp中
141
        for j in range(length - 1, -1, -1):
142
            k = (arr[j] // radix) % 10
143
            temp[count[k] - 1] = arr[j]
144
            count[k] -= 1
145
146
        # 将临时数组的内容复制到 arr中
147
        for j in range(0, length, 1):
148
            arr[j] = temp[j]
149
        radix = radix * 10
150
    temp.clear()
151
    count.clear()
152
    return arr
java 实现
1
import org.algorithm.array.sort.interf.Sortable;
2
3
/**
4
 * 基数排序
5
 */
6
public class RadixSort implements Sortable {
7
    
8
    @Override
9
    public int[] sort(int[] array) {
10
        if (array == null) {
11
            return null;
12
        }
13
        
14
        int maxLength = maxLength(array);
15
        
16
        return sortCore(array, 0, maxLength);
17
    }
18
19
    private int[] sortCore(int[] array, int digit, int maxLength) {
20
        if (digit >= maxLength) {
21
            return array;
22
        }
23
        
24
        final int radix = 10; // 基数
25
        int arrayLength = array.length;
26
        int[] count = new int[radix];
27
        int[] bucket = new int[arrayLength];
28
        
29
        // 统计将数组中的数字分配到桶中后，各个桶中的数字个数
30
        for (int i = 0; i < arrayLength; i++) {
31
            count[getDigit(array[i], digit)]++;
32
        }
33
        
34
        // 将各个桶中的数字个数，转化成各个桶中最后一个数字的下标索引
35
        for (int i = 1; i < radix; i++) {
36
            count[i] = count[i] + count[i - 1];
37
        }
38
        
39
        // 将原数组中的数字分配给辅助数组 bucket
40
        for (int i = arrayLength - 1; i >= 0; i--) {
41
            int number = array[i];
42
            int d = getDigit(number, digit);
43
            bucket[count[d] - 1] = number;
44
            count[d]--;
45
        }
46
        
47
        return sortCore(bucket, digit + 1, maxLength);
48
    }
49
    
50
    /*
51
     * 一个数组中最大数字的位数
52
     * 
53
     * @param array
54
     * @return
55
     */
56
    private int maxLength(int[] array) {
57
        int maxLength = 0;
58
        int arrayLength = array.length;
59
        for (int i = 0; i < arrayLength; i++) {
60
            int currentLength = length(array[i]);
61
            if (maxLength < currentLength) {
62
                maxLength = currentLength;
63
            }
64
        }
65
        
66
        return maxLength;
67
    }
68
    
69
    /*
70
     * 计算一个数字共有多少位
71
     * 
72
     * @param number
73
     * @return
74
     */
75
    private int length(int number) {
76
        return String.valueOf(number).length();
77
    }
78
    
79
    /*
80
     * 获取 x 这个数的 d 位数上的数字
81
     * 比如获取 123 的 0 位数,结果返回 3
82
     * 
83
     * @param x
84
     * @param d
85
     * @return
86
     */
87
    private int getDigit(int x, int d) {
88
        int a[] = { 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000 };
89
        return ((x / a[d]) % 10);
90
    }
91
}
基数排序过程图
  • 如果我们的无序是 T = [ 2314, 5428, 373, 2222, 17 ]，那么其排序的过程就如下两幅所示。
    基数排序过程图-1

img

  • 基数排序过程图-2

img

复杂度分析

image-20210122154639300

其中，d 为位数，r 为基数，n 为原数组个数。 在基数排序中，因为没有比较操作，所以在复杂上，最好的情况与最坏的情况在时间上是一致的，均为 O(d * (n + r))。

参考

参考

赏

谢谢你请我吃糖果

支付宝
微信

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

身在井隅<br><br> 心想星光<br><br> 眼里有诗<br><br>自在远方