目录

目录

目录

算法介绍

基数排序，从左或从依次取出数列中每个数的每个数位上的数，根据取出的数，依次放到对应键值的块的最后面，然后按键值大小取出所有块，作为数列的新顺序，不断重复直到取出数列中所有数的所有数位上的数，最终的数列即为排好序的数列。
基数排序按取数方向分为两种：从左取每个数列上的数，为最高位优先（Most Significant Digit first, MSD）；从右取每个数列上的数，为最低位优先（Least Significant Digit first, LSD）。
下列以LSD为例。

算法介绍

快速排序，又称分割交换排序，是目前公认的最佳排序算法，核心思想是在数列中找一个数作为中介点，将比中介点小的数放到数列的左边（将不比中介点小的数放到数列的右边，两者是同时成立的，只要记住一个就好），把中介点放到相应的位置上，再对左右两边的数列进行同样操作直到两边最多包含一个数字。

视频演示

视频地址：https://www.bilibili.com/video/av18980345

算法介绍

归并排序，也叫合并排序，中心思想是将已排好序的两个或两个以上（常为两个）数列，合并成一个大的排序数列。为了保证这两个数列是已经排好序的，需要将数列对半分，直到该数列中只包含一个数字。

视频演示

视频地址：https://www.bilibili.com/video/av18980253

python 代码

算法介绍

希尔排序，用来解决插入排序的不足：每次只能将数据往后挪动一个位置，不能往后挪动到一个比较远的位置；用gap表示数据挪动的距离，在插入排序中，gap一直等于1，在最坏情况下，将第一个数挪动最后一个位置需要挪动 n-1 次，为方便理解，用“1位插入排序”表示“插入排序”。
希尔排序中先将gap设置为一个比较大的值，进行一次“gap位插入排序”，然后将gap变小，进行一次“gap位插入排序”，不断迭代，直到gap不大于0。
gap变化过程如下：首先将gap设置为 n//meta (meta通常为质数2)，然后下次将gap设置为 gap//meta，不断重复直到gap不大于0。gap更多变化方法

算法介绍

插入排序，依次取数组元素，与已排序的数据进行逐一比较，找到该元素的合适位置，放下该元素，直到完成排序。

视频演示

视频地址：https://www.bilibili.com/video/av18980488

python代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

#-*- coding: utf-8 -*-

# 升序
def insert_sort(data):
    n = len(data)
    # 外循环，依次拿出第 i 个数
    for i in range(1, n):
        cur_data = data[i]
        j=i-1
        # 内循环， 在已排序的数据中，找出当前数应该放的位置
        while j>=0 and cur_data<data[j]:
            data[j+1]=data[j] # 将大的数依次往后挪一位，为当前数腾位置
            j-=1
        data[j+1]=cur_data
    return data

if __name__ == '__main__':
    data = [7, 8, 5, 2, 4, 6, 3]
    sorted_data = insert_sort(data.copy())
    print("排序前：", data)
    print("排序后：", sorted_data)