Python实例代码，十大经典排序算法（附算法思想、实例代码，值得收藏学习）

排序算法是《数据结构与算法》中最基本的算法之一，适合Python初学者上手实践，检验**python基础知识（列表、循环语句、if语句、函数等）**掌握情况。

排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。此篇文章内容来自个人梳理总结，参考来源**《王道丛书–数据结构》、菜鸟教程以及博客园经典排序算法**。

1 插入排序

1.1 基本思想

每次将一个待排序的记录按其关键字大小插入前面已排好序的子序列，直到全部记录插入完成。假设待排序表L[1…n]在某次排序过程中的某一时刻状态如下：有序序列L[1…i-1]，L[i]，无序序列L[i+1…n]。

1.2 算法步骤

1. 查找L[i]在L[1…i-1]中的插入位置k;
2. 将L[k…i-1]中的所有元素依次后移一个位置；
3. 将L[i]复制到L[k]。

为了实现对L[1…n]的排序，可以将L[2]- L[n]依次插入前面已排好序的子序列，初始L[1]可以视为一个已排好序的子序列。

1.3 动画演示

1.4 算法代码

算法中列表中第一个元素下标从0开始计算。

 #直接插入排序
 def InsertSort(array):
     n=len(array)                     #求出待排序列表长度，即列表中元素个数
     for i in range(1,n):            #初始list[0]可以视为一个已排好序的子序列，从list[1]开始往后遍历，range(1,n)代表1,2,3...n-1,共遍历n-1次
         for j in range(i,0,-1):     #开始1趟遍历，如果后面的元素比前面的小，进行交换
             if(array[j]<array[j-1]):
                 array[j],array[j-1]=array[j-1],array[j]
             else:
                 break
 
 #实例代码：
 array_A=[3,8,18,4,29,6,12]
 InsertSort(array_A)
 print(array_A)
 
 #输出结果：
 [3, 4, 6, 8, 12, 18, 29, 100]

2 冒泡排序

2.1基本思想

从后往前（或从前往后）两两比较相邻元素的值，若为逆序（即L[i-1]> L[i]），则交换它们位置，直到序列比较完，程这样的过程为“一趟”冒泡排序。第一趟冒泡排序，结果是将最小的元素交换到带排序的第一个位置，第二趟冒泡排序，结果是将第二小的元素交换到带排序的第二个位置。这样最多做n-1趟。

2.2 算法步骤

1. 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
3. 针对所有的元素重复以上的步骤，除了最后一个；
4. 重复步骤1~3，直到排序完成。

2.3 动画演示

2.4 算法代码

算法中列表中第一个元素下标从0开始计算。

 #冒泡排序
 def BubbleSort(array):
     n=len(array)                         #求出待排序列表长度，即列表中元素个数
     for i in range(n):
         for j in range(n-1,i,-1):       #一趟冒泡排序
             if(array[j]<array[j-1]):      #若为逆序
                 array[j],array[j-1]=array[j-1],array[j]     #交换
 
 #实例代码：
 array_A=[6,9,2,12,4,67,35]
 BubbleSort(array_A)
 print(array_A)
 
 #输出结果：
 [2, 4, 6, 9, 12, 35, 67]

3 选择排序

3.1 基本思想

将表分为两部分，有序部分和无序部分。每次从无序部分中选取最小的元素，然后将其放入有序部分中。假设排序表为L[1…n]，第i趟排序即从L[i…n]中选择关键字最小的元素与L[i]交换，每一趟排序可以确定一个元素的最终位置，这样经过n-1趟排序就可使得整个排序表有序。

3.2 算法步骤

1. 初始状态：无序区为L[1…n]，有序区为空；
2. 第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为L[1…i-1]和L[i…n]。该趟排序从当前无序区中选出关键字最小的记录 L[k]，将它与无序区的第1个记录L[i]交换，使L[1…i]和L[i+1…n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
3. n-1趟结束，数组有序化了。

3.3 动画演示

3.4 算法代码

算法中列表中第一个元素下标从0开始计算。

 #简单选择排序
 def SelectSort(array):
     n=len(array)         #求出待排序列表长度，即列表中元素个数
     for i in range(n):  #一共进行n-1趟排序
         min=i           #记录最小元素位置
         for j in range(i+1,n):      #在L[i...n-1]中选择最小的元素
             if(array[j]<array[min]):  
                 min=j               #更新最小元素位置
         if(min!=i):
             array[i],array[min]=array[min],array[i]     #交换
             
 #实例代码：
 array_A=[7,2,15,45,26,18,35]
 SelectSort(array_A)
 print(array_A)
 
 #输出结果：
 [2, 7, 15, 18, 26, 35, 45]

4 希尔排序

4.1 基本思想

先追求表中元素部分有序，再逐渐逼近全局有序。先将待排序表分割成若干形如L[i,i+d,i+2d,…i+kd]的“特殊”子表，对各个子表分别进行直接插入排序。缩小增量d，重复上述过程，直到d=1为止。

4.2 算法步骤

1. 选择一个增量递减序列d1，d2，…，dk，其中d一直递减，直到dk=1；
2. 按增量序列个数k，对序列进行k 趟排序；
3. 每趟排序，根据对应的增量di，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

4.3 动画演示

4.4 算法代码

算法中列表中第一个元素下标从0开始计算。

 #希尔排序
 def ShellSort(array):
     n=len(array)
     dk=n//2                     #初始化增量为数组长度的一半，//整除
     while(dk>=1):               #增量必须是大于1的整数
         for i in range(dk,n):   #遍历需要进行插入排序的数
             ind=i
             while(ind>=dk and array[ind]<array[ind-dk]):      #对每组进行插入排序
                 array[ind],array[ind-dk]=array[ind-dk],array[ind]   #交换
                 ind=ind-dk
         dk=dk//2                #增量缩小一半
 
 #实例代码：
 array_A=[100,2,17,23,56,16,35]
 ShellSort(array_A)
 print(array_A)
 
 #输出结果：
 [2, 16, 17, 23, 35, 56, 100]

5 归并排序

5.1 基本思想

归并的含义是指将两个或两个以上的有序表组合成一个新的有序表。假定带排序表含有n个记录，则可将其视为n个有序的子表，每个子表的长度为1，然后两两归并得到 n/2 （向下取整）个长度为2或1的有序表；如此重复两两归并，直到合并成一个长度为n的有序表为止。

5.2 算法步骤

1. 把长度为n的输入序列分成两个长度为n/2的子序列；
2. 对这两个子序列分别采用归并排序；
3. 将两个排序好的子序列合并成一个最终的排序序列。

5.3 动画演示

5.4 算法代码

算法中列表中第一个元素下标从0开始计算。

 #归并排序
 def merge(left, right):
     l, r = 0, 0             # 初始化两个指针l, r, 初始位置为起始位置
     temp_list=[]                        #初始化一个临时数组temp_list    
     while(l<len(left) and r<len(right)):  #while循环用于合并两个有序数组
         if(left[l]<right[r]):
             temp_list.append(left[l])
             l=l+1
         else:
             temp_list.append(right[r])
             r=r+1
     temp_list+=left[l:]         #把数组未添加的部分加到结果数组末尾
     temp_list+=right[r:]
     return temp_list            #返回已排序的数组
 
 def MergeSort(array):
     n=len(array)
     if(n<2):                #递归边界条件
         return array         #到达边界时返回当前的子数
     middle=n//2             #求出数组的中位数
     left=array[:middle]
     right=array[middle:]
     return merge(MergeSort(left), MergeSort(right))     #调用merge函数分别为左右数组排序
 
 #实例代码：
 array_A=[100,2,17,23,56,16,35]
 print(MergeSort(array_A))
 
 #输出结果：
 [2, 16, 17, 23, 35, 56, 100]

6 快速排序

6.1 基本思想

基于分治法，在待排序L[1…n]中人取一个元素pivot基准（通常取首元素），通过一趟排序将待排序表分为独立的两部分L[1…k-1]和L[k+1…n]，使得L[1…k-1]中的所有元素小于pivot，L[k+1…n]中的所有元素都大于等于pivot，则pivot放在了其最终位置L[k]上，这个过程称为一趟快速排序。然后分别递归地对两个子表重复上述过程，直至每部分内只有一个元素或空为止。

6.2 算法步骤

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

6.3 动画演示

6.4 算法代码

算法中列表中第一个元素下标从0开始计算。

 #快速排序
 def QuickSort(array):
     if len(array) <= 1:              #边界条件
         return array
     key = array[0]                       #取数组的第一个数为基准数
     llist,rlist,mlist = [],[],[key]     #定义空列表，分别存储小于/大于/等于基准数的元素
     for i in range(1,len(array)):        #遍历数组，把元素归类到3个列表中
         if array[i] > key:
             rlist.append(array[i])
         elif array[i] < key:
             llist.append(array[i])
         else:
             mlist.append(array[i])
     return QuickSort(llist)+mlist+QuickSort(rlist) #对左右子列表快排，拼接3个列表并返回
 
 #实例代码：
 array_A=[23,2,57,3,26,16,35,45]
 print(QuickSort(array_A))
 
 #输出结果：
 [2, 3, 16, 23, 26, 35, 45, 57]

7 基数排序

7.1 基本思想

基于关键字各位的大小进行排序，第一种是最高位优先法（MSD），按关键字权重递减依次逐层划分成若干更小的子序列，最后将子序列依次连接成一个有序序列；另一种是最低位优先法（LSD），按关键字权重递增依次进行排序，最后形成一个有序序列。

7.2 算法步骤

此算法我们研究最低位优先法，按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。

1. 取得数组中的最大数，并取得位数；
2. list为原始数组，从最低位开始取每个位组成radix数组；
3. 对radix进行计数排序（利用计数排序适用于小范围数的特点）；

7.3 动画演示

7.4 算法代码

算法中列表中第一个元素下标从0开始计算。

 #基数排序
 def RadixSort(array):
     max_num = max(array)                #求出列表中最大元素
     place = 1
     while max_num >= 10**place:     #循环条件，如果10的place次方小于等于max_num
         place += 1
     for i in range(place):
         buckets = [[] for _ in range(10)]   #生成10个桶
         for var in array:
             radix = int(var/(10**i) % 10)   #每次循环，依次此数字个位、十位、百位...数值
             buckets[radix].append(var)      #分桶
         j = 0
         for k in range(10):                 #分桶完成，将数据依次取出
             for var in buckets[k]:
                 array[j] = var              #将数据重新写回list
                 j += 1
     return array
 
 #实例代码：
 array_A=[23,2,57,3,26,16,35,45]
 RadixSort(array_A)
 print(array_A)
 
 #输出结果：
 [2, 3, 16, 23, 26, 35, 45, 57]

8 计数排序

8.1 基本思想

计数排序先找到待排序列表中的最大值 k，开辟一个长度为 k+1 的计数列表，计数列表中的所有初始值都为 0。走访待排序列表，如果走访到的元素值为 i，则计数列表中索引 i 的值加1，走访完整个待排序列表，就可以统计出待排序列表中每个值的数量。然后创建一个新列表，根据计数列表中统计的数量，依次在新列表中添加对应数量的 i ，得到排好序的列表。

8.2 算法步骤

1. 找到待排序列表中的最大值 k，开辟一个长度为 k+1 的计数列表，计数列表中的值都为 0。
2. 走访待排序列表，如果走访到的元素值为 i，则计数列表中索引 i 的值加1。
3. 走访完整个待排序列表，计数列表中索引 i 的值 j 表示 i 的个数为 j，统计出待排序列表中每个值的数量。
4. 创建一个新列表，遍历计数列表，依次在新列表中添加 j 个 i，新列表就是排好序后的列表，整个过程没有比较待排序列表中的数据大小。

8.3 动画演示

8.4 算法代码

算法中列表中第一个元素下标从0开始计算。

 #计数排序
 def CountingSort(array):
     if len(array) < 2:
         return array
     max_num = max(array)
     count = [0] * (max_num + 1)
     for num in array:
         count[num] += 1
     new_array = list()
     for i in range(len(count)):
         for j in range(count[i]):
             new_array.append(i)
     return new_array
 
 #实例代码
 list_A=[23,2,57,3,16,35,45,123,67]
 print(CountingSort(list_A))
 
 #输出结果：
 [2, 3, 16, 23, 35, 45, 57, 67, 123]

9 堆排序

9.1 基本思想

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：

1. 大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
2. 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；

9.2 算法步骤

1. 将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
2. 将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
3. 由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。

9.3 动画演示

9.4 算法代码

#堆排序
def MAX_Heapify(heap,HeapSize,root):	#在堆中做结构调整使得父节点的值大于子节点
    left = 2*root + 1
    right = left + 1
    larger = root
    if left < HeapSize and heap[larger] < heap[left]:
        larger = left
    if right < HeapSize and heap[larger] < heap[right]:
        larger = right
    if larger != root:		#如果做了堆调整则larger的值等于左节点或者右节点的，这个时候做对调值操作
        heap[larger],heap[root] = heap[root],heap[larger]
        MAX_Heapify(heap, HeapSize, larger)

def Build_MAX_Heap(heap):	#构造一个堆，将堆中所有数据重新排序
    HeapSize = len(heap)	#将堆的长度当独拿出来方便
    for i in range((HeapSize -2)//2,-1,-1):		#从后往前出数
        MAX_Heapify(heap,HeapSize,i)

def HeapSort(heap):			#将根节点取出与最后一位做对调，对前面len-1个节点继续进行对调整过程。
    Build_MAX_Heap(heap)
    for i in range(len(heap)-1,-1,-1):
        heap[0],heap[i] = heap[i],heap[0]
        MAX_Heapify(heap, i, 0)
    return heap

#实例代码
array_A=[3,14,100,12,23,78,15,9,98]
HeapSort(array_A)
print(array_A)

#输出结果：
[3, 9, 12, 14, 15, 23, 78, 98, 100]

10 桶排序

10.1 基本思想

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。

10.2 算法步骤

1. 设置一个定量的数组当作空桶；
2. 遍历输入数据，并且把数据一个一个放到对应的桶里去；
3. 对每个不是空的桶进行排序；
4. 从不是空的桶里把排好序的数据拼接起来。

10.3 动画演示

10.4 算法代码

#桶排序
def bucket_sort(array):
    min_num, max_num = min(array), max(array)
    bucket_num = (max_num-min_num)//3 + 1
    buckets = [[] for _ in range(int(bucket_num))]
    for num in array:
        buckets[int((num-min_num)//3)].append(num)
    new_array = list()
    for i in buckets:
        for j in sorted(i):
            new_array.append(j)
    return new_array

#实例
array_A=[3,14,56,12,23,78,15,9,98]
bucket_sort(array_A)
print(array_A)

#输出结果：
[3, 14, 56, 12, 23, 78, 15, 9, 98]

11 算法性能分析

通过下面一张图，对上述10种算法的时间复杂度、空间复杂度、排序方式和稳定性进行对比分析。

最后

如果对Python感兴趣的话，可以试试我的学习方法以及相关的学习资料

点此免费领取：CSDN大礼包：《python学习路线&全套学习资料》免费分享

一、Python所有方向的学习路线

Python所有方向的技术点做的整理，形成各个领域的知识点汇总，它的用处就在于，你可以按照上面的知识点去找对应的学习资源，保证自己学得较为全面。

二、Python必备开发工具

三、Python视频合集

观看零基础学习视频，看视频学习是最快捷也是最有效果的方式，跟着视频中老师的思路，从基础到深入，还是很容易入门的。

四、实战案例

光学理论是没用的，要学会跟着一起敲，要动手实操，才能将自己的所学运用到实际当中去，这时候可以搞点实战案例来学习。

五、Python练习题

检查学习结果。

六、面试资料

我们学习Python必然是为了找到高薪的工作，下面这些面试题是来自阿里、腾讯、字节等一线互联网大厂最新的面试资料，并且有阿里大佬给出了权威的解答，刷完这一套面试资料相信大家都能找到满意的工作。


这份完整版的Python全套学习资料已经上传CSDN，朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费】