面试必会：十大经典排序算法（python实现，附复杂度分析及稳定性） |
您所在的位置：网站首页 › python排序算法工具 › 面试必会：十大经典排序算法（python实现，附复杂度分析及稳定性） |
面试必会：十大经典排序算法（python实现，附复杂度分析及稳定性）
|
十大排序算法复杂度及稳定性属性表
n: 数据规模 k: “桶”的个数 In-place: 占用常数内存，不占用额外内存 Out-place: 占用额外内存 1、冒泡排序（Bubble Sort）冒泡排序算法的原理如下： a. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。 —— b. 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。 —— c. 针对所有的元素重复以上的步骤，除了最后一个。 —— d. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较 复杂度及稳定性： 时间复杂度：O(n^2) 空间复杂度：O(1) 稳定性：稳如老狗，内排序 python实现代码： def bubble_sort(nums): n = len(nums) # 进行多次循环 for c in range(n): for i in range(1, n - c): if nums[i - 1] > nums[i]: nums[i - 1], nums[i] = nums[i], nums[i - 1] return nums 2、选择排序（Select Sort）每一趟从待排序的数据元素中选出最小（最大）的元素，顺序放在待排序的数列最前，直到全部待排序的数据元素全部排完。 举例： [4, 2, 3] 找出最小的：2,与第一个元素交换 [2, 4, 3] 找出最小的：3，与第二个元素交换 [2, 3, 4] 复杂度及稳定性： 时间复杂度：O(n^2) 空间复杂度：O(1) 稳定性：链表稳定，数组不稳定，内排序 python实现代码： def select_sort(nums): n = len(nums) for i in range(n): for j in range(i, n): if nums[i] > nums[j]: nums[i], nums[j] = nums[j], nums[i] return nums 3、插入排序（Insertion Sort）核心思想：插入排序是前面已排序数组找到插入的位置 复杂度及稳定性： 时间复杂度：O(n^2) 空间复杂度：O(1) 稳定性：稳如老狗，内排序 python实现代码： def insertion_sort(nums): n = len(nums) for i in range(1, n): while i > 0 and nums[i - 1] > nums[i]: nums[i - 1], nums[i] = nums[i], nums[i - 1] i -= 1 return nums 4、希尔排序（Shell Sort）插入排序的进阶版。。。 算法描述： 我们来看下希尔排序的基本步骤，在此我们选择增量gap=length/2，缩小增量继续以gap = gap/2的方式，这种增量选择我们可以用一个序列来表示，{n/2,(n/2)/2…1}，称为增量序列。希尔排序的增量序列的选择与证明是个数学难题，我们选择的这个增量序列是比较常用的，也是希尔建议的增量，称为希尔增量，但其实这个增量序列不是最优的。 先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述： 步骤1：选择一个增量序列 t1，t2，…，tk，其中 ti > tj，tk=1； —— 步骤2：按增量序列个数k，对序列进行k 趟排序； —— 步骤3：每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。 复杂度及稳定性： 时间复杂度：O(nlogn) 空间复杂度：O(n) 稳定性：很稳定，外排序（需要额外空间） python实现代码： def shell_sort(nums): n = len(nums) gap = n // 2 while gap: for i in range(gap, n): while i - gap >= 0 and nums[i - gap] > nums[i]: nums[i - gap], nums[i] = nums[i], nums[i - gap] i -= gap gap //= 2 return nums 5、归并排序（Merge Sort）归并排序，采用是分治法，先将数组分成子序列，让子序列有序，再将子序列间有序，合并成有序数组。 算法描述： 1、把长度为n的输入序列分成长度 n/2的子序列； 2、对两个子序列采用归并排序； 3、合并所有子序列。 复杂度及稳定性： 时间复杂度：O(nlogn) 空间复杂度：O(1) 稳定性：不稳定，内排序 python实现代码： def merge_sort(nums): if len(nums) |
图片名词解释：【本文地址】
今日新闻 |
推荐新闻 |