排序算法

• 冒泡排序

• 选择排序

• 插入排序

• 快速排序（最常见）

• 希尔排序

• 归并排序

源码：Sorting

冒泡排序

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

• 冒泡排序算法的思路如下（升序）：

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

• 冒泡排序的分析

  bubblesort

• 演示

  bubble

• 时间复杂度

  • 最优时间复杂度：O(n) ——表示遍历一次发现没有任何可以交换的元素，排序结束
  • 最坏时间复杂度：O(n2)
  • 稳定性：稳定

• Python 代码

    def bubble_sort(L):
        N = len(L)
        if N <= 0 :
            print("Please input correct list.")
            return
        for i in range(N):
            for j in range(0,N-1-i):
                if L[j] > L[j+1] :
                    L[j],L[j+1] = L[j+1],L[j]
                    print(L)
        return L
  
    if __name__ == '__main__':
        L = [9,8,7,6,5,4,3,2,1]
        print(bubble_sort(L))
  

• 输出

    >>>
    RESTART: F:\杂\markdown\Python\DataStructure&Algorithm\Sorting\bubble_sort.py
    [8, 9, 7, 6, 5, 4, 3, 2, 1]
    [8, 7, 9, 6, 5, 4, 3, 2, 1]
    [8, 7, 6, 9, 5, 4, 3, 2, 1]
    [8, 7, 6, 5, 9, 4, 3, 2, 1]
    [8, 7, 6, 5, 4, 9, 3, 2, 1]
    [8, 7, 6, 5, 4, 3, 9, 2, 1]
    [8, 7, 6, 5, 4, 3, 2, 9, 1]
    [8, 7, 6, 5, 4, 3, 2, 1, 9]
    [7, 8, 6, 5, 4, 3, 2, 1, 9]
    [7, 6, 8, 5, 4, 3, 2, 1, 9]
    [7, 6, 5, 8, 4, 3, 2, 1, 9]
    [7, 6, 5, 4, 8, 3, 2, 1, 9]
    [7, 6, 5, 4, 3, 8, 2, 1, 9]
    [7, 6, 5, 4, 3, 2, 8, 1, 9]
    [7, 6, 5, 4, 3, 2, 1, 8, 9]
    [6, 7, 5, 4, 3, 2, 1, 8, 9]
    [6, 5, 7, 4, 3, 2, 1, 8, 9]
    [6, 5, 4, 7, 3, 2, 1, 8, 9]
    [6, 5, 4, 3, 7, 2, 1, 8, 9]
    [6, 5, 4, 3, 2, 7, 1, 8, 9]
    [6, 5, 4, 3, 2, 1, 7, 8, 9]
    [5, 6, 4, 3, 2, 1, 7, 8, 9]
    [5, 4, 6, 3, 2, 1, 7, 8, 9]
    [5, 4, 3, 6, 2, 1, 7, 8, 9]
    [5, 4, 3, 2, 6, 1, 7, 8, 9]
    [5, 4, 3, 2, 1, 6, 7, 8, 9]
    [4, 5, 3, 2, 1, 6, 7, 8, 9]
    [4, 3, 5, 2, 1, 6, 7, 8, 9]
    [4, 3, 2, 5, 1, 6, 7, 8, 9]
    [4, 3, 2, 1, 5, 6, 7, 8, 9]
    [3, 4, 2, 1, 5, 6, 7, 8, 9]
    [3, 2, 4, 1, 5, 6, 7, 8, 9]
    [3, 2, 1, 4, 5, 6, 7, 8, 9]
    [2, 3, 1, 4, 5, 6, 7, 8, 9]
    [2, 1, 3, 4, 5, 6, 7, 8, 9]
    [1, 2, 3, 4, 5, 6, 7, 8, 9]
    [1, 2, 3, 4, 5, 6, 7, 8, 9]
    >>>
  

选择排序

• 选择排序（Selection sort）是一种简单直观的排序算法。

• 它的工作原理如下：

  • 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
  • 然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾
  • 以此类推，直到所有元素均排序完毕。

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

• 选择排序分析

  selectionsort

• 演示

  selection

• 时间复杂度

  • 最优时间复杂度：O(n2)
  • 最坏时间复杂度：O(n2)
  • 稳定性：不稳定（考虑升序每次选择最大的情况）

• Python 代码

    def select_sort(L):
        N = len(L)
        if N <= 0 :
            print("Please input correct list.")
            return
        for i in range(N-1):
            indexOfMax = 0
            for j in range(1,N-i):
                if L[j] > L[indexOfMax] :
                    indexOfMax = j
            L[N-1-i], L[indexOfMax] = L[indexOfMax], L[N-1-i]
            print(L)
        return L
  
    if __name__ == '__main__':
        L = [9,8,7,6,5,4,3,2,1]
        select_sort(L)
  

• 输出

    >>>
    RESTART: F:/杂/markdown/Python/DataStructure&Algorithm/Sorting/selection_sort.py
    [1, 8, 7, 6, 5, 4, 3, 2, 9]
    [1, 2, 7, 6, 5, 4, 3, 8, 9]
    [1, 2, 3, 6, 5, 4, 7, 8, 9]
    [1, 2, 3, 4, 5, 6, 7, 8, 9]
    [1, 2, 3, 4, 5, 6, 7, 8, 9]
    [1, 2, 3, 4, 5, 6, 7, 8, 9]
    [1, 2, 3, 4, 5, 6, 7, 8, 9]
    [1, 2, 3, 4, 5, 6, 7, 8, 9]
    >>>
  

插入排序

• 插入排序（Insertion Sort）是一种简单直观的排序算法，对于少量元素，它是一种有效的算法。

• 想像一下，我们在打扑克牌，首先我们手上没有牌，然后一张一张从桌上摸牌，每次摸牌都会按照从小到大的顺序排好，所以手上的牌总是有序的。

• 它的工作原理：

  • 通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
  • 插入排序在实现上，在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

• 演示

  Insertion-sort-example

• 伪代码

    INSERTION-SORT(A)
        for j = 2 to A.length
            key = A[j]
            //Insert A[j] into the sorted sequence A[1..j-1].
            i = j - 1
            while i > 0 and A[i] > key
                A[i+1] = A[i]
                i = i - 1
            A[i+1] = key
  

• 时间复杂度

  • 最优时间复杂度：O(n) ——升序排列，序列已经处于升序状态
  • 最坏时间复杂度：O(n2) ——序列处于降序状态，要转变为升序
  • 稳定性：稳定

• Python 代码

    def insertion_sort(L):
        N = len(L)
        if N <= 0:
            print("Please input correct list.")
            return
        for i in range(N): # i指示当前待排元素
            if L[i - 1] < L[i]: # 如果待排元素比已排序列的最后一个元素（最大的元素）还大，则直接加入已排序列
                continue
            temp = L[i]
            for j in range(i - 1, -1, -1): # i-1指示已排序列的最后一项，然后以此与当前待排元素比较，往前移动
                L[j + 1] = L[j]
                if L[j - 1] <= temp:
                    L[j] = temp
                    print(L)
                    break
        return L
  
    if __name__ == '__main__':
        L = [1, 8, 7, 6, 5, 4, 3, 2, 1]
        print("ordered sequence =",insertion_sort(L))
  

• 输出

    >>>
    RESTART: F:\杂\markdown\Python\DataStructure&Algorithm\Sorting\insertion_sort.py
    [8, 9, 7, 6, 5, 4, 3, 2, 1]
    [7, 8, 9, 6, 5, 4, 3, 2, 1]
    [6, 7, 8, 9, 5, 4, 3, 2, 1]
    [5, 6, 7, 8, 9, 4, 3, 2, 1]
    [4, 5, 6, 7, 8, 9, 3, 2, 1]
    [3, 4, 5, 6, 7, 8, 9, 2, 1]
    [2, 3, 4, 5, 6, 7, 8, 9, 1]
    [1, 2, 3, 4, 5, 6, 7, 8, 9]
    [1, 2, 3, 4, 5, 6, 7, 8, 9]
    >>>
  

快速排序（最常见）

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

• 步骤为：

  • 从数列中挑出一个元素，称为"基准"（pivot），或称枢纽
  • 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
  • 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
  • 递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

• 时间复杂度

  • 最优时间复杂度：O(nlogn)
  • 最坏时间复杂度：O(n2) ——每次分区时，某个分区为空
  • 稳定性：不稳定

• 从一开始快速排序平均需要花费O(n log n)时间的描述并不明显。但是不难观察到的是分区运算，数组的元素都会在每次循环中走访过一次，使用O(n)的时间。在使用结合（concatenation）的版本中，这项运算也是O(n)。

• 在最好的情况，每次我们运行一次分区，我们会把一个数列分为两个几近相等的片段。这个意思就是每次递归调用处理一半大小的数列。因此，在到达大小为一的数列前，我们只要作log n次嵌套的调用。这个意思就是调用树的深度是O(log n)。但是在同一层次结构的两个程序调用中，不会处理到原来数列的相同部分；因此，程序调用的每一层次结构总共全部仅需要O(n)的时间（每个调用有某些共同的额外耗费，但是因为在每一层次结构仅仅只有O(n)个调用，这些被归纳在O(n)系数中）。结果是这个算法仅需使用O(n log n)时间。

• Python 代码

    def quick_sort(L):
        return qsort(L,0,len(L)-1)
  
    def qsort(L,low,high):
        if(low < high):
            pivotloc = partition(L,low,high)
            qsort(L,low,pivotloc-1)
            qsort(L,pivotloc+1,high)
        return L
  
    def partition(L,low,high):
        if(low >= high):
            return
        pivotkey = L[low]
        while(low < high):
            while(low < high and L[high] >= pivotkey):
                high = high - 1
            L[low],L[high] = L[high],L[low]
            while(low < high and L[low] <= pivotkey):
                low = low + 1
            L[high],L[low] = L[low],L[high]
            print("pivotkey =",pivotkey)
            print(L,"\n")
        return low
  
    if __name__ == '__main__':
        L = [9,8,7,6,5,4,3,2,1]
        print(quick_sort(L))
  

• 输出

    >>>
    RESTART: F:\杂\markdown\Python\DataStructure&Algorithm\Sorting\quick_sort.py
    pivotkey = 9
    [1, 8, 7, 6, 5, 4, 3, 2, 9]
  
    pivotkey = 1
    [1, 8, 7, 6, 5, 4, 3, 2, 9]
  
    pivotkey = 8
    [1, 2, 7, 6, 5, 4, 3, 8, 9]
  
    pivotkey = 2
    [1, 2, 7, 6, 5, 4, 3, 8, 9]
  
    pivotkey = 7
    [1, 2, 3, 6, 5, 4, 7, 8, 9]
  
    pivotkey = 3
    [1, 2, 3, 6, 5, 4, 7, 8, 9]
  
    pivotkey = 6
    [1, 2, 3, 4, 5, 6, 7, 8, 9]
  
    pivotkey = 4
    [1, 2, 3, 4, 5, 6, 7, 8, 9]
  
    [1, 2, 3, 4, 5, 6, 7, 8, 9]
    >>>
  

希尔排序

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

• 基本思想：先将整个待排序列分割称为若干子序列分别进行直接插入排序，待整个序列“基本有序”时，再对全体记录进行一次直接插入排序

• 希尔排序过程

  • 希尔排序的基本思想是：将数组列在一个表中并对列分别进行插入排序，重复这过程，不过每次用更长的列（步长更长了，列数更少了）来进行。最后整个表就只有一列了。将数组转换至表是为了更好地理解这算法，算法本身还是使用数组进行排序。

  • 例如，假设有这样一组数[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]，如果我们以步长为5开始进行排序，我们可以通过将这列表放在有5列的表中来更好地描述算法，这样他们就应该看起来是这样(竖着的元素是步长组成)：

    13 14 94 33 82
    25 59 94 65 23
    45 27 73 25 39
    10
    

    然后我们对每列进行排序：

    10 14 73 25 23
    13 27 94 33 39
    25 59 94 65 82
    45
    

    将上述四行数字，依序接在一起时我们得到：[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ]。这时10已经移至正确位置了，然后再以3为步长进行排序：

    10 14 73
    25 23 13
    27 94 33
    39 25 59
    94 65 82
    45
    

    排序之后变为：

    10 14 13
    25 23 33
    27 25 59
    39 65 73
    45 94 82
    94
    

    最后以1步长进行排序（此时就是简单的插入排序了）

• 时间复杂度

  • 最优时间复杂度：根据步长序列的不同而不同
  • 最坏时间复杂度：O(n2)
  • 稳定性：不稳定

• Python 代码

    def shell_sort(L,delta):
        N = len(L)
        for inc in delta:
            L = shell_insert(L,inc)
            print(L,"\n")
        return L
  
    def shell_insert(L,inc):
        N = len(L)
        for index in range(inc):               # 整个序列分为若干子序列，index是每个子序列的头元素
            for i in range(index+inc,N,inc):   # 默认每个子序列的头元素为“已排序列”，除了头元素的子序列为“待排序列”
                temp = L[i]                    # 每个子序列的排序方式为直接插入排序，所以当前待排元素的值给temp
                for j in range(i-inc,-1,-inc): # 在子序列的“已排序列”中找到合适的插入地点，所以是倒序
                    if temp < L[j]:
                        L[j+inc] = L[j]
                    else :
                        break                  # 当前待排元素比“已排序列”中的末尾元素还要大，所以直接放入末尾
                    if j == index or L[j-inc] < temp :
                        L[j] = temp
                        print(L)
        return L
  
    if __name__ == '__main__':
        L = [9,8,7,6,5,4,3,2,1]
        delta = [5,3,1] #构造增量序列
        print(shell_sort(L,delta))
  

• 输出

    >>>
    RESTART: F:\杂\markdown\Python\DataStructure&Algorithm\Sorting\shell_sort.py
    [4, 8, 7, 6, 5, 9, 3, 2, 1]
    [4, 3, 7, 6, 5, 9, 8, 2, 1]
    [4, 3, 2, 6, 5, 9, 8, 7, 1]
    [4, 3, 2, 1, 5, 9, 8, 7, 6]
    [4, 3, 2, 1, 5, 9, 8, 7, 6]
  
    [1, 3, 2, 4, 5, 9, 8, 7, 6]
    [1, 3, 2, 4, 5, 6, 8, 7, 9]
    [1, 3, 2, 4, 5, 6, 8, 7, 9]
  
    [1, 2, 3, 4, 5, 6, 8, 7, 9]
    [1, 2, 3, 4, 5, 6, 7, 8, 9]
    [1, 2, 3, 4, 5, 6, 7, 8, 9]
  
    [1, 2, 3, 4, 5, 6, 7, 8, 9]
    >>>
  

归并排序

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

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

• 归并排序的分析

  Merge-sort-example

• 时间复杂度

  • 最优时间复杂度：O(nlogn)
  • 最坏时间复杂度：O(nlogn)
  • 稳定性：稳定
  • 缺点:占用了一定的空间，所以归并算法是用空间换取时间的典型应用

• Python 代码

    def merge(left, right):
        lp, rp = 0, 0
        result = []
        while lp < len(left) and rp < len(right):
            if left[lp] <= right[rp]:
                result.append(left[lp])
                lp += 1
            else:
                result.append(right[rp])
                rp += 1
        result += left[lp:]
        result += right[rp:]
        return result
  
    def merge_sort(alist):
        length = len(alist)
        if length == 1:
            return alist
        mid = length // 2
        left = merge_sort(alist[:mid])
        right = merge_sort(alist[mid:])
        print("left = %s, right = %s"%(left,right))
        result = merge(left, right)
        print("merge:",result)
        return result
  
    if __name__ == '__main__':
        alist = [9, 8, 7, 6, 5, 4, 3, 2, 1]
        print("ordered sequence =",merge_sort(alist))
  

• 输出

    left = [9], right = [8]
    merge: [8, 9]
    left = [7], right = [6]
    merge: [6, 7]
    left = [8, 9], right = [6, 7]
    merge: [6, 7, 8, 9]
    left = [5], right = [4]
    merge: [4, 5]
    left = [2], right = [1]
    merge: [1, 2]
    left = [3], right = [1, 2]
    merge: [1, 2, 3]
    left = [4, 5], right = [1, 2, 3]
    merge: [1, 2, 3, 4, 5]
    left = [6, 7, 8, 9], right = [1, 2, 3, 4, 5]
    merge: [1, 2, 3, 4, 5, 6, 7, 8, 9]
    ordered sequence = [1, 2, 3, 4, 5, 6, 7, 8, 9]
  

各种排序算法效率比较

2017911-排序比较

• 算法是否稳定：待排序列中同样元素的先后顺序是否改变

  比如待排序列是：2，3，1，8，9，1'

  排列后的序列是：1'，1，2，3，8，9

• 快速排序应用广泛的原因：

  • 性能接近 O(nlogn)

  • 辅助空间较归并排序小

  • 一般不太关注稳定与否