【数据结构6】排序(Python)



2018年11月20日    Author:Guofei

文章归类: 0x80_数据结构与算法    文章编号: 561

版权声明:本文作者是郭飞。转载随意,但需要标明原文链接,并通知本人
原文链接:https://www.guofei.site/2018/11/20/sort.html


0. 评价标准

  1. 时间复杂度
  2. 空间复杂度
  3. 稳定性(指的是,当两个元素的Key相等时,排序之前前面的元素,在排序之后仍然出现在前面)
排序方法 原理 最好时间 平均时间 最坏时间 空间复杂度 稳定性
冒泡排序   O(n) O(n^2) O(n^2) O(1) 稳定
直接插入法 把元素逐一与已经排序的数据做比较,然后插入到合适位置 O(n) O(n^2) O(n^2) O(1) 稳定
希尔排序     O(n^1.333)   O(1) 不稳定
直接选择排序   O(n^2) O(n^2) O(n^2) O(1) 不稳定
快速排序   O(nlogn) O(nlogn) O(n^2) O(logn) 不稳定
归并排序   O(nlogn) O(nlogn) O(nlogn) O(n) 稳定
堆排序   O(nlogn) O(nlogn) O(nlogn) O(1) 不稳定
基数排序(链式队列)   O(mn) O(mn) O(mn) O(n) 稳定
基数排序(顺序队列)   O(mn) O(mn) O(mn) O(mn) 稳定

0.1 测试数据

我们把排序的对象抽象成 DataType 数据类型,之后会使用key作为排序的目标

class DataType:
    def __init__(self, key, value):
        self.key = key
        self.value = value

    def __repr__(self):
        return 'key:{key},value:{value}'.format(key=self.key, value=self.value)

data = [DataType(64, 'data1'), DataType(5, 'data2'), DataType(7, 'data3'), DataType(89, 'data4'),
     DataType(6, 'data5'),DataType(24, 'data6'), DataType(24, 'data7')]

1. 平方级复杂度

1.1 冒泡排序

BubbleSort

  1. 比较相邻的元素。如果第j个比第j+1个大,就交换它们两个;
  2. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对,这样在最后的元素应该会是最大的数;
  3. 针对所有的元素重复以上的步骤,除了最后一个;
  4. 重复步骤1~3,直到排序完成。
def bubble_sort1(arr):
    for i in range(len(arr) - 1):
        for j in range(len(arr) - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]


#%% 测试正确性              
import random

n = 10
arr = list(range(n))
random.shuffle(arr)

bubble_sort1(arr)

assert arr == list(range(n))

优化1:在若干次循环后,大概率已经是排序完成了,不需要把所有的循环都跑完。如果一轮循环都没变化,提前结束即可。

def bubble_sort2(arr):
    for i in range(len(arr) - 1):
        is_sorted = True
        for j in range(len(arr) - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                is_sorted = False

        if is_sorted:
            break

优化2:

  • 第i次循环后,最后i+1个元素一定是已经排好序的,之后不再参与变化(原始算法也有体现)。
  • 但,末尾已经排好序的数量可能多于 i+1 个。这就又有优化空间了
  • 方法:记录下每一轮排序后,最后一个发生元素交换的位置,这个元素之后的位置其实就是已经排好序的位置了,之后不再遍历
def bubble_sort3(arr):
    last_exchange_idx_tmp, last_exchange_idx = 0, len(arr) - 1
    for i in range(len(arr) - 1):
        for j in range(last_exchange_idx):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                last_exchange_idx_tmp = j
        last_exchange_idx = last_exchange_idx_tmp

优化3:鸡尾酒排序

  • 方法:交替进行,从左到右冒泡,下一轮从右往左冒泡,下下一轮又从左往右冒泡,以此类推
  • 适用场景:大多数元素已有序,但位置未必正确。例如 2,3,4,5,6,7,8,1,冒泡排序怎样都要8轮,但鸡尾酒排序只需要2轮

1.2 直接插入排序

InsertSort

  1. 从第一个元素开始,该元素可以认为已经被排序;
  2. 取出下一个元素,在已经排序的元素序列中从后向前扫描;
  3. 如果该元素(已排序)大于新元素,将该元素移到下一位置;
  4. 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置;
  5. 将新元素插入到该位置后;
  6. 重复步骤2~5。
def InsertSort(data):
    len_data = len(data)
    for i in range(len_data - 1):
        tmp = data[i + 1]
        j = i
        while (j > -1) and (tmp.key < data[j].key):
            data[j + 1] = data[j]
            j -= 1
        data[j + 1] = tmp
    return data
  • 时间复杂度
    • 最好复杂度。已经完成排序的序列,比较次数n-1,赋值次数2(n-1),复杂度$O(n)$
    • 最坏复杂度。原序列是反序排列,复杂度是$O(n^2)$
    • 平均复杂度。原序列随机排列,复杂度是$O(n^2/4)=O(n^2)$
  • 空间复杂度$O(1)$
  • 稳定性:稳定

1.3 希尔排序

为了减少数据移动操作。

ShellSort

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

1.4 直接选择排序

SelectSort 思路:每次在池子中选择一个最小的,放到序列前面

  1. 初始状态:无序区为R[1..n],有序区为空;
  2. 第i趟排序(i=1,2,3…n-1)开始时,当前有序区和无序区分别为R[1..i-1]和R(i..n)。该趟排序从当前无序区中-选出关键字最小的记录 R[k],将它与无序区的第1个记录R交换,使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区;
  3. n-1趟结束,数组有序化了。
def SelectSort(data):
    len_data = len(data)
    for i in range(len_data - 1):
        min_index = i
        for j in range(i + 1, len_data):  # 找到之后最小的
            if data[j].key < data[min_index].key:
                min_index = j
        if min_index != i:  # 如果最小的还是最开始的那个,不进行交换
            data[min_index], data[i] = data[i], data[min_index]
    return data

2. nlogn 复杂度

2.1 快速排序

下面这个图有些问题,不是快排。

QuickSort

快排思路

  1. 找一个基准值
  2. 使小于基准值的放到左边,大于基准值p的放到右边
  3. 上面得到了2个子列,对每个子列重复1,2

那么第二步如何实现呢?

  1. 两个指针指向两个端点,序号分别是i,j,后面的算法两个指针向中间移动
  2. 把基准值p拿出来,这样链上有个空位。例如,选左端点为p,这样i就是空位
  3. 右指针j向左移动,如果遇到比p小的,就填到空位i上。然后j就变成空位(看成空位,实际不必替换)。
  4. 如果i是空位,j向左移动;如果j是空位,i向右移动
  5. 直到i==j,然后把p填到i上
  6. 完成
def quick_sort(start_idx, end_idx, arr):
    if start_idx >= end_idx:
        return
    pivot_idx = partition(start_idx, end_idx, arr)
    quick_sort(start_idx, pivot_idx - 1, arr)
    quick_sort(pivot_idx + 1, end_idx, arr)


def partition(start_idx, end_idx, arr):
    # 这里用最左边为pivot;也可以先随机找一个值,与第一个交换,达成随机 pivot 的目的
    pivot = arr[start_idx]
    left, right = start_idx, end_idx
    hole = 0  # 0:代表 left 是空洞;1:代表right是空洞
    while left < right:
        if hole == 0:
            if arr[right] < pivot:
                arr[left] = arr[right]
                hole = 1
                left += 1
            else:
                right -= 1
        else:
            if arr[left] >= pivot:
                arr[right] = arr[left]
                hole = 0
                right -= 1
            else:
                left += 1
    arr[left] = pivot
    return left

2.2 堆排序

HeapSort

# 懒省事,做个弊,代价就是不能针对第0章定义的 DataType 进行排序了
import heapq
def HeapSort(data):
    heapq.heapify(data)  # O(n)
    res = []
    while data:
        res.append(heapq.heappop(data))
    return res

HeapSort([[3, 9], [5, 2], [7, 9], [1, 3], [3, 5]])

4. 归并排序

MergeSort

  1. 把长度为n的输入序列分成两个长度为n/2的子序列;
  2. 对这两个子序列分别采用归并排序(触发递归);
  3. 将两个排序好的子序列合并成一个最终的排序序列。

3. 线性复杂度

3.1 计数排序

适用情况:取值范围为有限个整数,例如,有100万个数字,它们都是 0 到 9 的整数,要求排序 算法:循环一次记数,再循环一次把数字填回去

def count_sort(arr):
    counter = [0 for _ in range(max(arr) + 1)]

    for val in arr:
        counter[val] += 1

    pointer = 0
    for i in range(len(arr)):
        if counter[pointer] == 0:
            pointer += 1
        arr[i] = pointer
        counter[pointer] -= 1


import random

n = 10000
arr = [random.randint(0, 9) for i in range(n)]
count_sort(arr)
assert arr == sorted(arr)

3.2 桶排序

算法步骤

  • 按照最大值最小值,创建n个桶
  • 遍历arr,把元素放入桶内
  • 每个桶内做排序

算法复杂度

  • 最好的情况:n个元素,均匀分到n个桶内。时间复杂度 On,空间复杂度 On
  • 最坏的情况:极不均匀,大多数元素被分到同一个桶内,退化为快排,时间复杂度为O(nlogn),空间复杂度为 On(比快排浪费)

3.3. 基数排序

RadixSort

6. 大规模数据排序

2G内存,如何给20亿个int数据(8G)排序?

  1. 把8G数据分4片,每一片做排序
  2. 对于每片,每次读取1个值,比较后输出
  3. 这个题目有4片,n片的话第二步可以用堆排序

参考文献

朱战立:《数据结构-使用C语言》,西安交通大学出版社
https://www.cnblogs.com/onepixel/articles/7674659.html


您的支持将鼓励我继续创作!