十大经典排序算法3（Python版本）

四、希尔排序

1、希尔介绍
希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；

但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。

2、排序思想
希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。

3、算法步骤

• 选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；

• 按增量序列个数 k，对序列进行 k 趟排序；

• 每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

4、Python练习

def shellSort(arr):
    import math
    gap=1  # 增量序列的间隔基准
    while(gap < len(arr)/3):  # 按照序列进行间隔定位
        gap = gap*3+1
    while gap > 0:
        for i in range(gap,len(arr)):
            temp = arr[i]
            j = i-gap
            while j >=0 and arr[j] > temp:  # 当前的数字大于之前的数字则进行交换
                arr[j+gap]=arr[j]
                j-=gap
            arr[j+gap] = temp
        gap = math.floor(gap/3)
    return arr
}

五、归并排序

1、归并介绍
归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：

自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第 2 种方法）；

自下而上的迭代；

和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是 O(nlogn) 的时间复杂度。代价是需要额外的内存空间。

2、算法步骤

• 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；

• 设定两个指针，最初位置分别为两个已经排序序列的起始位置；

• 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；

• 重复步骤 3 直到某一指针达到序列尾；

• 将另一序列剩下的所有元素直接复制到合并序列尾。

3、动图演示

4、Python练习

def mergeSort(arr):
    import math
    if(len(arr)<2):
        return arr
    middle = math.floor(len(arr)/2)
    left, right = arr[0:middle], arr[middle:]
    return merge(mergeSort(left), mergeSort(right))

def merge(left,right):
    result = []
    while left and right:
        if left[0] <= right[0]:
            result.append(left.pop(0));
        else:
            result.append(right.pop(0));
    while left:
        result.append(left.pop(0));
    while right:
        result.append(right.pop(0));
    return result

文章转载于：
十大经典排序算法（Python）