python实现八大常见排序算法

文章目录常见的排序算法冒泡排序选择排序插入排序希尔排序归并排序快速排序计数排序基数排序 常见的排序算法 冒泡排序 每次比较相邻两个数的大小，如果不是预期排序就交换顺序。 import random def bubble_sort(blist): list_len = len(blist) for i in range(list_len): for j in range(list_len - 1): if blist[j] > blist[j+1]: blist[j], blist[j+1] = blist[ 在编程领域，排序算法是计算机科学中的基础概念，它们用于对一组数据进行排列，以便于检索、分析或处理。Python是一种流行的编程语言，其简洁的语法使得实现各种排序算法变得非常直观。本篇文章将探讨八大常见排序算法的Python实现，包括冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、计数排序和基数排序。 1. 冒泡排序（Bubble Sort） 冒泡排序是最基础的排序算法之一，它通过重复遍历待排序的列表，依次比较相邻元素并根据需要交换它们的位置来实现排序。在每一轮遍历中，最大的元素会逐渐“浮”到列表末尾。Python实现如下： ```python def bubble_sort(blist): list_len = len(blist) for i in range(list_len): for j in range(list_len - 1): if blist[j] > blist[j+1]: blist[j], blist[j+1] = blist[j+1], blist[j] ``` 2. 选择排序（Selection Sort） 选择排序的工作原理是在每一轮中找到剩余未排序部分的最小（或最大）元素，并将其放在正确的位置上。Python实现如下： ```python def select_sort(slist): list_len = len(slist) for i in range(list_len): for j in range(i + 1, list_len): if slist[i] > slist[j]: slist[i], slist[j] = slist[j], slist[i] ``` 3. 插入排序（Insertion Sort） 插入排序将列表分为已排序和未排序两部分，每次从未排序部分取出一个元素，插入到已排序部分的合适位置。Python实现如下： ```python def insert_sort(ilist): list_len = len(ilist) for i in range(1, list_len): num = ilist.pop(i) j = i - 1 while j >= 0 and ilist[j] > num: ilist[j + 1] = ilist[j] j -= 1 ilist[j + 1] = num ``` 4. 希尔排序（Shell Sort） 希尔排序是插入排序的一种优化，通过间隔序列（也称为增量序列）来减少元素的交换次数。Python实现通常使用Hibbard增量序列： ```python def shell_sort(shlist): gap = len(shlist) // 2 while gap > 0: for i in range(gap, len(shlist)): temp = shlist[i] j = i while j >= gap and shlist[j - gap] > temp: shlist[j] = shlist[j - gap] j -= gap shlist[j] = temp gap //= 2 ``` 5. 归并排序（Merge Sort） 归并排序采用分治策略，将大问题分解为小问题，然后将小问题的解合并成大问题的解。Python实现如下： ```python def merge_sort(slist): if len(slist) <= 1: return slist mid = len(slist) // 2 left = merge_sort(slist[:mid]) right = merge_sort(slist[mid:]) return merge(left, right) def merge(left, right): merged = [] i, j = 0, 0 while i < len(left) and j < len(right): if left[i] <= right[j]: merged.append(left[i]) i += 1 else: merged.append(right[j]) j += 1 merged.extend(left[i:]) merged.extend(right[j:]) return merged ``` 6. 快速排序（Quick Sort） 快速排序也是一种分治算法，通过选取一个“基准”元素，将列表分为小于和大于基准的两部分，然后递归地对这两部分进行快速排序。Python实现如下： ```python def quick_sort(slist): if len(slist) <= 1: return slist pivot = slist[0] less = [x for x in slist[1:] if x <= pivot] greater = [x for x in slist[1:] if x > pivot] return quick_sort(less) + [pivot] + quick_sort(greater) ``` 7. 计数排序（Counting Sort） 计数排序适用于非负整数排序，它统计每个数出现的次数，然后根据这些统计结果生成排序后的序列。Python实现如下： ```python def counting_sort(slist): max_val = max(slist) count = [0] * (max_val + 1) for num in slist: count[num] += 1 sorted_list = [] for i, c in enumerate(count): sorted_list.extend([i] * c) return sorted_list ``` 8. 基数排序（Radix Sort） 基数排序是按照数字的每一位分别进行排序，通常使用计数排序作为子步骤。Python实现相对复杂，涉及到多位数的处理。 以上就是八大常见排序算法的Python实现。每种排序算法都有其适用场景和优缺点，例如冒泡排序简单但效率较低，而快速排序则速度快但可能有最坏情况。了解和掌握这些排序算法有助于我们更好地理解和优化算法，提高程序性能。