排序

0. 常见排序算法效率比较

时间复杂度及稳定性比较

排序方法	平均方法	最优复杂度	最坏复杂度	辅助空间	稳定性
冒泡排序	O($n^2$n2)	O($n^2$n2)	O($n^2$n2)	O(1)	稳定
选择排序	O($n^2$n2)	O($n^2$n2)	O($n^2$n2)	O(1)	不稳定
插入排序	O($n^2$n2)	O($n^2$n2)	O($n^2$n2)	O(1)	稳定
希尔排序	O(nlogn)~O($n^2$n2)	O($n^{1.3}$n1.3)	O($n^2$n2)	O(1)	不稳定
快速排序	O(nlogn)	O(nlogn)	O($n^2$n2)	O(nlogn)~O(n)	不稳定
归并排序	O(nlogn)	O(nlogn)	O(nlogn)	O(n)	稳定

综上，归并的排序方法最为合理

1. 冒泡排序

冒泡排序（Bubble Sort）是一种简单的排序算法。它重复地遍历要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复地进行直到没有再需要交换，即该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

冒泡排序算法步骤：

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

实例：

# coding=utf-8
def bubble_sort(alist):
    """冒泡排序"""
    # 时间复杂度
    # 最优时间复杂度：O(n) （表示遍历一次发现没有任何可以交换的元素，排序结束。）
    # 最坏时间复杂度：O(n^2)
    # 稳定性：稳定

    for j in range(len(alist) - 1, 0, -1):
        for i in range(j):
            if alist[i] > alist[i + 1]:
                alist[i], alist[i + 1] = alist[i + 1], alist[i]


li = [34, 26, 83, 27, 77, 31, 54, 35, 12]
print(li)
bubble_sort(li)
print(li)


# 结果：
# [34, 26, 83, 27, 77, 31, 54, 35, 12]
# [12, 26, 27, 31, 34, 35, 54, 77, 83]

2. 选择排序

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对n个元素的表进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。

选择排序步骤：

1. 在未排序序列中找到最小（大）元素，存放到排序序列的起始位置;
2. 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾;
3. 重复步骤2，直至所有元素均排序完成。

实例：

# coding=utf-8
def select_sort(alist):
    """选择排序"""
    # 时间复杂度
    # 最优时间复杂度：O(n^2)
    # 最坏时间复杂度：O(n^2)
    # 稳定性：不稳定（考虑升序每次选择最大的情况）

    n = len(alist)
    for j in range(n - 1):
        min_index = j
        for i in range(j + 1, n):
            if alist[i] < alist[min_index]:
                min_index = i
        if j != min_index:
            alist[j], alist[min_index] = alist[min_index], alist[j]


if __name__ == '__main__':
    li = [34, 26, 83, 27, 77, 31, 54, 35, 12]
    print(li)
    select_sort(li)
    print(li)

# 结果：
# [34, 26, 83, 27, 77, 31, 54, 35, 12]
# [12, 26, 27, 31, 34, 35, 54, 77, 83]

3. 插入排序

插入排序（Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

插入排序步骤：

1. 选择未排序的首个数据，在已排序序列中从后向前扫描，找到相应位置并插入；
2. 插入排序时，从后向前扫描过程中，反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

实例：

# coding=utf-8
def insert_sort(alist):
    """插入排序"""
    # 时间复杂度
    # 最优时间复杂度：O(n) （升序排列，序列已经处于升序状态）
    # 最坏时间复杂度：O(n^2)
    # 稳定性：稳定

    n = len(alist)
    for j in range(1, n):
        for i in range(j, 0, -1):
            if alist[i] < alist[i - 1]:
                alist[i], alist[i - 1] = alist[i - 1], alist[i]
            else:
                break


if __name__ == '__main__':
    li = [34, 26, 83, 27, 77, 31, 54, 35, 12]
    print(li)
    insert_sort(li)
    print(li)

# 结果：
# [34, 26, 83, 27, 77, 31, 54, 35, 12]
# [12, 26, 27, 31, 34, 35, 54, 77, 83]

4. 希尔排序

希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因DL．Shell于1959年提出而得名。 希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

希尔排序步骤：

1. 将数组列在一个表中并对其以步长为数组长度的一半(len(list)//2)分组；
2. 对每组使用直接插入排序算法排序；
3. 重复这过程，不过每次用更长的组（步长更长了，组数更少了）来进行。最后整个表就只有一组了；
4. 当增量减至1时，整个文件恰被分成一组，算法便终止。

实例：

# coding=utf-8
def shell_sort(alist):
    """希尔排序"""
    # 时间复杂度
    # 最优时间复杂度：根据步长序列的不同而不同
    # 最坏时间复杂度：O(n^2)
    # 稳定性：不稳定

    n = len(alist)
    # 初始步长
    gap = n // 2
    while gap > 0:
        # 按步长进行插入排序
        for i in range(gap, n):
            while i >= gap:
                if alist[i] < alist[i - gap]:
                    alist[i], alist[i - gap] = alist[i - gap], alist[i]
                    i -= gap
                else:
                    break

        gap = gap // 2


if __name__ == '__main__':
    li = [34, 26, 83, 27, 77, 31, 54, 35, 12]
    print(li)
    shell_sort(li)
    print(li)

# 结果：
# [34, 26, 83, 27, 77, 31, 54, 35, 12]
# [12, 26, 27, 31, 34, 35, 54, 77, 83]

5. 快速排序

快速排序（Quick sort），又称划分交换排序（partition-exchange sort），通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

快速排序步骤为：

1. 从数列中挑出一个元素，称为"基准"（pivot），
2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

注意：递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

实例：

# coding=utf-8
def quick_sort(alist, start, end):
    """快速排序"""
    # 时间复杂度
    # 最优时间复杂度：O(nlogn)
    # 最坏时间复杂度：O(n^2)
    # 稳定性：不稳定

    # 递归的退出条件
    if start >= end:
        return
    # 设定起始元素为要寻找位置的基准元素mid
    mid = alist[start]
    # left 为序列左边的由左向右移动的游标
    left = start
    # right 为序列右边向左移动的游标
    right = end
    while left < right:
        # 如果left与right未重合，right指向的元素不比基准元素小，则right向左移动
        while left < right and alist[right] >= mid:
            right -= 1
        alist[left] = alist[right]
        # 如果left与right未重合，left指向的元素比基准小，则left向右移动
        while left < right and alist[left] < mid:
            left += 1
        # 将left指向的元素放到right的位置
        alist[right] = alist[left]
    # 从循环退出后，left与right相遇，即left==right，此时所指的
    alist[left] = mid

    # 对基准元素左边的子序列进行快速排序
    quick_sort(alist, start, left - 1)
    # 对基准元素右边的子序列进行快速排序
    quick_sort(alist, left + 1, end)


if __name__ == '__main__':
    li = [34, 26, 83, 27, 77, 31, 54, 35, 12]
    print(li)
    quick_sort(li, 0, len(li) - 1)
    print(li)

# 结果：
# [34, 26, 83, 27, 77, 31, 54, 35, 12]
# [12, 26, 27, 31, 34, 35, 54, 77, 83]

6. 归并排序

归并排序(merge sort)是采用分治法的一个非常典型的应用。归并排序的思想就是先递归分解数组，再合并数组。

将数组分解最小之后，然后合并两个有序数组，基本思路是比较两个数组的最前面的数，谁小就先取谁，取了后相应的指针就往后移一位。然后再比较，直至一个数组为空，最后把另一个数组的剩余部分复制过来即可。

归并排序步骤：

1. 将数组分解最小；合并两个有序数组
2. 比较两个数组的最前面的数，谁小就先取谁，取了后相应的指针就往后移一位；
3. 循环再比较，直至一个数组为空；
4. 最后把另一个数组的剩余部分复制过来即可。

实例：

# coding=utf-8
def merge_sort(alist):
    """归并排序"""
    # 时间复杂度
    # 最优时间复杂度：O(nlogn)
    # 最坏时间复杂度：O(nlogn)
    # 稳定性：稳定

    n = len(alist)
    if 1 == n:
        return alist
    # 二分分解
    mid = n // 2

    # 对左半部分进行归并排序
    left_sorted_li = merge_sort(alist[:mid])
    right_sorted_li = merge_sort(alist[mid:])

    # 合并两个有序数组，并返回
    return merge(left_sorted_li, right_sorted_li)


def merge(left_sorted_li, right_sorted_li):
    """合并两个有序数组，将两个有序数组left[]和right[]合并成一个大的有序数组"""
    left_n = len(left_sorted_li)
    right_n = len(right_sorted_li)
    left, right = 0, 0
    merge_sort_li = []
    while left < left_n and right < right_n:
        if left_sorted_li[left] <= right_sorted_li[right]:
            merge_sort_li.append(left_sorted_li[left])
            left += 1
        else:
            merge_sort_li.append(right_sorted_li[right])
            right += 1
    merge_sort_li += left_sorted_li[left:]
    merge_sort_li += right_sorted_li[right:]
    return merge_sort_li


if __name__ == '__main__':
    li = [34, 26, 83, 27, 77, 31, 54, 35, 12]
    print(li)
    sorted_li = merge_sort(li)
    print(sorted_li)


# 结果：
# [54, 26, 93, 17, 77, 31, 44, 55, 20]
# [17, 20, 26, 31, 44, 54, 55, 77, 93]