排序

分类

1. 时间复杂度（最差、平均、和最好性能）: 列表（list）的大小n。一般而言，好的性能是O()，坏的性能是O()。对于一个排序理想的性能是O(n)，但平均而言不可能达到。基于比较的排序算法对大多数输入而言至少需要O()。

2. 空间复杂度

3. 稳定性: 稳定排序算法会让原本有相等键值的纪录维持相对次序。也就是如果一个排序算法是稳定的，当有两个相等键值的纪录R和S，且在原本的列表中R出现在S之前，在排序过的列表中R也将会是在S之前。

4. 比较

时间复杂度

图片来自Wiki

空间复杂度

稳定性

稳定的

1. 冒泡排序（bubble sort）: O()
2. 鸡尾酒排序（cocktail sort）: O()
3. 计数排序（counting sort）: O(n+k)；需要O(n+k)额外空间

4. 桶排序（bucket sort）: O(n)；需要O(k)额外空间

5. 插入排序（insertion sort）: O()
6. 归并排序（merge sort）: O()；需要O(n)额外空间
7. 原地归并排序 : O(n\log^2 n)如果使用最佳的现在版本

8. 二叉排序树排序（binary tree sort）: O()期望时间；O()最坏时间；需要O(n)额外空间
9. 鸽巢排序（pigeonhole sort）: O(n+k)；需要O(k)额外空间

10. 基数排序（radix sort）: O(nk)；需要O(n)额外空间

11. 侏儒排序（gnome sort）: O()
12. 图书馆排序（library sort）: O()期望时间；O()最坏时间；需要()n额外空间
13. 块排序（block sort）: O()

不稳定的

1. 选择排序（selection sort）: O()
2. 希尔排序（shell sort）: O()如果使用最佳的现在版本
3. 克洛弗排序（Clover sort）: O(n)期望时间，O()最坏情况
4. 梳排序 : O()
5. 堆排序（heap sort）: O()
6. 平滑排序（smooth sort）: O()
7. 快速排序（quick sort）: O()期望时间，O()最坏情况；对于大的、随机数列表一般相信是最快的已知排序
8. 内省排序（introsort）: O()
9. 耐心排序（patience sort）: O()最坏情况时间，需要额外的O(n+k)空间，也需要找到最长的递增子序列（longest increasing subsequence）

不实用的

1. Bogo排序 : O()，最坏的情况下期望时间为无穷。
2. Stupid排序 : O(n^{3});递归版本需要O()额外存储器
3. 珠排序（bead sort）: O(n) 或 O(),但需要特别的硬件
4. 煎饼排序 : O(n),但需要特别的硬件

5. 臭皮匠排序（stooge sort）算法简单，但需要约的时间

比较

基于比较

1. 冒泡

2. 选择

3. 插入

4. 归并（递归实现）

5. 快速（递归实现）

6. 随机快速（递归实现）

7. 堆排序

不基于比较

1. 计数排序

2. 基数排序

3. 桶排序

代码实现

全部代码都已上传到Github

冒泡排序

BubbleSort

class BubbleSort(Base):
    def execute(self, L: List[int]) -> List[int]:
        for i in range(0, self.length):
            for j in range(i + 1, self.length):
                if L[i] > L[j]:
                    L[i], L[j] = L[j], L[i]
        return L

分析

比较和交换需要一个以常量为界的时间，我们称之为c。 （标准）Bubble Sort中有两个嵌套循环。 外循环正好运行N次迭代。 但内部循环运行变得越来越短：

1. 当 i = 0，（N-1）次迭代（比较和可能交换）时。

2. 当 i = 1，（N-2）次迭代时，...

3. 当 i =（N-2）时，1次迭代,

4. 当 i=（N-1），0迭代.

5. 因此，总迭代次数=（N-1）+（N-2）+ ... + 1 + 0 = N *（N-1）/ 2。

6. 总时间= c N （N-1）/ 2 = O（N ^ 2）。

鸡尾酒排序

鸡尾酒排序等于是冒泡排序的轻微变形。不同的地方在于从低到高然后从高到低，而冒泡排序则仅从低到高去比较序列里的每个元素。他可以得到比冒泡排序稍微好一点的性能，原因是冒泡排序只从一个方向进行比对（由低到高），每次循环只移动一个项目。

以序列（2,3,4,5,1）为例，鸡尾酒排序只需要访问一次序列就可以完成排序，但如果使用冒泡排序则需要四次。

CocktailSort

class CocktailSort(Base):
    def execute(self, L: List[int]) -> List[int]:
        flag = True
        for i in range(len(L) // 2):
            if flag:
                flag = False
                for j in range(i, len(L) - i - 1):
                    if L[j] > L[j+1]:
                        L[j], L[j+1] = L[j+1], L[j]
                        flag = True

                for j in range(len(L) - 1 - i, i, -1):
                    if L[j] < L[j-1]:
                        L[j], L[j-1] = L[j-1], L[j]
                        flag = True
            else:
                break
        return L

分析

1. 时间复杂度：鸡尾酒排序的效率还是很低的，两层循环，时间复杂度为 O(n^2) 。

2. 空间复杂度：由于只需要几个临时变量，所以空间复杂度为 O(1) 。

插入排序

InsertionSort

class InsertionSort(Base):
    def execute(self, L: List[int]) -> List[int]:
        for p in range(1, self.length):
            tmp = L[p]
            i = p
            while i > 0 and L[i-1] > tmp:
                L[i] = L[i-1]
                i = i-1
            L[i] = tmp
        return L

分析

外循环执行N-1次 内循环执行的次数取决于输入：

1. 在最好的情况下，数组已经排序并且（L[i-1] > tmp）总是为假所以不需要移位数据，并且内部循环运行在O（1），

2. 在最坏的情况下，数组被反向排序并且（L[i-1] > tmp）始终为真插入始终发生在数组的前端，并且内部循环以O（N）运行。

因此，最佳情况时间是O(N × 1) = O(N) ，最坏情况时间是O(N × N) = O(N2).

计数排序

当输入的元素是n个 0 到 k 之间的整数时，它的运行时间是 n+k。

由于用来计数的数组 C 的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。例如：计数排序是用来排序0到100之间的数字的最好的算法，但是它不适合按字母顺序排序人名。但是，计数排序可以用在基数排序算法中，能够更有效的排序数据范围很大的数组。

class CountingSort(Base):
    def execute(self, L: List[int]) -> List[int]:
        n = len(L)
        max_value = max(L)
        min_value = min(L)
        count = [0] * (max_value - min_value + 2) # 优化count数组空间

        for i in L:
            count[i] += 1

        sort_L = []
        for j in range(len(count)):
            if count[j] != 0:
                for y in range(count[j]):
                    sort_L.append(j)

        return sort_L

分析

1. 计数排序用待排序的数值作为计数数组（列表）的下标，统计每个数值的个数，然后依次输出即可。

2. 计数数组的大小取决于待排数据取值范围，所以对数据有一定要求，否则空间开销无法承受。

3. 计数排序只需遍历一次数据，在计数数组中记录，输出计数数组中有记录的下标，时间复杂度为O(n+k)。

4. 额外空间开销即指计数数组，实际上按数据值分为k类（大小取决于数据取值），空间复杂度O(k)。

桶排序

桶排序是计数排序的推广

将数组分到有限数量的桶里。每个桶再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序,在这里使用快排）

1. 设置一个定量的数组当作空桶子。

2. 寻访序列，并且把项目一个一个放到对应的桶子去。

3. 对每个不是空的桶子进行排序。

4. 从不是空的桶子里把项目再放回原来的序列中。

class BucketSort(Base):
    def execute(self, L: List[int]) -> List[int]:
        bucket_length = max(L) // 10 + 1
        buckets = [[] for i in range(0, bucket_length)]
        for i in L:
            buckets[i // 10].append(i)

        for i in buckets:
            quicksort = QuickSort(len(i))
            i = quicksort.execute(i)

        sort_L = []
        for i in buckets:
            if isinstance(i, list):
                for j in i:
                    sort_L.append(j)
            else:
                sort_L.append(i)

        return sort_L

快速排序

QuickSort

1. 挑选基准值：从数列中挑出一个元素，称为“基准”（pivot），

2. 分割：所有比基准值小的元素放在基准值的左边，所有比基准值大的元素放在基准值的右边，分割成两个子序列

3. 递归排序子序列：递归地将小于基准值元素的子序列和大于基准值元素的子序列排序。

class QuickSort(Base):
    def execute(self, L: List[int]) -> List[int]:
        length = len(L)
        if length <= 1:
            return L

        self.quicksort(L, 0, length - 1)
        return L

    def partition(self, L: List[int], left: int, right: int) -> int:
        key = left
        while left < right:
            while left < right and L[right] >= L[key]:
                right -= 1
            while left < right and L[left] <= L[key]:
                left += 1
            L[left], L[right] = L[right], L[left]
        L[left], L[key] = L[key], L[left]
        return left

    def quicksort(self, L: List[int], left: int, right: int):
        if left >= right:
            return

        mid = self.partition(L, left, right)
        self.quicksort(L, left, mid - 1)
        self.quicksort(L, mid + 1, right)

归并排序

分而治之

1. （分）将一个序列从中间位置分成两个序列

   1. 继续将这两个子序列按照第一步继续二分下去

   2. 直到所有子序列的长度都为1（终止）

2. （治）两两合并成一个有序序列

class MergeSort(Base):
    def execute(self, L: List[int]) -> List[int]:        
        return self.merge_sort(L)

    def merge(self, a: List[int], b: List[int]) -> List[int]:
        merged = []
        i, j = 0, 0
        while i < len(a) and j < len(b):
            if a[i] <= b[j]:
                merged.append(a[i])
                i += 1
            else:
                merged.append(b[j])
                j += 1
        merged.extend(a[i:])
        merged.extend(b[j:])
        return merged

    def merge_sort(self, L: List[int]) -> List[int]:
        if len(L) <= 1:
            return L
        mid = len(L) // 2
        a = self.merge_sort(L[:mid])
        b = self.merge_sort(L[mid:])
        return self.merge(a, b)

选择排序

SelectionSort

1. 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置

2. 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾

class SelectionSort(Base):
    def execute(self, L: List[int]) -> List[int]:
        for i in range(self.length):
            min_index = i
            for j in range(i + 1, self.length):
                if L[min_index] > L[j]:
                    min_index = j
            L[min_index], L[i] = L[i], L[min_index]
        return L

参考

1. 排序算法
2. visualgo
3. 快速排序