踏踏实实地打好算法基础(2)—插入排序和希尔排序算法-一一网

插入排序

插入排序虽然没有冒泡排序和选择排序那么简单直观，不过其原理也不算难懂，打过扑克人应该都会秒懂。

基本思想

每步将一个待排序的对象，按其关键码大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止。

插入排序算法

通过一个指针从左向右移动
每次移动将进入数字与排好序的数字比较，然后插入合适的位置
不断重复上面步骤，直到把最后一个数据插入合适的位置，就完成了对原有数组从小到大的排序

将数组分为已排序和未排序两个部分
元素 2 为划分为已排序部分
然后每一次迭代都将未排序的一个元素插入到已排序的适当位置
当 6 进入已排序区域从右到左一个一个对比，直到 6 放置适当位置

然后 5 进入到已排序区域
5 和 6 进行对比，5 小于 6 所以将 5 和 6 交换位置

接下里 5 与 2 进行比较，5 大于 2 所以就不再交换位置停留到当前位置
然后将 1 进入到已排序区域

当 1 元素从未排序进入已排序区域后，通过从右到左一个一个元素对比交换直到 1 来到其应该位置。

代码实现

class Solution:
    def insertionArraySor(self, nums):
        n = len(nums)
        for i in range(1, n):
            j = i
            while nums[j-1] > nums[j] and j > 0:
                nums[j-1], nums[j] = nums[j],nums[j-1]
                j -= 1

        return nums
复制代码

首先初始化 j=i
然后 while nums[j-1] > nums[j] and j > 0 然后将插入数据与已排序区域一个一个元素进行对比

希尔排序(shell sort)

希尔排序是直接插入排序算法的优化改进版本，或者缩小增量排序。是法因 D.L.Shell 于 1959 年提出而得名的算法

希尔排序是非稳定排序算法，

基本思想

设待排序列有 n 个元素，取一个整数 gap(gap<n)作为间隔，将全部元素分为 gap 个子序列，所有距离为 gap 的元素放在同一个子序列中。对于每一个子序列中分别采用直接插入排序。然后缩小间隔 gap 例如取 gap = gap/2 重复上述的子序列划分和排序工作。

希尔排序一般流程

将有 n 个元素的数组分成 gap = n//2 n/gap 个数字序列，第 1 个数据和第 n/2+1 个数据为一对
一次循环使每一个序列对排好顺序，在每一个子序列中分别采用直接插入排序
然后缩小间隔 gap，将 gap = gap/2, 然后变为 n/gap 个子序列，重复上述的子序列划分和排序工作
不断重复上述过程，随着序列减少最后变为一个，也就完成了整个排序

首先每间隔(gap) 3 取一个数字组成一组来进行插入排序
经过这一次迭代后我们该排完序的大致有了一些模样，较大数字已经位于序列的右侧，较小数字位于序列左侧
这个就是希尔排序的魅力，因为原有插入排序每次交换幅度比较小

代码实现

    def sellArraySort(self, nums):
        n = len(nums)
        gap = n // 2
        while gap > 0:
            for i in range(gap,n):
                anchor = nums[i]
                j = i
                while j>=gap and nums[j-gap] > anchor:
                    nums[j] = nums[j - gap]
                    j -= gap
                nums[j] = anchor
            gap = gap // 2
        return nums
复制代码