常见排序算法的Python实现

àì夳堔傛蜴生んèń 2022-05-30 07:35 194阅读 0赞

# 排序算法的Python实现 #

import copy
    import random
    import math
    
    sort_list = [20,1,24,54,11,26,87,45,32,544,25,87,47,48,58,1024]
    global size
    size = len(sort_list)
    
    '''
    选择排序，顾名思义，扫描全表，选最小值
    外循环走size-1次，每一次确定当前一个最小的数
    内循环走size-（已经确定的最小数），理解为当前位置之前的数字都已有序，从当前位置出发到结尾扫描确定当前最小的数字
    时间复杂度：平均O(n**2)，最坏O(n**2)，最好O(n**2)
    空间复杂度：O(1)
    稳定性：不稳定
    '''
    def select_sort(sort_list):
        for i in range(size-1):
            min = i
            for j in range(i, size):
                if sort_list[j] < sort_list[min]:
                    min = j
            sort_list[min], sort_list[i] = sort_list[i], sort_list[min]
        print("选择排序结果是：",sort_list)
    
    '''
    冒泡排序，逐个比较，将最大的数排到最后方
    外循环走size-1次，每次确定一个最大的数
    内循环走size-（当前已确定的数），理解为从头开始，两两比较，a(n)>a(n+1)，则交换
    时间复杂度：平均O(n**2)，最坏O(n**2)，最好O(n)
    空间复杂度：O(1)
    稳定性：稳定
    '''
    def bub_sort(sort_list):
        for i in range(size-1):
            for j in range(1, size):
                if sort_list[j] < sort_list[j-1]:
                    sort_list[j], sort_list[j-1] = sort_list[j-1], sort_list[j]
        print("冒泡排序结果是：",sort_list)
    
    '''
    插入排序，类似于体育课排队列
    外循环走size-1次，每次确定一个较小的数，一次内循环结束，当前位置的左侧是相对大小确定的
    内循环走0次或者当前已确定数的次数，理解为当前数与之前的第一个数对比，若小于则交换，继而继续比较，所以最少0次，最多当前已确定数次
    时间复杂度：平均O(n**2)，最坏O(n**2)，最好O(n)
    空间复杂度：O(1)
    稳定性：稳定
    '''
    def insert_sort(sort_list):
        for i in range(1, size):
            j = i
            while j > 0 and sort_list[j]<sort_list[j-1]:
                sort_list[j], sort_list[j-1] = sort_list[j-1], sort_list[j]
                j -= 1
        print("插入排序结果是：",sort_list)
    
    '''
    希尔排序（该处指配合插入排序的希尔排序），由插入排序的定义可以看出来，当前的数想要确定位置必须与之前的数字逐个比较，
    而希尔排序改成h个比较，这样做的好处是，针对数据量大的数组，排序的过程更轻松（构建h个不同的子数组，每个子数组逻辑相邻（相差距离为h））
    外循环的运算次数为（size = size//3循环，直到size等于1，每循环一次，运算次数加一
    如size = 150,150//3=50（1次），50//3=16（2次），16//3=5（3次），5//3=1（4次））
    内循环为选择插入排序，次数由当前的外循环变量决定
    时间复杂度：平均O(n**1.3)，其他情况不好分析
    空间复杂度：O(1)
    稳定性：不稳定
    '''
    def shell_sort(sort_list):
        h = 1
        while h < size//3:
            h = h*3+1
    
        while h >=1:
            for i in range(h, size):
                j = i
                while j > h and sort_list[j]<sort_list[j-h]:
                    sort_list[j], sort_list[j-h] = sort_list[j-h], sort_list[j]
                    j -= h
            h = h//3
        print("希尔排序结果是：",sort_list)
    
    '''
    归并排序，分治算法思想，将一个大问题分解成若干个小问题，若问题类似可用递归完成
    常见两种归并算法，自顶向下和自底向上
    自顶向下的算法用递归的方法，先解决左边的排序，再解决右边的排序
    自底向上的算法用拆解合并的思想，先拆成size/2个小数组进行归并排序，继而将结果拆成size/4个数组归并排序，当size/(2**n)<1时完成排序
    时间复杂度：平均O(nlog2n)，最坏O(nlog2n)，最好O(nlog2n)
    空间复杂度：O(n)（需要一个临时数组来保存）
    稳定性：稳定
    '''
    class merge(object):
        #原地归并抽象方法，方便复用，传入数组，左值，中值，右值
        def merge_sort(self, sort_list, lo, mid, hi):       
            i = lo
            j = mid+1
            aux = copy.deepcopy(sort_list)      
    
            for k in range(lo, hi+1):
                if i > mid:
                    sort_list[k] = aux[j]
                    j += 1
                elif j > hi:
                    sort_list[k] = aux[i]
                    i += 1
                elif aux[j] <= aux[i]:
                    sort_list[k] = aux[j]
                    j += 1
                else:
                    sort_list[k] = aux[i]
                    i += 1
    
        def sort(self, sort_list):
            self.sort1(sort_list, 0, size-1)
    
        #自顶向下的归并排序
        def sort1(self, sort_list, lo, hi):
            if hi <= lo:            
                return sort_list
    
            mid = lo + (hi-lo)//2
            self.sort1(sort_list, lo, mid)
            self.sort1(sort_list, mid+1, hi)
            self.merge_sort(sort_list, lo, mid, hi)
    
        def sort2(self, sort_list):
            sz = 1
            while sz < size:
                lo = 0
                while lo < size-sz:
                    self.merge_sort(sort_list, lo, lo+sz-1, min(lo+sz+sz-1, size-1))
                    lo += sz+sz
                sz = sz+sz
            print(sort_list)
    
    '''
    快速排序，是常规条件下最快的排序算法，使用分治算法思想，利用递归完成
    首先先改变数组内部顺序（消除输入依赖），然后通过切分函数找出一个值（二分切分中，该值越接近正确顺序的中值越好）
    以该值为mid，递归调用自身，分而治之
    重点在于切分函数，二分切分函数的思想是，以某子数组第一个数a为基准，
    从左往右扫描找出一个大于a的数，再从右往左扫描找出一个小于a的数，两者交换
    最后将a放到正确的位置，返回切分的数的索引
    时间复杂度：平均O(nlog2n)，最坏O(n**2)，最好O(nlog2n)
    空间复杂度：O(log2n)（需要一个临时数组来保存）
    稳定性：不稳定
    '''
    class quick(object):
        #消除输入依赖
        def sort(self, sort_list):
            random.sample(sort_list, size)
            self.sort1(sort_list, 0, size-1)
    
        #递归主函数体，从切分函数得到切分索引，左右递归，递归结束不用归并
        def sort1(self, sort_list, lo, hi):
            if hi <= lo:
                return sort_list
    
            j = self.partition(sort_list, lo, hi)
            self.sort1(sort_list, lo, j-1)
            self.sort1(sort_list, j+1, hi)
    
        #切分函数，左右指针，轮流扫描，交换位置，最后将切分元素放到正确的位置，返回切分索引
        def partition(self, sort_list, lo, hi):
            i = lo
            j = hi+1
            v = sort_list[lo]
    
            while True:
                i = i + 1
                while sort_list[i]<v:
                    if i==hi:
                        break
                    i += 1
                j = j - 1
                while v < sort_list[j]:
                    if j==lo:
                        break
                    j -= 1
    
                if i >= j:
                    break
    
                sort_list[i], sort_list[j] = sort_list[j], sort_list[i]
    
            sort_list[lo], sort_list[j] = sort_list[j], sort_list[lo]
            return j
    
    '''
    基数排序，不进行比较的整数排序算法，基数指的是整数的进制（默认为10），
    根据位数要做几次不同的桶排序，位数的计算为int(math.ceil(math.log(max(sort_list)+1, radix)))
    每次循环完成当前位数（个位、十位、百位）的大小排序，理解过程可见http://bubkoo.com/2014/01/15/sort-algorithm/radix-sort/
    一共有十个桶，分别对应0-10，每个桶有若干数据，则桶可以用二维数组完成，记为a[index1][index2]，
    对每一个sort_list里的数，index1 = sort_list_num%(radix**i)//(radix**(i-1))
    时间复杂度：平均O(k*n)，最坏O(k*n)，最好O(k*n)，k为最大数字的位数
    空间复杂度：O(n)
    稳定性：稳定
    '''
    def radix_sort(sort_list, radix=10):
        """sort_list为整数列表， radix为基数"""
        K = int(math.ceil(math.log(max(sort_list)+1, radix)))   
        for i in range(1, K+1):
            bucket = [[] for i in range(radix)]
            for val in sort_list:
                bucket[val%(radix**i)//(radix**(i-1))].append(val)
            del sort_list[:]
            for each in bucket:
                sort_list.extend(each)
                print(sort_list)
    
    '''
    堆排序
    时间复杂度：平均O(nlog2n)，最坏O(nlog2n)，最好O(nlog2n)
    空间复杂度：O(1)（需要一个临时数组来保存）
    稳定性：不稳定
    '''
    
    
    
    #select_sort(sort_list)
    #bub_sort(sort_list)
    #insert_sort(sort_list)
    #shell_sort(sort_list)
    #自顶向下归并排序测试
    # a = merge()
    # a.sort(sort_list)
    # print(sort_list)
    #自底向上归并排序测试
    # a = merge()
    # a.sort2(sort_list)
    # print(sort_list)
    #快速排序测试
    # print(sort_list)
    # a = quick()
    # a.sort(sort_list)
    # print(sort_list)
    #基数排序测试
    #radix_sort(sort_list)