健康资讯 关于【排序的十种算法】，今天涌涌小编给您分享一下，如果对您有所帮助别忘了关注本站哦。
- 内容导航：
- 1、排序的十种算法：十大排序算法介绍及python实现
- 2、排序的十种算法，十大经典排序算法
1、排序的十种算法：十大排序算法介绍及python实现
排序算法
排序算法简单地分为两类：比较排序和非比较排序，其中比较排序是通过比较元素的相对大小来实现排序，其复杂度的上限为O(nlogn)，所以也称其为非线性时间排序；非比较排序不是通过比较元素相对大小来实现，通常能够以O(n)的复杂度来实现，所以也称其为线性时间排序，下面给出了十种排序算法的复杂度（时间复杂度和空间复杂度）和稳定性
其中，n 表示需要排序的元素数量，k 表示桶的数量
LB三人组
冒泡排序
冒泡排序的思想就是每次循环过程中，大的元素下降，小的元素上升，从而进行排序，具体过程如下：
代码如下：
def bubble_sort(a): n = len(a) flag = False #设置标志位，避免无效排序 for i in range(n-1, 0, -1): for j in range(i): if a[j] > a[j + 1]: a[j], a[j + 1] = a[j + 1], a[j] flag = True if not flag: break return aif __name__ == "__main__": a = [90, 5, 83, 42, 12, 15] print(bubble_sort(a))
选择排序
选择排序的思想就是每次循环的过程中找到最小的值放在第一位，依次循环找到其他较小的值放在接下来的位置，通过查找进行排序，其过程如下：
代码如下：
def select_sort(a): n = len(a) for i in range(n - 1): min_index = i for j in range(i+1, n): if a[j] < a[min_index]: min_index = j a[i], a[min_index] = a[min_index], a[i] return aif __name__ == "__main__": a = [90, 5, 83, 42, 12, 15] print(select_sort(a))
插入排序
插入排序的思想就是和之前的元素进行比较，大的元素放在后面，小的元素放在前面，具体过程如下：
代码如下：
def insert_sort(a): n = len(a) for i in range(1, n): cur_val = a[i] pos = i while pos > 0 and a[pos - 1] > cur_val: a[pos] = a[pos - 1] pos -= 1 a[pos] = cur_val return aif __name__ == "__main__": a = [90, 5, 83, 42, 12, 15] print(insert_sort(a))
希尔排序
希尔排序是插入排序的另一种变化，通过有间隔的插入排序并逐步减小间隔实现最终的排序，其过程如下：
代码如下：
def shell_sort(a): n = len(a) gap = n // 2 while gap > 0: for i in range(gap): gap_insert(a, i, gap) #有间隔的插入排序 gap //= 2 return adef gap_insert(a, sta, gap): for i in range(sta + gap, len(a), gap): cur_val = a[i] pos = i while pos > sta and a[pos - gap] > cur_val: a[pos] = a[pos - gap] pos -= gap a[pos] = cur_val return aif __name__ == "__main__": a = [90, 5, 83, 42, 12, 15] print(shell_sort(a))
NB三人组
归并排序
归并排序是基于分治的思想，将需要排序的数据分为两个子序列，对子序列进行排序，然后将排好序的子序列进行合并实现最终的排序，过程如下：
代码如下：
def merge_sort(a): if len(a) <= 1: return a n = len(a) // 2 left = merge_sort(a[:n]) #子序列归并排序 right = merge_sort(a[n:]) return merge(left, right) #合并排好序的子序列def merge(left, right): l, r = 0, 0 res = [] while l < len(left) and r < len(right): if left[l] < right[r]: res.append(left[l]) l += 1 else: res.append(right[r]) r += 1 res.extend(left[l:]) res.extend(right[r:]) return resif __name__ == "__main__": a = [90, 5, 83, 42, 12, 15] print(merge_sort(a))
堆排序
堆排序思想是建立一个大根堆，将堆顶位置与最后一个进行交换，再建立大根堆，重复上述操作实现排序，过程如下：
代码如下：
def heap_sort(a): n = len(a) for i in range(n // 2 - 1, -1, -1): siftdown(a, i, n - 1) #建立大根堆 for j in range(n - 1, 0, -1): a[0], a[j] = a[j], a[0] #交换后，继续建立大根堆 siftdown(a, 0, j-1) return adef siftdown(a, sta, end): root = sta #根节点 while True: child = 2 * root + 1 #左孩子节点 if child > end: break if child + 1 <= end and a[child] < a[child + 1]: #存在右孩子节点 child += 1 if a[root] < a[child]: #维护大根堆 a[root], a[child] = a[child], a[root] root = child else: break return aif __name__ == "__main__": a = [90, 5, 83, 42, 12, 15] print(heap_sort(a))
快速排序
快速排序的思想是选择一个基准线，将比基准线小的放在一边，比基准线大的放在另一边，通过对两部分进行排序实现最终的排序，过程如下：
代码如下：
def quick_sort(a): if len(a) <= 1: return a left = [] right = [] base = a.pop() for x in a: if x < base: left.append(x) else: right.append(x) return quick_sort(left) + [base] + quick_sort(right)if __name__ == "__main__": a = [90, 5, 83, 42, 12, 15] print(quick_sort(a))
线性时间排序
计数排序
计数排序的思想是建立计数器，统计每个数字出现的次数，再将统计的结果输出实现最终的排序，过程如下：
代码如下：
def count_sort(a): n = len(a) max_val = max(a) count = [0] * (max_val + 1) for i in range(n): count[a[i]] += 1 res = [] for i in range(max_val + 1): for j in range(count[i]): res.append(i) return resif __name__ == "__main__": a = [90, 5, 83, 42, 12, 15] print(count_sort(a))
桶排序
桶排序的思想就是将对应范围内的元素放进桶中，对桶中的元素进行排序，然后再将元素按照顺序取出，完成最终的排序，过程如下：
代码如下：
2、排序的十种算法，十大经典排序算法
上文中提到一个题目，必须使用比较类排序。那么比较类和非比较类的区别在哪里呢
比较类排序：通过比较元素来决定元素间的相对次序，其时间复杂度不能突破O(nlogn)。
非比价类排序：不通过比较，可以用线性时间运行，如桶排序，计数排序，基数排序
各排序算法的类型
- 冒泡排序
依次比较相邻元素，让元素像冒泡一样向数组头部移动
算法描述：
1比较相邻的元素，如果第一个比第二个大，则交换。
2对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数
3重复步骤2，直到某一趟中没有任何交换，则排序结束
- 选择排序
依次选出第一大的，第二大的，直到排序完成
算法描述：
- 遍历数组，找到最小的元素放到第一位
- 遍历数组，找到第二小的放到第二位
- 重复以上步骤，直到排序完成
- 插入排序
将未确定数组中拿出一个数往已确定数组中插入
算法描述
- 第一个元素认为是已经配排序
- 去除下一个元素，往前面扫描，插入合适的位置，目前已确认两个元素
- 重复以上步骤直到排序完成
- 希尔排序，又称缩小增量排序
先将整个待排序列按增量分隔成若干子序列进行插入排序，然后将增量缩小，再进行一轮排序直到增量为1
- 归并排序
该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列
算法描述
- 把长度为n的输入序列分为两个长度为n/2的序列
- 把两个子序列分别采用归并排序
- 快速排序
同样使用了分治法，从数列中挑出一个元素作为基准，将比基准小的摆在基准前面，将比基准大的摆在基准后面，形成两个子序列。递归的把子数列进行快速排序
归并和快排的区别是，归并是合并起来，快速排序是逐渐分开
算法描述
1数列中挑出一个元素，称为基准
2重新排序数列，将元素中比基准小的放在基准前面，将所有元素比基摆在基准后面
3递归子数列
- 堆排序
将数组构建成大顶堆，将大顶堆的顶部输出，重新恢复大顶堆，重复以上知道排序完成
构建大顶堆的时间复杂度为O(n)
- 计数排序
计数排序要求输入的数据必须是有确定范围的整数，统计每个数出现的次数后依次输出数组中，要求数据较为均匀
- 桶排序
利用了函数的映射关系，将数据分到有限的桶内，每个桶内在排序。要求数据较为均匀
- 基数排序
基数排序是按照低位先排序后，再按高位排序，要求数据位数差异不大
参考自《十大经典排序算法（动图演示）》
十大排序顺口溜：快速冒泡，希尔插入，归并，选择堆，桶和计数，对比基数
故事解释：扫地比赛，为了报名快速冒泡，希尔（人名）插入队伍，归并地上的垃圾，选择别人的垃圾堆，放进桶里进行计数，对比重量基数后获胜。
本文关键词：排序的几种算法实例，排序算法怎么写，排序的十种算法有哪些，排序算法 简书，排序算法总结。这就是关于《排序的十种算法，十大排序算法介绍及python实现》的所有内容，希望对您能有所帮助！
