常见排序算法的python实现

一:冒泡排序Bubble Sort

  1. 核心思想:重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。

  2. 复杂度和稳定性:平均情况与最坏情况均为 O(n^2),空间复杂度:O(1),稳定排序。

  3. python实现:

    
    def bubble_sort(alist):
        # 冒泡需要n(列表长度)次遍历(不是严格的遍历,每一次遍历排定一个数字,下一次遍历的数字少一个)
        for i in range(len(alist)):  
            print(alist)
            # 对于每一个i,排定一个数字,下一次遍历时就不包含该已经排定的数字和之前已经排定的数字
            for j in range(1, len(alist)-i):
                if alist[j - 1] > alist[j]:   # 较大的数字后移,如同较大的泡泡上浮
                    alist[j - 1], alist[j] = alist[j], alist[j - 1]
        return alist
    
    unsorted_list = [6, 5, 3, 1, 8, 7, 2, 4]
    print(bubble_sort(unsorted_list))
    

二:选择排序Selection Sort

  1. 核心思想:从剩余元素中找出最小值放置在已经排序的元素数组末尾。

  2. 复杂度和稳定性:平均情况与最坏情况均为 O(n^2);空间复杂度:O(1),因为使用了temp变量;非稳定排序。

  3. python实现:

    
    def selection_sort(alist):
        for i in range(len(alist)):              # 不断的选择剩余元素中的最小值
            print(alist)
            min_index = i                        # 剩余元素中最小值的索引初始化指向 i
            for j in range(i+1, len(alist)):     # 遍历所有剩余元素
                if alist[j] < alist[min_index]:  # 如果扫描到比当前最小值还小的元素,改变min_index索引
                    min_index = j                # 剩余元素中最小值的索引指向新的最小值
            alist[min_index], alist[i] = alist[i], alist[min_index]  # 每一次遍历(不是完整遍历),排定一个'最小值'
    
        return alist
    
    unsorted_list = [8, 5, 2, 6, 9, 3, 1, 4, 0, 7]
    print(selection_sort(unsorted_list))
    

三:插入排序Insertion Sort

  1. 核心思想:对于每个未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。

  2. 复杂度和稳定性:平均情况与最坏情况均为 O(n^2),空间复杂度:未使用额外空间,稳定排序。

  3. python实现:

    
    def insertion_sort(alist):
        for i, item_i in enumerate(alist):  # 索引i 和 第i个元素
            print(alist)
            index = i
            while index > 0 and alist[index - 1] > item_i:  # 对已经排序的数组从后往前扫描比较
                alist[index] = alist[index - 1]  # 如果被扫描的元素(已排序)大于新元素,将该元素后移一位
                index -= 1
    
            alist[index] = item_i  # 找到已经排序的元素中小于或等于新元素的位置,将新元素插入到该位置
    
        return alist
    
    
     unsorted_list = [6, 5, 3, 1, 8, 7, 2, 4]
     print(insertion_sort(unsorted_list))
    
    

四:希尔排序Shell Sort

  1. 核心思想:使数组中任意间隔为h的元素都是有序的,即h有序数组(h个互相独立的数组编织在一起组成的一个数组)。

    • 进行排序时,如果h很大,能够将元素移动到很远的地方去。
    • 对于任意以1结尾的h序列,我们能够将数组排序。
  2. 注意:对每一列进行排序之后,子数组是部分有序的,子数组部分有序的程度取决于递增序列的选择。

  3. 复杂度和稳定性:平均情况O(nlogn~n^2),最坏情况为 O(n^2);空间复杂度:O(1),因为使用了temp变量;非稳定排序。

  4. python实现:

    
       def shell_sort(alist):    # 将alist按升序排列
           alength = len(alist)
           h = 1
           while h < alength//3:  # h序列的初始值
               h = 3*h + 1
           while h >= 1:
               print(h)
               print(alist)
               # 对每一列进行排序,排序之后子数组是部分有序的,一共存在(alength-h)个子数组需要排序
               for i in range(h, alength): 
                   j = i
                   # 将alist[i]插入到alist[i-h],alist[i-2h],alist[i-3h]...之中,子数组成为部分有序
                   # 子数组中元素alist[i]交换到比它到的元素之前去
                   while j >= h and alist[j] < alist[j-h]: 
                       alist[j], alist[j-h] = alist[j-h], alist[j] 
                       j -= h
               h = h//3
    
           return alist
    
       unsorted_list = [8, 5, 2, 6, 10, 3, 1, 4, 9, 7]
       print(shell_sort(unsorted_list))
    

五:归并排序Merge Sort

六:快排Quick Sort

  1. 核心思想

    1. 从数列中挑出一个元素作为基准数。
    2. 分区过程,将比基准数大的放到右边,小于或等于它的数都放到左边。
    3. 再对左右区间递归执行第二步,直至各区间只有一个数。
  2. 复杂度和稳定性:平均情况O(NlogN),最坏情况均为 O(N^2);空间复杂度:O(logN~N);非稳定排序。

  3. python实现:

    
    class Quick:
        def quick_sort(self, alist):
            self.quick_sort_rec(alist, 0, len(alist)-1)
    
        def quick_sort_rec(self, alist, lo, hi):
            if hi <= lo:
                return
            j = self.partition(alist, lo, hi)
            self.quick_sort_rec(alist, lo, j-1)
            self.quick_sort_rec(alist, j+1, hi)
    
        @staticmethod
        def partition(alist, lo, hi):
            """将数组切分为alist[lo..i-1], alist[i], alist[i+1..hi] """
            i = lo          # 左扫描指针
            j = hi + 1      # 右扫描指针
            v = alist[lo]   # 切分元素
            while True:     # 扫描左右,检查扫描是否结束并交互元素
                while True:
                    i += 1
                    if alist[i] >= v:
                        break
                    if i == hi:
                        break
                while True:
                    j -= 1
                    if v >= alist[j]:
                        break
                    if j == lo:
                        break
                if i >= j:
                    break
                alist[i], alist[j] = alist[j], alist[i]
            alist[lo], alist[j] = alist[j], alist[lo]   # 将 v = a[j] 放入正确的位置
            return j                                    # a[lo..j-1] <= a[j] <= a[j+1..hi] 达成
    
    unsorted_list = [8, 5, 2, 6, 9, 3, 1, 4, 0, 7]
    quicksort = Quick()
    quicksort.quick_sort(unsorted_list)
    print(unsorted_list)
    

七:堆排序Heap Sort

  1. coming soon......
comments powered by Disqus