python希尔排序、归并排序

Myth丶恋晨 2023-06-11 10:21 53阅读 0赞

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

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

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

![aHR0cHM6Ly93d3cucnVub29iLmNvbS93cC1jb250ZW50L3VwbG9hZHMvMjAxOS8wMy9Tb3J0aW5nX3NoZWxsc29ydF9hbmltLmdpZg][]

![SouthEast][]

代码如下：

def shell_sort(alist):
        '''
        希尔排序
        :param alist:
        :return:
        '''
        n = len(alist)
        gap = n // 2
        # gap变化到0之前，插入算法执行的次数
        while gap > 0:
            # 插入算法，与普通的插入算法就是gap步长的不同
            for j in range(gap,n):
                i = j
                while i > 0 and alist[i] < alist[i - gap]:
                    alist[i],alist[i-gap] = alist[i-gap],alist[i]
                    i -= gap
            # 缩短gap步长
            gap //= 2
    if __name__ == '__main__':
        li = [54,26,93,17,77,31,44,55,28]
        print('排序前',li)
        shell_sort(li)
        print('排序后',li)

运行结果：

排序前 [54, 26, 93, 17, 77, 31, 44, 55, 28]
    排序后 [17, 26, 28, 31, 44, 54, 55, 77, 93]

# **归并排序** #

归并排序（英语：Merge sort，或mergesort），是创建在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

### 1、归并排序原理 ###

归并排序采用分而治之的原理：

一、将一个序列从中间位置分成两个序列；

二、在将这两个子序列按照第一步继续二分下去；

三、直到所有子序列的长度都为1，也就是不可以再二分截止。这时候再两两合并成一个有序序列即可。

### 2、原理图 ###

### ![70][]    ###

代码如下：

def merge(left_li,right_li):
        '''
        排序合并
        :param left_li:
        :param right_li:
        :return:
        '''
        left_pointer,right_pointer = 0,0
        result = []
        while right_pointer < len(left_li) and left_pointer < len(right_li):
            if left_li[right_pointer] < right_li[left_pointer]:
                result.append(left_li[right_pointer])
                right_pointer += 1
            else:
                result.append(right_li[left_pointer])
                left_pointer += 1
        if right_pointer == len(left_li):
            for i in right_li[left_pointer:]:
                result.append(i)
        else:
            for i in left_li[right_pointer:]:
                result.append(i)
    
        return result
    
    def merge_sort(alist):
        '''
        分组整合
        :param alist:
        :return:
        '''
        n = len(alist)
        if n <= 1:
            return alist
        mid = n // 2
        left_li = merge_sort(alist[:mid])
        right_li = merge_sort(alist[mid:])
        return merge(left_li,right_li)
    
    if __name__ == '__main__':
        li = [54, 26, 93, 17, 77, 31, 44, 55, 28]
        print('排序前',li)
        print('排序后',merge_sort(li))

运行结果：

排序前 [54, 26, 93, 17, 77, 31, 44, 55, 28]
    排序后 [17, 26, 28, 31, 44, 54, 55, 77, 93]

[aHR0cHM6Ly93d3cucnVub29iLmNvbS93cC1jb250ZW50L3VwbG9hZHMvMjAxOS8wMy9Tb3J0aW5nX3NoZWxsc29ydF9hbmltLmdpZg]: /images/20230531/225d1e19e6864caeadb7440553e3ae43.png
[SouthEast]: /images/20230531/e1a6d3e2c0c24d21a2848598809808ec.png
[70]: /images/20230531/fe732a5fc4084973bda810ba74034099.png