推荐做网站的公司,专业的移动网站建设公司,网站群如何做网站,泰州网站建设多少钱本篇将详细讲一下以下排序算法#xff1a;
直接插入排序希尔排序选择排序快速排序归并排序计数排序 排序的概念 排序#xff1a;所谓排序#xff0c;就是使一串记录#xff0c;按照其中的某个或某写关键字的大小#xff0c;按照递增或递减0排列起来的操作。 稳定性的概念…本篇将详细讲一下以下排序算法
直接插入排序希尔排序选择排序快速排序归并排序计数排序 排序的概念 排序所谓排序就是使一串记录按照其中的某个或某写关键字的大小按照递增或递减0排列起来的操作。 稳定性的概念 假定在待排序的记录序列中存在多个具有相同的关键字的记录若经过排序这些记录的相对次序保持不变。如一下例子
5 2 3 4 5 9 8 经过排序如果红5和蓝5的相对顺序不对这就叫稳定反之则不稳定。 直接插入排序 直接插入排序的思想将待排序的记录按其关键码值的大小逐个插入到一个已经排好序的序列中直到所有的序列为有序序列。
实际中我们玩扑克牌时就用到了这样的一个排序算法。 时间复杂度 直接插入排序时一个稳定的排序如果有相同的元素它们的相对位置不会发生变化。它时间复杂度最好的情况下是ON,当一个数插入到已经排好序的序列中只需要比较一次就好了。
最坏情况ON^2 在完全逆序的情况下要排升序。 希尔排序 希尔排序其实和插入排序很像只不过希尔排序的思想是先预排序最后插入排序。
预排序的意义在哪里
大的数更快到后面去小的数更快到前面去。gap越大跳的越快越不有序当gap 1 时就是插入排序。 时间复杂度 希尔排序的时间复杂度大约为ON^1.3 选择排序 选择排序的思想选择排序可以在一次查找中找到最大的数和最小的数然后把最大的数放到最后最小的数放到最前面。 时间复杂度 时间复杂度是ON^2
稳定性差 快速排序 快排思想说到排序或多或少都听过快速排序快速排序是Hoare于1962年提出的一种二叉树结构的交换方法其基本思想为任取待排序元素序列中的某个元素作为基准值按照该排序吗将待排序集合分割成2个子序列左序列小于keyi值右序列大于keyi值然后重复此方法最后拍完序。
快速排序一次可以确定一个值在正确的位置上。这个值就是key值 if (begin end){return;}int left begin, right end;int keyi left;while (left right){//先让右边先走while (leftright a[right]a[keyi]){--right;}while (left right a[left] a[keyi]){left;}Swap(a[left], a[right]);}Swap(a[keyi], a[left]);keyi left;//[begin,keyi-1] keyi [keyi1,end]QuickSort(a,begin,keyi-1);QuickSort(a,keyi1,end);
最常见的就是上面的递归代码这是Hoare的一种方式实现快排。
Hoare思想让基准值的右边先走直到找到比基准值小的数然后让左边走直到找到比基准值大的数然后交换最后leftright相等的时候将left位置的值与基准值交换。这样就实现了一次排序。 这里我们想一想快速排序为什么要让基准值的对面开始 挖坑法 用一个tmp记录第一个值的坑位让右边先走直到找到比坑位小的数然后让a[right]赋值给坑位然后把坑位给给right继续让左边先走直到找到比坑位大的数然后把值赋给坑位让坑位给给left一直循环。 前后指针法让prev指向key值cur指向key值之后的一个值当a[cur] a[key] 的时候就让prev和cur交换然后一直循环。 快排的非递归 快排的思想其实不难发现像一个栈后进先出因为快排每次可以确定一个基准值的位置所以第一次push进left和right让他们进行一次排序就接着push进right和keyi1再push进keyi-1和left注意顺序因为快排的中间也是一个后进先出的思想。 快排的缺点 快排其实是有缺点的因为快排的时间复杂度不一定是O(N*logN如果排升序给一个倒序的序列就有可能达到O(N^2)。所以有了这么一个缺点就可以做一个三数区中的优化其实Sort函数中也有这样的处理而且Sort中还优化了一次快排递归深度过深的时候会用堆排序在接近有序的时候会用插入排序而且Sort中只对了右边进行递归处理。如果有兴趣可以去了解一下Sort的源码里面有详细解释。 归并排序 归并排序它是建立在归并操作上的一种有效的排序算法该算法采用了分治的思想。将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段有序。若将两个有序表合并成一个有序表称为二路归并。 归并排序可以看出是一个后序的排序 先递归然后从前面开始排好序然后再memcpy到原数组。
归并排序其实用在解决磁盘外的外排序问题中如果有下面的场景归并排序就起到了很大的作用。 时间复杂度 归并排序也是一种经典的O(N*logN) 空间复杂度是O(N),这时因为开辟了一块tmp临时数组 计数排序 思想计数排序又称为鸽巢原理是对哈希直接定址法的变形应用。
步骤1.统计想相同元素出现的次数
2.根据统计的结果将序列回收到原来的序列中 计数排序的特性
计数排序在数据范围集中时效率很高但是使用范围及场景有限。时间复杂度O(MAX(N,范围))空间复杂度O(范围)
