python实现常见的排序算法

大家好，欢迎来到IT知识分享网。

一、冒泡排序

def bubble_sort(arr): n = len(arr) for i in range(0, n): # 表示排序的轮次 is_swap = False # 表示是否在该轮次有交换操作 for j in range(1, n-i): if arr[j] < arr[j-1]: arr[j], arr[j-1] = arr[j-1], arr[j] is_swap = True if not is_swap: # 若是该轮次没有交换操作，说明所有元素已经排好序了 return arr 

二、插入排序

def insertion_sort(arr): n = len(arr) for i in range(1, n): tmp = arr[i] # 将当前要比较的未排序元素存到临时变量tmp，方便后移 j = i - 1 while j >= 0 and arr[j] > tmp: # 从后往前遍历已排序元素，若是大于tmp，就往后移一位，否则，就将tmp插到该元素后面 arr[j+1] = arr[j] j -= 1 arr[j+1] = tmp return arr 

三、归并排序

归并排序：稳定排序，最差和平均和最好时间复杂度O(nlogn)；空间复杂度是O(n)，即临时存储空间；适用于大数据量、稳定性要求高、链表结构等的排序。

思路：分而治之策略，先将数组递进地对半分组，直到每组仅剩一个元素时，开始两两之间归并，归并操作是将两个较短的已排序的数组合并为一个较长的排序的数组。

def merge_sort(arr): # 先将数组不断对半拆分成更小的数组，直到每个数组只剩下一个元素 if len(arr) > 1: mid = len(arr) // 2 left = arr[:mid] right = arr[mid:] merge_sort(left) merge_sort(right) # 然后将数组两两合并，此时需要合并的数组是有序的。 i = j = k = 0 while i < len(left) and j < len(right): if left[i] < right[j]: arr[k] = left[i] i += 1 else: arr[k] = right[j] j += 1 k += 1 # 合并后，如果有剩余的元素，需要将其添加到数组后面 while i < len(left): arr[k] = left[i] i += 1 k += 1 while j < len(right): arr[k] = right[j] j += 1 k += 1 return arr

四、快速排序

快速排序：不稳定排序，最好和平均时间复杂度是O(nlogn)，最差时间复杂度是O(n^2)，即原数组是排好序的情况；空间复杂度是O(logn)；适用于大规模数据且内存有限的情况。

思路：随机选择一个基准，将小/大于它的元素置于其前/后，由此将数组划分成小于和大于基准的两部分，然后，递归地对子数组执行上述操作，直到子数组只剩一个元素位置。

1、递归 

def quickSort(arr, low, high): if low < high: # 当子数组长度为1时，停止递归 pivot = arr[low] # 基准值可选数组首个/末尾元素或随机选取 left, right = low, high # 遍历数组，将小于基准值的元素放到左边，大于的放右边 while low < high: while low < high and arr[high] > pivot: high -= 1 arr[low] = arr[high] while low < high and arr[low] <= pivot: low += 1 arr[high] = arr[low] arr[low] = pivot # 递归地对基准左右两边的子数组分别重复上述操作，直到子数组长度为1为止 quickSort(arr, left, low-1) quickSort(arr, low+1, right) return arr

2、stack 

def quickSort_stack(arr): left, right = 0, len(arr)-1 stack = [left, right] # 用栈存储子数组的左右边界索引 while stack: right = stack.pop() left = stack.pop() if left >= right: # 左右边界相遇的子数组，无需继续排序 continue # 使用双指针，将小于基准的元素放到左边，大于的放右边，i指向小于基准值的序列的最后一个位置 pivot = arr[right] i = left - 1 for j in range(left, right): if arr[j] < pivot: i += 1 arr[i], arr[j] = arr[j], arr[i] arr[i+1], arr[right] = arr[right], arr[i+1] stack.extend([left, i, i+2, right]) # 左右子数组的左右边界索引入栈 return arr

3、用双指针快排

def quickSort(arr, low, high): if low < high: # 当子数组长度为1时，停止递归 # 选择一个基准值，将小于基准值的元素放到其左边，大于的放右边 pivot = arr[high] # 基准值可选数组首个/末尾元素或随机选取 i = low - 1 # i指向小于基准值的序列的最后一个位置 # 遍历数组，遇到小于基准值的元素，i向前一步，与i处元素交换位置 for j in range(low, high): if arr[j] < pivot: i += 1 arr[i], arr[j] = arr[j], arr[i] arr[i+1], arr[high] = arr[high], arr[i+1] # 递归地对基准左右两边的子数组分别重复上述操作，直到子数组长度为1为止 quickSort(arr, low, i) quickSort(arr, i+2, high) return arr

五、选择排序

def selection_sort(arr): # 遍历数组，每次从未排序数组中找出最小值并放到未排序数组开头，直到全部排序完毕 n = len(arr) for i in range(n-1): # i指向未排序数组的首位置 min_idx = i for j in range(i+1, n): # 从后面找到最小值并与i位置元素交换 if arr[j] < arr[min_idx]: min_idx = j arr[i], arr[min_idx] = arr[min_idx], arr[i] return arr

六、堆排序

堆排序：不稳定排序，平均时间复杂度是O(nlogn)，空间复杂度O(1)；它是利用堆设计的一种排序算法，堆积是一个近似二叉树的结构，并满足堆的性质，即子节点索引大于（小于）父节点的。

大顶堆：每个节点值大于等于其子节点值，用于堆排序中的升序：key[i]>=key[2i+1]，key[i]>=key[2i+2];

小顶堆：每个节点值小于等于其子节点值，用于堆排序中的降序：key[i]<=key[2i+1]，key[i]<=key[2i+2];

堆是一个完全二叉树，所以，假设某一节点序号为i，则其左节点是2i+1，右节点是2i+2，i从0开始；最后一个非叶子结点的序号是 n//2-1 (若n为偶数，最后一个非叶子节点只有左叶子n-1，该非叶子节点是n//2-1；同理，若n为奇数，最后一个非叶子节点为(n-1-2)//2=n//2-1，向下取整)。

思路：1）建堆，初始化待排序数组为大顶堆；2）交换堆顶和最后一个元素；3）除过最后一个元素，对新堆顶元素堆化；4）重复上述步骤，直到堆中只剩一个元素。

def heapify(arr, i, n): # 建立大顶堆，即每个节点大于等于其子节点值 dad = i son = 2 * i + 1 while son < n: if son+1 < n and arr[son+1] > arr[son]: # 找出左右子节点中较大的节点 son += 1 if arr[son] <= arr[dad]: # 如果子节点小于父节点，则跳出循环 break arr[son], arr[dad] = arr[dad], arr[son] # 否则交换父子节点，并继续向下比较 dad = son son = 2 * dad + 1 def heap_sort(arr): n = len(arr) for i in range(n//2-1, -1, -1): # 从最后一个非叶子节点开始，建立大顶堆 heapify(arr, i, n) # 将堆顶元素即arr[0]与最后一个元素交换，然后将堆的大小减一，并对新的堆顶重新建立大顶堆 for i in range(n-1, 0, -1): arr[0], arr[i] = arr[i], arr[0] heapify(arr, 0, i) return arr

七、希尔排序

希尔排序：不稳定排序，时间复杂度与增量gap选择有关，最坏O(n^2)，平均O(n^1.3)，空间复杂度O(1)；通过对插入排序引入间隔序列提高效率；适用于中等规模数据。

思路：1)显示设定一个增量gap，2)然后对相距gap的元素进行插入排序，3)缩小增量gap；4）重复步骤2、3，直到gap不大于0。

def shell_sort(arr): n = len(arr) gap = 1 while gap < n/3: gap = 3 * gap + 1 while gap > 0: for i in range(gap, n): tmp = arr[i] j = i - gap while j >= 0 and arr[j] > tmp: arr[j+gap] = arr[j] j -= gap arr[j+gap] = tmp gap = (gap - 1) // 3 return arr

八、计数排序

计数排序：稳定排序，时间复杂度是O(n+k)，空间复杂度是O(k)，n表示原数组长度，k表示原数组的数值范围，该算法不涉及比较操作；适用于时间复杂度要求线性、数值范围小、密集分布的整数排序。

思路：1）获取数组的最小最大值，确定计数范围；2）用一个数组counter统计原数组每个元素出现的次数，counter的索引对应于原数组元素值；3）遍历counter，根据计数值和索引，填充原数组。

1. 非稳定

def counting_sort(arr): n = len(arr) max_val, min_val = max(arr), min(arr) # 找出数组的最大值和最小值 counter = [0] * (max_val-min_val+1) # 定义计数器数组，长度为数组元素的范围 for i in arr: # 用counter数组统计每个元素出现的次数，索引为元素值-最小值 counter[i-min_val] += 1 # 遍历counter数组，根据每个元素出现的次数，将其依次添加到原数组中 k = 0 for i in range(max_val-min_val+1): for j in range(counter[i]): arr[k] = i + min_val k += 1 return arr

2.  稳定 

def counting_sort(arr): # 只计算数组最大值，最小值默认为0，建立计数数组 m = max(arr) counter = [0] * (m+1) for a in arr: counter[a] += 1 # 计算累加和，此时counter[i]-1代表的是i元素在排序后的数组存放的最后一个位置（同一元素可能存在多个） for i in range(1, m+1): counter[i] += counter[i-1] # 建立一个与原数组同size的数组res，倒序遍历原数组，将每个元素根据上述所说放入适当的位置 n = len(arr) res = [0] * n for i in range(n-1, -1, -1): a = arr[i] res[counter[a]-1] = a # counter[i]-1代表的是i元素在排序后的数组存放的最后一个位置（同一元素可能存在多个） counter[a] -= 1 # 当放了一个元素后，该元素对应的counter值要减一，对应该元素下次出现时的位置 # 将排序后的数组放回原数组 for i in range(n): arr[i] = res[i]

九、桶排序

桶排序：其稳定性视使用的桶内排序算法而异，平均时间复杂度O(n+k)，空间复杂度是O(n+k)，其中，n是数组长度，k是桶数；适用于分布均匀、数据范围确定、规模小的整数排序。

思路：将数组元素划分到不同值范围的桶中，单个桶中的元素进行排序，然后将各个桶的元素合并。

步骤：1）获取数组最大最小值，确定数组值范围，并且设定一个桶size；2）根据值范围和桶size，计算需要的桶数量；3）将元素放进桶中，对于每个元素v，(v-minv)//桶size 就是其对应的桶索引；4）桶内元素排序；5）将各个桶元素按顺序放回原数组。

 def bucket_sort(arr): n = len(arr) min_val, max_val = min(arr), max(arr) # 找出数组的最大值和最小值 bucketSize = 100 # 定义桶的大小 bucktNum = (max_val - min_val) // bucketSize+ 1 # 计算桶的数量 buckets = [[] for _ in range(bucktNum)] # 定义桶数组 for i in arr: # 将元素放入对应桶中 b_idx = (i - min_val) // bucketSize # 计算元素所在的桶的索引 buckets[b_idx].append(i) for i in range(bucktNum): # 对每个桶进行排序 buckets[i].sort() # 将桶中的元素依次添加到原数组中 k = 0 for tmp in buckets: for j in tmp: arr[k] = j k += 1 return arr 

十、基数排序

基数排序：稳定排序，时间复杂度是O(d(n+k))，空间复杂度是O(n+k)，其中n是数组长度，k是值范围长度，d是最大位数，相当于进行了d次计数排序；适用于位数小、范围确定、规模适中的整数、或字符串、时间日期等的排序。

思路：1）获取数组最大值，确定数值最大位数；2）从低位到高位，根据数组各个元素的相同位做计数排序。

def counting_sort_digit(arr, exp, n): counter = [0] * 10 # 定义计数器数组，长度为10 output = [0] * n # 定义输出数组，长度为n for i in arr: # 用counter数组统计每个元素的第exp位数出现的次数 idx = (i // exp) % 10 # 计算元素的第exp位数 counter[idx] += 1 for i in range(1, 10): # 计算累加和，此时counter[i]-1代表的是i元素在排序后的数组存放的最后一个位置 counter[i] += counter[i-1] i = n - 1 while i >= 0: # 倒序遍历原数组，将每个元素根据上述所说放入适当的位置 idx = (arr[i] // exp) % 10 output[counter[idx]-1] = arr[i] counter[idx] -= 1 i -= 1 for i in range(n): arr[i] = output[i] def radix_sort(arr): n = len(arr) max_val = max(arr) exp = 1 # 定义基数 while max_val // exp > 0: # 基数排序的次数 counting_sort_digit(arr, exp, n) exp *= 10 # 基数翻倍 return arr