本期导读
排序算法可以说是每个程序员都必须得掌握的了, 弄明白它们的原理和实现很有必要，以下为大家介绍十大常用排序算法的python实现方式，方便大家学习。
01 冒泡排序——交换类排序
02 快速排序——交换类排序
03 选择排序——选择类排序
04 堆排序——选择类排序
05 插入排序——插入类排序
06 希尔排序——插入类排序
07 归并排序——归并类排序
08 计数排序——分布类排序
09 基数排序——分布类排序
10 桶排序——分布类排序
01冒泡排序冒泡排序（Bubble Sort）: 一个经典的排序算法，因在算法运行中，极值会像水底的气泡一样逐渐冒出来，因此而得名。
算法原理：
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
代码如下：
'''冒泡排序''' def Bubble_Sort(arr): for i in range(1, len(arr)): for j in range(0, len(arr)-i): if arr[j] > arr[j+1]: arr[j], arr[j + 1] = arr[j + 1], arr[j] return arr arr = [29, 63, 41, 5, 62, 66, 57, 34, 94, 22] result = Bubble_Sort(arr) print('result list: ', result) # result list: [5, 22, 29, 34, 41, 57, 62, 63, 66, 94]
02快速排序快速排序（Quicksort）：通过一趟排序将要排序的数据分割成独立的两部分，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列，是对冒泡排序算法的一种改进。
算法原理：
- 首先设定一个分界值，通过该分界值将数组分成左右两部分。
- 将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。
- 然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
- 重复上述过程，直到左、右两个部分各数据排序完成。
代码如下：
'''快速排序''' def Quick_Sort(arr): # 递归入口及出口 if len(arr) >= 2: # 选取基准值，也可以选取第一个或最后一个元素 mid = arr[len(arr) // 2] # 定义基准值左右两侧的列表 left, right = [], [] # 从原始数组中移除基准值 arr.remove(mid) for num in arr: if num >= mid: right.append(num) else: left.append(num) return Quick_Sort(left) + [mid] + Quick_Sort(right) else: return arr arr = [27, 70, 34, 65, 9, 22, 47, 68, 21, 18] result = Quick_Sort(arr) print('result list: ', result) # result list: [9, 18, 21, 22, 27, 34, 47, 65, 68, 70]
03选择排序选择排序（Selection sort）：是一种简单直观的排序算法。无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。
算法原理：
- 在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
- 从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
- 以此类推，直到所有元素均排序完毕。
代码如下：
'''选择排序''' def Selection_Sort(arr): for i in range(len(arr) - 1): # 记录最小数的索引 minIndex = i for j in range(i + 1, len(arr)): if arr[j] < arr[minIndex]: minIndex = j # i 不是最小数时，将 i 和最小数进行交换 if i != minIndex: arr[i], arr[minIndex] = arr[minIndex], arr[i] return arr arr = [5, 10, 76, 55, 13, 79, 49, 51, 65, 30] result = Quick_Sort(arr) print('result list: ', result) # result list: [5, 10, 13, 30, 49, 51, 55, 65, 76, 79]
04插入排序插入排序（Insertion Sort）：一般也被称为直接插入排序，是一种最简单直观的排序算法。
算法原理：
- 将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
- 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。
代码如下：
'''插入排序''' def Insertion_Sort(arr): for i in range(1, len(arr)): key = arr[i] j = i - 1 while j >= 0 and key < arr[j]: arr[j + 1] = arr[j] j -= 1 arr[j + 1] = key return arr arr = [31, 80, 42, 47, 35, 26, 10, 5, 51, 53] result = Insertion_Sort(arr) print('result list: ', result) # result list: [5, 10, 26, 31, 35, 42, 47, 51, 53, 80]
05堆排序堆排序（Heap sort）：是指利用堆这种数据结构所设计的一种排序算法，堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。
算法原理：
- 创建一个堆 H[0……n-1]；
- 把堆首（最大值）和堆尾互换；
- 把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；
- 重复步骤 2，直到堆的尺寸为 1。
代码如下：
'''堆排序''' def Heapify(arr, n, i): largest = i # 左右节点分块 left = 2 * i + 1 right = 2 * i + 2 if left < n and arr[i] < arr[left]: largest = left if right < n and arr[largest] < arr[right]: largest = right if largest != i: # 大小值交换 arr[i], arr[largest] = arr[largest], arr[i] # 递归 Heapify(arr, n, largest) def Heap_Sort(arr): nlen = len(arr) for i in range(nlen, -1, -1): # 调整节点 Heapify(arr, nlen, i) for i in range(nlen - 1, 0, -1): arr[i], arr[0] = arr[0], arr[i] # 调整节点 Heapify(arr, i, 0) return arr arr = [26, 53, 83, 86, 5, 46, 72, 21, 4, 75] result = Heap_Sort(arr) print('result list: ', result) # result list: [4, 5, 21, 26, 46, 53, 72, 75, 83, 86]
往期推荐
12306火车票查询--Python可以这么玩！！！
17张“高逼格”程序员壁纸，你品！你细品！！！
END
以上就是本期为大家整理的全部内容了，赶快练习起来吧，喜欢的朋友可以
点赞、点在看
也可以分享到朋友圈让更多人知道哦
