排序

一、选择排序

简介

因为每次都是选择一个最小的元素，因此被命名为：选择排序

步骤

1. 首先，从第一个元素到最后一个元素中，选择一个最小的元素；
2. 将这个元素和第一个元素进行交换，此时，第一个元素一定是所有数中最小的；
3. 之后，从第二个元素到最后一个元素中，选择一个最小的元素；
4. 将这个元素和第二个元素进行交换，此时，第二个元素一定是所有数中第二小的；
5. 重复以上操作；

时间复杂度和空间复杂度

实现

JavaScript

function SelectionSort(a) {
    // 获取 a 列表长度
    const n = a.length
    // 枚举每次选择的左端点 i，范围 0 到 n - 2
    for (let i = 0; i < n - 1; i++) {
        /**
         * 找到一个值最小的数的下标
         */
        // 对于每次选择，将 i 存储到变量 min 中
        let min = i
        // 遍历 i + 1 到 n - 1
        for (let j = i + 1; j < n; j++) {
            if (a[j] < a[min]) {
                min = j
            }
        }
        // 找到最小的数和第 i 个数进行交换
        [a[i], a[min]] = [a[min], a[i]]
        // 打印一下
        console.log(a)
    }
}

// 测试
const a = [8, 5, 6, 4, 3, 7, 10, 2]
SelectionSort(a)

// 输出
// [2, 5, 6, 4, 3, 7, 10, 8]
// [2, 3, 6, 4, 5, 7, 10, 8]
// [2, 3, 4, 6, 5, 7, 10, 8]
// [2, 3, 4, 5, 6, 7, 10, 8]
// [2, 3, 4, 5, 6, 7, 10, 8]
// [2, 3, 4, 5, 6, 7, 10, 8]
// [2, 3, 4, 5, 6, 7, 8, 10]

Python

def SelectionSort(a):
    # 获取 a 列表长度
    n = len(a)
    # 枚举每次选择的左端点 i，范围 0 到 n - 2
    for i in range(n - 1):
        """
        找到一个值最小的数的下标
        """
        # 对于每次选择，将 i 存储到变量 min 中
        min = i
        # 遍历 i + 1 到 n - 1
        for j in range(i + 1, n):
            if a[j] < a[min]:
                min = j
        # 找到最小的数和第 i 个数进行交换
        a[i], a[min] = a[min], a[i]
        # 打印一下
        print(a)

# 测试
a = [8, 5, 6, 4, 3, 7, 10, 2]
SelectionSort(a)

# 输出
# [2, 5, 6, 4, 3, 7, 10, 8]
# [2, 3, 6, 4, 5, 7, 10, 8]
# [2, 3, 4, 6, 5, 7, 10, 8]
# [2, 3, 4, 5, 6, 7, 10, 8]
# [2, 3, 4, 5, 6, 7, 10, 8]
# [2, 3, 4, 5, 6, 7, 10, 8]
# [2, 3, 4, 5, 6, 7, 8, 10]

二、冒泡排序

简介

通过不断比较相邻的元素，将数值大的元素向后冒，从而实现排序的过程。

步骤

• 首先，需要将第 1 个元素和第 2 个元素进行比较，如果前者大于后者，则进行交换
• 然后，比较第 2 个元素和第 3 个元素，如果前者大于后者，则进行交换
• 依此类推，直到最大的元素被移动到最后的位置
• 然后进行第 2 轮比较，直到次大的元素移动到倒数第 2 的位置
• 然后进行第 3 轮比较，直到第 3 大的元素移动到倒数第 3 的位置
• 最后，经过 n 轮的比较和交换后，一定可以保证所有元素都是升序排列的

时间复杂度和空间复杂度

实现

JavaScript

function BubbleSort(a) {
    // 获取 a 列表长度
    const n = a.length
    // i 代表本次冒泡数的右边界，它的取值是 n - 1 到 0
    // 由于是逆序枚举，所以步长为 -1
    for (let i = n - 1; i >= 0; i--) {
        // 内层循环用来比较相邻的元素
        for (let j = 0; j < i; j++) {
            // 这样本轮枚举完毕，第 i 个数一定是前面的数中最大的
            if (a[j] > a[j + 1]) {
                [a[j], a[j + 1]] = [a[j + 1], a[j]]
            }
        }
        // 打印 list
        console.log(a)
    }
}

// 测试
const a = [5, 6, 8, 4, 3, 7, 10, 2]
BubbleSort(a)

// 输出
// [5, 6, 4, 3, 7, 8, 2, 10]
// [5, 4, 3, 6, 7, 2, 8, 10]
// [4, 3, 5, 6, 2, 7, 8, 10]
// [3, 4, 5, 2, 6, 7, 8, 10]
// [3, 4, 2, 5, 6, 7, 8, 10]
// [3, 2, 4, 5, 6, 7, 8, 10]
// [2, 3, 4, 5, 6, 7, 8, 10]
// [2, 3, 4, 5, 6, 7, 8, 10]

Python

def BubbleSort(a):
    # 获取 a 列表长度
    n = len(a)
    # i 代表本次冒泡数的右边界，它的取值是 n - 1 到 0
    # 由于是逆序枚举，所以步长为 -1
    for i in range(n - 1, -1, -1):
        # 内层循环用来比较相邻的元素
        for j in range(0, i):
            # 这样本轮枚举完毕，第 i 个数一定是前面的数中最大的
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
        # 打印 list
        print(a)

# 测试
a = [5, 6, 8, 4, 3, 7, 10, 2]
BubbleSort(a)

# 输出
# [5, 6, 4, 3, 7, 8, 2, 10]
# [5, 4, 3, 6, 7, 2, 8, 10]
# [4, 3, 5, 6, 2, 7, 8, 10]
# [3, 4, 5, 2, 6, 7, 8, 10]
# [3, 4, 2, 5, 6, 7, 8, 10]
# [3, 2, 4, 5, 6, 7, 8, 10]
# [2, 3, 4, 5, 6, 7, 8, 10]
# [2, 3, 4, 5, 6, 7, 8, 10]

三、插入排序

简介

插入排序就是对前 i-1 个数已经有序的情况下，将第 i 个数插入到合适的位置

由于每次都是将元素插入有序数列中，故此命名：插入排序

步骤

• 首先，将第 2 个元素和第 1 个元素进行比较，如果第 2 个元素 <= 第 1 个元素，则将第 1 个元素向后移动，并且第 2 个元素执行插入，则前两个元素就保持有序了
• 然后进行第二轮比较，将第 3 个元素和依次和第 2 个元素、第 1 个元素进行比较，并且将第 3 个元素插入合适的位置，直到前 3 个元素保持有序
• 由于前 3 个元素已经有序，那么对于第 4 个元素，继续找到 1 个合适的位置，执行插入，就能保证前 4 个元素有序
• 迭代执行 n - 1 次以上的插入操作以后，一定可以保证所有元素都是升序排列的 时间复杂度和空间复杂度

时间复杂度和空间复杂度

实现

Python

def InsertionSort(a):
    # 获取 a 列表长度
    n = len(a)
    # 遍历枚举 1 到 n-1
    for i in range(1, n):
        # 对于当前枚举到的数，缓存到 x 中
        x = a[i]
        # 逆序判断前面 i-1 个数
        j = i - 1
        while j >= 0:
            if x <= a[j]:
                # 将 a[j] 向后移动
                a[j + 1] = a[j]
                # 继续判断前一个数
                j -= 1
            else:
                # 跳出循环
                break
        # 并且把 x 插入到对应位置
        a[j + 1] = x
        # 打印 list
        print(a)

# 测试
a = [8, 5, 6, 4, 3, 7, 10, 2]
InsertionSort(a)

# 输出
[5, 8, 6, 4, 3, 7, 10, 2]
[5, 6, 8, 4, 3, 7, 10, 2]
[4, 5, 6, 8, 3, 7, 10, 2]
[3, 4, 5, 6, 8, 7, 10, 2]
[3, 4, 5, 6, 7, 8, 10, 2]
[3, 4, 5, 6, 7, 8, 10, 2]
[2, 3, 4, 5, 6, 7, 8, 10]

四、归并排序

简介

归并排序就是利用分冶的思想，采用递归的形式，对元素进行排序

当我们有两个长度为 n 的有序数组时，可以通过两个指针的移动，在 O(n) 的时间复杂度内，快速将它们合并成一个有序数组。而这两个长度为 n 的有序数组，也是可以通过两个 n/2 的有序数组合并得来。因此，只要对数组不断进行分冶，就可以把一个无序数组变成有序

由于在数组拆分时用到了递归，而对数组组合的过程用到了合并，因此命名：归并排序

步骤

• 首先将数组拆分成左右两部分
• 对于左边部分，继续拆分成左右两部分，直到无法拆分，此时将最小单元左侧部分保持有序，最小单元右侧部分也保持有序，然后对排序后的这两部分进行合并
• 对于右侧部分，同左边部分一样拆分和合并
• 最后合并左右两部分的数组

时间复杂度和空间复杂度

实现

Python

def Merge(a, start, mid, end):
    # 临时列表
    tmp = []
    # 两个游标，分别从两段区间的起点开始
    l = start
    r = mid + 1
    # 当两个区间都未到达区间右端点时
    while l <= mid and r <= end:
        # 判断，将小的值插入临时列表
        if a[l] <= a[r]:
            tmp.append(a[l])
            # 对相应游标进行自增
            l += 1
        else:
            tmp.append(a[r])
            # 对相应游标进行自增
            r += 1
    # 当跳出循环时，将剩余的部分直接塞入临时列表
    tmp.extend(a[l : mid + 1])
    tmp.extend(a[r : end + 1])

    # 把临时列表的值，拷贝回原列表 a
    for i in range(start, end + 1):
        a[i] = tmp[i - start]
    # 打印本次合并结果
    print(start, end, tmp)

# 递归函数
def MergeSort(a, start, end):
    # 若待排序元素只有一个则直接返回
    if start == end:
        return
    # 否则计算出中点 mid
    mid = (start + end) // 2
    # 对左端点 start 到中点 mid 的元素执行一次归并排序
    MergeSort(a, start, mid)
    # 对中点 mid + 1 到右端点 end 的元素执行一次归并排序
    MergeSort(a, mid + 1, end)
    # 以上两次归并排序产生了两个有序数组，最后调用 Merge 进行归并排序
    Merge(a, start, mid, end)

# 测试
a = [8, 5, 6, 4, 3, 7, 10, 2]
MergeSort(a, 0, 7)

# 输出
0 1 [5, 8]
2 3 [4, 6]
0 3 [4, 5, 6, 8]
4 5 [3, 7]
6 7 [2, 10]
4 7 [2, 3, 7, 10]
0 7 [2, 3, 4, 5, 6, 7, 8, 10]

五、桶排序

简介

桶排序：首先生成一些桶，将数字散列到不同的桶中，对桶中的元素分别执行排序，再将元素依次取出的过程

核心思想：就是将待排序的数，散列到几个有序的桶中，每个桶里的数据，再单独进行排序

桶排序一般不会直接用，会做一些变形

步骤

• 首先建立 3 个桶，然后遍历数字
• 将所有数字分散到 3 个桶中，并且保证第 2 个桶中的所有元素 > 第 1 个桶中的所有元素，第 3 个桶中的所有元素 > 第 2 个桶中的所有元素
• 接下来对每个桶分别进行选择排序，待到 3 个桶都有序以后，再将元素依次取出，这样整个序列就排好序了

时间复杂度和空间复杂度

实现

Python

# 选择排序
def SelectionSort(a):
    n = len(a)
    for i in range(0, n):
        min = i
        for j in range(i + 1, n):
            if a[j] < a[min]:
                min = j
        a[i], a[min] = a[min], a[i]

# 桶排序
def BucketSort(a):
    # 首先确定列表元素最小值和最大值
    minV = min(a)
    maxV = max(a)
    # 定义桶的数量
    bucketCount = 3
    # 生成 3 个桶
    bucket = [[], [], []]
    # 计算每个桶不同数字的元素个数
    perBucket = (maxV - minV + bucketCount) // bucketCount

    # 遍历原列表
    for num in a:
        # 根据元素的值，选择一个合适的桶
        bucketIndex = (num - minV) // perBucket
        # 把当前元素放入这个桶中
        bucket[bucketIndex].append(num)

    # 遍历每个桶，执行选择排序
    for i in range(bucketCount):
        SelectionSort(bucket[i])

    # 遍历每个桶，对桶中排好序的元素，依次放回原列表
    idx = 0
    for i in range(bucketCount):
        for v in bucket[i]:
            a[idx] = v
            idx += 1

    # 打印桶信息
    print(bucket)
    # 打印排序信息
    print(a)

# 测试
a = [7, 11, 5, 9, 8, 6, 3, 12, 1, 10, 4, 2]
BucketSort(a)

# 输出
[[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

思考

• 桶内排序使用什么排序最好呢？
• 桶的数量又该如何取舍呢？