十大排序算法,一次让你看个够(Python)

ゝ一世哀愁。 2022-12-21 03:16 127阅读 0赞

### 十大排序算法,一次让你看个够Python版 ###

*  复杂度
 *  比较算法
 *   *  冒泡排序
     *   *  步骤
         *  实现
     *  选择排序
     *   *  步骤
         *  实现
     *  插入排序
     *   *  步骤
         *  实现
     *  希尔排序
     *   *  步骤
         *  实现
     *  归并排序
     *   *  步骤
         *   *  迭代法
             *  递归法
         *  实现
     *  快速排序
     *   *  步骤
         *  实现
     *  堆排序
     *   *  步骤
         *  实现
 *  非比较排序
 *   *  计数排序
     *   *  步骤
         *  实现
     *  桶排序
     *   *  实现
     *  基数排序
     *   *  步骤
         *  实现

# 复杂度 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ExMzA5NTI1ODAy_size_16_color_FFFFFF_t_70_pic_center]

# 比较算法 #

## 冒泡排序 ##

冒泡排序(Bubble Sort)是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。  
![在这里插入图片描述][20201114095516886.gif_pic_center]

### 步骤 ###

冒泡排序算法的运作如下：

*  比较相邻的元素。如果第一个比第二个大，就交换他们两个。
 *  对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
 *  针对所有的元素重复以上的步骤，除了最后一个。
 *  持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

### 实现 ###

import random
    def Bubble_sort(arr):
        for i in range(len(arr)-1):
            count=0
            for j in range(len(arr)-i-1):
                if arr[j+1]<arr[j]:
                    arr[j],arr[j+1]=arr[j+1],arr[j]
                    count+=1
            if not count: #如果本来是有序的，走一遍就可以直接退出
                break
        print(arr)
    arr=[random.randint(1,100) for x in range(100)]
    print(arr)
    Bubble_sort(arr)

## 选择排序 ##

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理大致是将后面的元素最小元素一个个取出然后按顺序放置。简单的描述为每次选出当前下标的最小值/最大值  
![在这里插入图片描述][20201114100216290.gif_pic_center]

### 步骤 ###

*  在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
 *  再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
 *  重复第二步，直到所有元素均排序完毕。

### 实现 ###

import random
    def selection_sort(list):
        n=len(list)
        for i in range (0,n):
            min = i
            for j in range(i+1,n):
                if list[j]<list[min]:
                    min=j
                    list[min],list[i]=list[i],list[min]
        print(list)
    arr=[random.randint(1,100) for x in range(1000)]
    print(arr)
    selection_sort(arr)

## 插入排序 ##

插入排序（Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。  
![在这里插入图片描述][20201114100431803.gif_pic_center]

### 步骤 ###

*  从第一个元素开始，该元素可以认为已经被排序
 *  取出下一个元素，在已经排序的元素序列中从后向前扫描
 *  如果该元素（已排序）大于新元素，将该元素移到下一位置
 *  重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
 *  将新元素插入到该位置后
 *  重复步骤2~5

### 实现 ###

import random
    def Insert_Sort(arr):
        # 插入排序
        # 第一层for表示循环插入的遍数
        for i in range(1, len(arr)):
            # 设置当前需要插入的元素
            current = arr[i]
            # 与当前元素比较的比较元素
            pre_index = i - 1
            while pre_index >= 0 and arr[pre_index] > current:
                # 当比较元素大于当前元素则把比较元素后移
                arr[pre_index + 1] = arr[pre_index]
                # 往前选择下一个比较元素
                pre_index -= 1
            # 当比较元素小于当前元素，则将当前元素插入在 其后面
            arr[pre_index + 1] = current
        print(arr)
    arr=[random.randint(1,100) for x in range(1000)]
    print(arr)
    Insert_Sort(arr)

## 希尔排序 ##

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。  
希尔排序是基于插入排序的以下两点性质而提出改进方法的：  
插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率  
但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ExMzA5NTI1ODAy_size_16_color_FFFFFF_t_70_pic_center 1]

### 步骤 ###

每次以一定步长(就是跳过等距的数)进行排序，直至步长为1.

### 实现 ###

import random
    def shell_sort(list):
        n = len(list)
        # 初始步长
        gap = n // 2
        while gap > 0:
            for i in range(gap, n):
                # 每个步长进行插入排序
                temp = list[i]
                j = i
                # 插入排序
                while j >= gap and list[j - gap] > temp:
                    list[j] = list[j - gap]
                    j -= gap
                list[j] = temp
            # 得到新的步长
            gap = gap // 2
        print(list)
    arr=[random.randint(1,100) for x in range(10)]
    print(arr)
    shell_sort(arr)

## 归并排序 ##

归并操作(归并算法)，指的是将两个已经排序的序列合并成一个序列的操作。归并排序算法依赖归并操作。  
![在这里插入图片描述][20201114100940890.gif_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ExMzA5NTI1ODAy_size_16_color_FFFFFF_t_70_pic_center 2]

### 步骤 ###

#### 迭代法 ####

*  申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
 *  设定两个指针，最初位置分别为两个已经排序序列的起始位置
 *  比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
 *  重复步骤3直到某一指针到达序列尾
 *  将另一序列剩下的所有元素直接复制到合并序列尾

#### 递归法 ####

假设序列共有n个元素：

*  将序列每相邻两个数字进行归并操作，形成 \{\\displaystyle floor(n/2)\} floor(n/2)个序列，排序后每个序列包含两个元素
 *  将上述序列再次归并，形成 \{\\displaystyle floor(n/4)\} floor(n/4)个序列，每个序列包含四个元素
 *  重复步骤2，直到所有元素排序完毕

### 实现 ###

import random
    # 递归法
    def merge_sort(list):
        # 认为长度不大于1的数列是有序的
        if len(list) <= 1:
            return list
        # 二分列表
        middle = len(list) // 2
        left = merge_sort(list[:middle])
        right = merge_sort(list[middle:])
        # 最后一次合并
        return merge(left, right)
    # 合并
    def merge(left, right):
       #left=[3,22] right=[2,3,38]
       l=r=0
       result=[]
       while l<len(left) and r<len(right):
           if left[l]<right[r]:
               result.append(left[l])
               l+=1
           else:
               result.append(right[r])
               r+=1
       result+=left[l:]
       result+=right[r:]
       return result
    arr=[random.randint(1,100) for x in range(10)]
    print(arr)
    print(merge_sort(arr))

## 快速排序 ##

快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）。  
![在这里插入图片描述][20201114101242979.gif_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ExMzA5NTI1ODAy_size_16_color_FFFFFF_t_70_pic_center 3]

### 步骤 ###

*  从数列中挑出一个元素，称为”基准”（pivot），
 *  重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
 *  递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

### 实现 ###

普通版

def quick_sort(alist, start, end):
        """快速排序"""
        if start >= end:  # 递归的退出条件
            return
        mid = alist[start]  # 设定起始的基准元素
        low = start  # low为序列左边在开始位置的由左向右移动的游标
        high = end  # high为序列右边末尾位置的由右向左移动的游标
        while low < high:
            # 如果low与high未重合，high(右边)指向的元素大于等于基准元素，则high向左移动
            while low < high and alist[high] >= mid:
                high -= 1
            alist[low] = alist[high]  # 走到此位置时high指向一个比基准元素小的元素,将high指向的元素放到low的位置上,此时high指向的位置空着,接下来移动low找到符合条件的元素放在此处
            # 如果low与high未重合，low指向的元素比基准元素小，则low向右移动
            while low < high and alist[low] < mid:
                low += 1
            alist[high] = alist[low]  # 此时low指向一个比基准元素大的元素,将low指向的元素放到high空着的位置上,此时low指向的位置空着,之后进行下一次循环,将high找到符合条件的元素填到此处
    
        # 退出循环后，low与high重合，此时所指位置为基准元素的正确位置,左边的元素都比基准元素小,右边的元素都比基准元素大
        alist[low] = mid  # 将基准元素放到该位置,
        # 对基准元素左边的子序列进行快速排序
        quick_sort(alist, start, low - 1)  # start :0 low -1 原基准元素靠左边一位
        # 对基准元素右边的子序列进行快速排序
        quick_sort(alist, low + 1, end)  # low+1 : 原基准元素靠右一位 end: 最后
    
    
    
    if __name__ == '__main__':
        alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
        quick_sort(alist, 0, len(alist) - 1)
        print(alist)

进阶版

import random
    # 递归法
    def qsort(arr):
        if len(arr) <= 1:
            return arr
        else:
            pivot = arr[0]
            less = [x for x in arr[1:] if x < pivot]
            greater = [x for x in arr[1:] if x >= pivot]
            return qsort(less) + [pivot] + qsort(greater)
    arr=[random.randint(1,100) for x in range(10)]
    print(arr)
    print(qsort(arr))

## 堆排序 ##

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。  
![在这里插入图片描述][20201114101456345.gif_pic_center]

### 步骤 ###

*  创建最大堆:将堆所有数据重新排序，使其成为最大堆
 *  最大堆调整:作用是保持最大堆的性质，是创建最大堆的核心子程序
 *  堆排序:移除位在第一个数据的根节点，并做最大堆调整的递归运算

### 实现 ###

import random
    def heap_sort(list):
        # 创建最大堆
        for start in range((len(list) - 2) // 2, -1, -1):
            sift_down(list, start, len(list) - 1)
    
        # 堆排序
        for end in range(len(list) - 1, 0, -1):
            list[0], list[end] = list[end], list[0]
            sift_down(list, 0, end - 1)
        return list
    
    # 最大堆调整
    def sift_down(lst, start, end):
        root=start
        while True:
            child=root*2+1
            if child>end:
                break
            if child+1<=end and  lst[child]<lst[child+1]:
                child+=1
            if lst[child]>lst[root]:
                lst[root],lst[child]=lst[child],lst[root]
                root=child
            else:
                break
    arr=[random.randint(1,100) for x in range(10)]
    print(arr)
    print(heap_sort(arr))

# 非比较排序 #

## 计数排序 ##

当输入的元素是n个0到k之间的整数时，它的运行时间是Θ(n + k)。计数排序不是比较排序，排序的速度快于任何比较排序算法。  
由于用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。例如：计数排序是用来排序0到100之间的数字的最好的算法，但是它不适合按字母顺序排序人名。但是，计数排序可以用在基数排序算法中，能够更有效的排序数据范围很大的数组。  
![在这里插入图片描述][20201114101544430.gif_pic_center]

### 步骤 ###

找出待排序的数组中最大和最小的元素  
统计数组中每个值为i的元素出现的次数，存入数组 C 的第 i 项  
对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）  
反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1

### 实现 ###

import random
    def count_sort(arr):
        #字典来计数
        count_dic={ }
        for x in arr:
            count_dic[x]=count_dic.get(x,0)+1
        result=[]
        for key in sorted(count_dic.keys()):
            result+=[key]*count_dic[key]
        return result
    arr=[random.randint(1,100) for x in range(10)]
    print(count_sort(arr))

## 桶排序 ##

桶排序和计数排序原理类似

### 实现 ###

import random
    #桶排序
    def bucket_sort(the_list):
        #设置全为0的数组
        all_list = [0 for i in range(100)]
        last_list = []
        for v in the_list:
            all_list[v] = 1 if all_list[v]==0 else all_list[v]+1
        for i,t_v in enumerate(all_list):
            if t_v != 0:
                for j in range(t_v):
                    last_list.append(i)
        return last_list
    arr=[random.randint(1,100) for x in range(10)]
    print(arr)
    print(bucket_sort(arr))

## 基数排序 ##

基数排序(Radix Sort)是一种非比较型整数排序算法，是桶排序的扩展。基本思想是：将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。按照低位先排序，分别放入10个队列中，然后采用先进先出的原则进行收集；再按照高位排序，然后再收集；依次类推，直到最高位，最终得到排好序的数列。对于数值偏小的一组序列，其速度是非常快的，时间复杂度达到了线性，而且思想也非常的巧妙。  
[https://pic4.zhimg.com/v2-9f8cef3aa00fffbdd8496620f79088db\_b.webp][https_pic4.zhimg.com_v2-9f8cef3aa00fffbdd8496620f79088db_b.webp]

### 步骤 ###

1.取得数组中的最大数，并取得位数；  
2. 对数位较短的数前面补零；  
3. 分配，先从个位开始，根据位值(0-9)分别放到0~9号桶中;  
4. 收集，再将放置在0~9号桶中的数据按顺序放到数组中;  
5. 重复3~4过程，直到最高位，即可完成排序。

### 实现 ###

import random
    def radix_sort(arr):
        #表示第几轮
        wheel=0
        while(True):
            s=[[] for _ in range(10)]
            for x in arr:
                s[x//10**wheel%10].append(x)
            wheel+=1
            if len(s[0])==len(arr):
                return s[0]
            arr=[y for x in s for y in x]
        return arr
    arr=[random.randint(1,10000) for x in range(10)]
    print(arr)
    print(radix_sort(arr))

思路2:

from random import randint
    def radix_sort():
      A = [randint(1, 99999999) for _ in xrange(9999)]
      for k in xrange(8):
        S = [ [] for _ in xrange(10)]
        for j in A:
          S[j / (10 ** k) % 10].append(j)
        A = [a for b in S for a in b]
      for i in A:
        print(i)

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ExMzA5NTI1ODAy_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/c7a0faeb9bb941da99b08d01f6782ded.png
[20201114095516886.gif_pic_center]: /images/20221120/cc4d60cff6a649bcb3a7460032bb0aef.png
[20201114100216290.gif_pic_center]: /images/20221120/14c41bc0d50c4269b5b7c747f6f145f5.png
[20201114100431803.gif_pic_center]: /images/20221120/04b0b2d7604d4f4f8330882aa6ae670d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ExMzA5NTI1ODAy_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221120/5a8fd11392fa4abc9c869d45c1fad33e.png
[20201114100940890.gif_pic_center]: /images/20221120/bb551942ee1b4dc0ae14a91d6d372221.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ExMzA5NTI1ODAy_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221120/c989583c31e04fa29acd402224657c15.png
[20201114101242979.gif_pic_center]: /images/20221120/6c4acf22882f4497b00bcee0a442031c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ExMzA5NTI1ODAy_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221120/25bdb63756da4a30ad3eaf34a02699b7.png
[20201114101456345.gif_pic_center]: /images/20221120/277850b1094b430b978d1d80c8a1bb86.png
[20201114101544430.gif_pic_center]: /images/20221120/300fa706800e4e189b84a8a08b5f351d.png
[https_pic4.zhimg.com_v2-9f8cef3aa00fffbdd8496620f79088db_b.webp]: https://pic4.zhimg.com/v2-9f8cef3aa00fffbdd8496620f79088db_b.webp