史上最简单十大排序算法（Python实现）

您所在的位置：网站首页 › python排序函数代码 › 史上最简单十大排序算法（Python实现）

史上最简单十大排序算法（Python实现）

2023-12-03 08:56| 来源: 网络整理| 查看: 265

十大排序算法（Python实现）

一. 算法介绍及相关概念解读

算法分类

相关概念

1. 交换排序

1.1 冒泡排序(Bubble Sort)

1.2 快速排序(Quick Sort)

2. 插入排序

2.1 简单插入排序(Insert Sort)

2.2 希尔排序(Shell Sort)

3.选择排序

3.1 简单选择排序(Select Sort)

3.2 堆排序(Heap Sort)

4. 归并排序

4.1 二路归并排序(Two-way Merge Sort)

5. 线性时间非比较类排序

5.1 计数排序（Counting Sort）

5.2 桶排序（Bucket Sort）

5.3 基数排序（Radix Sort）

十大排序算法（Python实现）一. 算法介绍及相关概念解读

算法分类

十种常见排序算法可以分为两大类：

非线性时间比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此称为非线性时间比较类排序。

线性时间非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此称为线性时间非比较类排序。

相关概念稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。 1. 交换排序 1.1 冒泡排序(Bubble Sort) 比较相邻的元素。如果第一个比第二个大，就交换它们两个；对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；针对所有的元素重复以上的步骤，除了最后一个；重复步骤1~3，直到排序完成。

冒泡排序对n个数据操作n-1轮，每轮找出一个最大（小）值。

操作只对相邻两个数比较与交换，每轮会将一个最值交换到数据列首（尾），像冒泡一样。

每轮操作O(n)次，共O（n）轮，时间复杂度O(n^2)。

额外空间开销出在交换数据时那一个过渡空间，空间复杂度O(1)

def BubbleSort(lst): n=len(lst) if nlst[j+1]: (lst[j],lst[j+1])=(lst[j+1],lst[j]) return lst x=input("请输入待排序数列：\n") y=x.split() arr=[] for i in y: arr.append(int(i)) arr=BubbleSort(arr) #print(arr) print("数列按序排列如下：") for i in arr: print(i,end=' ') 1.2 快速排序(Quick Sort) 从数列中挑出一个元素，称为 “基准”（pivot）；重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

快速排序基于选择划分，是简单选择排序的优化。

每次划分将数据选到基准值两边，循环对两边的数据进行划分，类似于二分法。

算法的整体性能取决于划分的平均程度，即基准值的选择，此处衍生出快速排序的许多优化方案，甚至可以划分为多块。

基准值若能把数据分为平均的两块，划分次数O(logn)，每次划分遍历比较一遍O(n)，时间复杂度O(nlogn)。

额外空间开销出在暂存基准值，O(logn)次划分需要O(logn)个，空间复杂度O(logn)

def QuickSort(lst): # 此函数完成分区操作 def partition(arr, left, right): key = left # 划分参考数索引,默认为第一个数为基准数，可优化 while left < right: # 如果列表后边的数,比基准数大或相等,则前移一位直到有比基准数小的数出现 while left < right and arr[right] >= arr[key]: right -= 1 # 如果列表前边的数,比基准数小或相等,则后移一位直到有比基准数大的数出现 while left < right and arr[left] = right: return # 从基准开始分区 mid = partition(arr, left, right) # 递归调用 # print(arr) quicksort(arr, left, mid - 1) quicksort(arr, mid + 1, right) # 主函数 n = len(lst) if n =0 and arr[j]>temp): #从后向前，找打比其小的数的位置 arr[j+d]=arr[j] #向后挪动 j-=d if j!=i-d: arr[j+d]=temp n=len(lst) if n=1: shellinsert(lst,d) d=d//2 return lst x=input("请输入待排序数列：\n") y=x.split() arr=[] for i in y: arr.append(int(i)) arr=ShellSort(arr) #print(arr) print("数列按序排列如下：") for i in arr: print(i,end=' ')

希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列，也可以动态的定义间隔序列。动态定义间隔序列的算法是《算法（第4版）》的合著者Robert Sedgewick提出的。　

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

简单选择排序同样对数据操作n-1轮，每轮找出一个最大（小）值。

操作指选择，即未排序数逐个比较交换，争夺最值位置，每轮将一个未排序位置上的数交换成已排序数，即每轮选一个最值。

每轮操作O(n)次，共O（n）轮，时间复杂度O(n^2)。

额外空间开销出在交换数据时那一个过渡空间，空间复杂度O(1)。

def SelectSort(lst): n=len(lst) if n

【本文地址】

史上最简单十大排序算法（Python实现）

史上最简单十大排序算法（Python实现）

今日新闻

推荐新闻