八大排序算法

⑴ 八大排序算法与复杂度

  在处理大批量数据时，有序化的数据可以在很大程度上提高算法效率。
直接插入排序  先总结一下数据结构的八大排序，分别是插入排序中的 直接插入排序 ， 希尔排序 ，交换排序中的 起泡排序 ， 快速排序 ，选择排序中的 直接选择排序 ， 堆排序 ，以及 归并排序 和 基数排序 。
  如何评价排序的优劣呢？除了正确，易读和容错（自动检错，报错并通过与用户对话来纠错）以外，性能是一个重要指标。

  算法性能是指运行一个算法所需要的时间长短和内存多少，他们分别称为 时间复杂性 和 空间复杂性 。

  1）有些计算机需要用户提供程序运行时间的上限。一旦达到这个上限，程序将被强制结束。
  2）一个正在开发的程序可能需要一个令人满意的实时响应。
  选择什么样的时间单位（程序步）来度量算法运行时间呢？对少量的输入，算法瞬间就运行完了。所以对算法性能的评价总是对大的输入量而言的。
  假设输入量是n，算法运行时间是n的函数T(n)，我们研究当很大时，T(n)是什么级别。这里就用到了 大O记法 ：如果存在正常数c和n ₀ ，使得当n≥n ₀ 时，T(n)≤ c*f(n)，则记为T(n)=O(f(n))。

  算法所需空间包括固定部分和变动部分。固定部分与输入量或规模无关，主要包括程序码空间和常量，变量和对象的定长所占的空间。变动部分与输出量有关，主要包括递归栈空间和中间处理所需空间。如果用P表示算法，S(P)表示空间需求，那么S(P)=c（固定部分）+S _p （变动部分）。算法的空间复杂性分析重点是变动部分S _p 。

  此外，如果一种排序实施前后，关键码相同的任意两个数据元素其前后次序没有发生变化，那么这个排序方法就被称作是 稳定的 ，否则就是 不稳定的 。

原理：从待排序集的第1个数据元素开始，依次选择数据元素，与有序子集的数据元素依次从后往前进行比较，选择插入位置。

稳定性： 稳定 。

原理：以增量为步长划分子序列，即同一子序列的数据元素，其下标步长等于增量。对每个子序列实施直接插入排序。不断缩小增量，当增量为1时，所有数组元素都在一个子序列中，成为有序集。
   通俗来讲，增量即为数组中元素下表的差值，假设步长为4，及a[0]，a[4]，a[8]…为一个子序列。实行直接插入排序后，将增量缩小为一半，直至增量缩小为1。

稳定性： 不稳定

原理：把数组分为左右两个半区，左半区为有序子集，右半区为无序子集。开始时，左半区为空。在无序子集中，从后往前，两两相邻元素比较，逆序则交换。最后交换的位置成为有序子集的上界。直到一趟起泡排序中没有发生交换，排序停止。

稳定性： 稳定 。

原理：取无序子集中的第一个数据元素作为基准，将无序子集分为左右两个半区，左半区不大于基准，右半区不小于基准；然后对左右半区重复上述操作，知道各半区元素个数为1.

稳定性： 不稳定 ，主要是划分算法Partition造成的。

原理：将数组分为左右两个半区，左半区为有序子集，右半区为无序子集。开始时，有序子集为空。在无序子集中，选出最小元素，与无序子集第一个元素交换，再将第一个元素并入有序子集中。重复上述操作。

稳定性： 稳定 。

原理：
1）将数组分为左右两个半区，左半区为有序子集，右半区为无序子集。开始时，有序子集为空。
2）将无序子集创建为大根堆。
3）将堆化为无序子集首位数据元素交换，将交换后的尾元素并入有序子集，然后把缩小的无序子集调整为大根堆。
4）重复步骤3）n-2次。

稳定性： 不稳定 。

原理：
1） 归并 （一般指二路归并）：将两个有序表合成一个新的有序表。包含关键码的原始数组ini分为左右两个有序分区（归并段）[s,m]和[m+1,e]，将他们按序归并，一个归并段存储到一个辅助数组（merge）中。
2） 迭代归并 ：包含关键码的原始数组ini按长度len划分为几个连续的归并段，每一个归并段都有序，用二路归并将相邻归并段合成一个长度为2len的归并段并存入辅助数组，这个过程称为 一趟归并 。重复上述步骤。
 ①剩下一个长度为len的归并段和一个长度不足len的归并段，继续调用二路归并。
 ②只剩下一个长度为len或不足len的归并段，直接移至辅助数组merge。

稳定性： 稳定 。

原理：采用“分配”和“收集”技术，从关键码的低位到高位进行比较。有十个队列作为分配用的”箱子“，编号0~9。遵照先进先出原则，从个位开始排序，到十位，百位，以此类推。

稳定性： 稳定 。

⑵ 八大算法

算法中比较常用的有八种算法，基本算法的题，都是依靠这些基础算法或者结合使用出题的，所以要学会基础算法，才有可能去更好的掌握算法题。

插入排序，又叫直接插入排序。实际中，我们玩扑克牌的时候，就用了插入排序的思想。

基本思想：在待排序的元素中，假设前n-1个元素已有序，现将第n个元素插入到前面已经排好的序列中，使得前n个元素有序。按照此法对所有元素进行插入，直到整个序列有序。但我们并不能确定待排元素中究竟哪一部分是有序的，所以我们一开始只能认为第一个元素是有序的，依次将其后面的元素插入到这个有序序列中来，直到整个序列有序为止。

希尔排序，又称缩小增量法。其基本思想是：

 1>先选定一个小于N的整数gap作为第一增量，然后将所有距离为gap的元素分在同一组，并对每一组的元素进行直接插入排序。然后再取一个比第一增量小的整数作为第二增量，重复上述操作…

    2>当增量的大小减到1时，就相当于整个序列被分到一组，进行一次直接插入排序，排序完成。

选择排序，即每次从待排序列中选出一个最小值，然后放在序列的起始位置，直到全部待排数据排完即可。

如何进行堆排序呢？

步骤如下：

 1、将堆顶数据与堆的最后一个数据交换，然后对根位置进行一次堆的向下调整，但是调整时被交换到最后的那个最大的数不参与向下调整。

 2、完成步骤1后，这棵树除最后一个数之外，其余数又成一个大堆，然后又将堆顶数据与堆的最后一个数据交换，这样一来，第二大的数就被放到了倒数第二个位置上，然后该数又不参与堆的向下调整…反复执行下去，直到堆中只有一个数据时便结束。此时该序列就是一个升序。

冒泡排序，该排序的命名非常形象，即一个个将气泡冒出。冒泡排序一趟冒出一个最大（或最小）值。

快速排序是公认的排序之王，快速排序是Hoare于1962年提出的一种二叉树结构的交换排序算法，其基本思想为：

 任取待排序元素序列中的某元素作为基准值，按照该基准值将待排序列分为两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后左右序列重复该过程，直到所有元素都排列在相应位置上为止。

归并排序是采用分治法的一个非常典型的应用。其基本思想是：将已有序的子序合并，从而得到完全有序的序列，即先使每个子序有序，再使子序列段间有序。

计数排序，又叫非比较排序。顾名思义，该算法不是通过比较数据的大小来进行排序的，而是通过统计数组中相同元素出现的次数，然后通过统计的结果将序列回收到原来的序列中。

⑶ 算法八大排序是否都要会默写

算法八大排序都要会默写。根据查询相关公开信息得知，八大算法指插入排序、选择排序、冒泡排序、希尔排序、归并排序、快速排序、堆排序、计数排序。是编程必会的知识，要熟练掌握并默写。

⑷ 几种排序算法的比较

一、八大排序算法的总体比较

4.3、堆的插入：

每次插入都是将新数据放在数组最后。可以发现从这个新数据的父结点到根结点必然为一个有序的数列，然后将这个新数据插入到这个有序数据中

（1）用大根堆排序的基本思想

先将初始数组建成一个大根堆，此对为初始的无序区；

再将最大的元素和无序区的最后一个记录交换，由此得到新的无序区和有序区，且满足<=的值；

由于交换后新的根可能违反堆性质，故将当前无序区调整为堆。然后再次将其中最大的元素和该区间的最后一个记录交换，由此得到新的无序区和有序区，且仍满足关系的值<=的值，同样要将其调整为堆；

..........

直到无序区只有一个元素为止；

4.4：应用

寻找M个数中的前K个最小的数并保持有序；

时间复杂度：O(K)[创建K个元素最大堆的时间复杂度] +（M-K）*log(K)[对剩余M-K个数据进行比较并每次对最大堆进行从新最大堆化]

5.希尔排序

（1）基本思想

先将整个待排序元素序列分割成若干子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序（因为直接插入排序在元素基本有序的情况下，效率很高）；

（2）适用场景

比较在希尔排序中是最主要的操作，而不是交换。用已知最好的步长序列的希尔排序比直接插入排序要快，甚至在小数组中比快速排序和堆排序还快，但在涉及大量数据时希尔排序还是不如快排；

6.归并排序

（1）基本思想

首先将初始序列的n个记录看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n/2个长度为2的有序子序列，在此基础上，再对长度为2的有序子序列进行两两归并，得到若干个长度为4的有序子序列，以此类推，直到得到一个长度为n的有序序列为止；

（2）适用场景

若n较大，并且要求排序稳定，则可以选择归并排序；

7.简单选择排序

（1）基本思想

第一趟：从第一个记录开始，将后面n-1个记录进行比较，找到其中最小的记录和第一个记录进行交换；

第二趟：从第二个记录开始，将后面n-2个记录进行比较，找到其中最小的记录和第2个记录进行交换；

...........

第i趟：从第i个记录开始，将后面n-i个记录进行比较，找到其中最小的记录和第i个记录进行交换；

以此类推，经过n-1趟比较，将n-1个记录排到位，剩下一个最大记录直接排在最后；

⑸ 八大经典排序算法原理及实现

该系列文章主要是记录下自己暑假这段时间的学习笔记，暑期也在实习，抽空学了很多，每个方面的知识我都会另起一篇博客去记录，每篇头部主要是另起博客的链接。

冒泡排序算法应该是大家第一个接触的算法，其原理都应该懂，但我还是想以自己的语言来叙述下其步奏：

按照计算时间复杂度的规则，去掉常数、去掉最高项系数，其复杂度为O(N^2)
冒泡排序及其复杂度分析

空间复杂度就是在交换元素时那个临时变量所占的内存

给定一个整数序列{6,1,2,3,4},每完成一次外层循环的结果为：

我们发现第一次外层循环之后就排序成功了，但是还是会继续循环下去，造成了不必要的时间复杂度，怎么优化？

冒泡排序都是相邻元素的比较，当相邻元素相等时并不会交换，因此冒泡排序算法是稳定性算法

插入排序是对冒泡排序的一种改进

插入排序的思想是数组是部分有序的，再将无序的部分插入有序的部分中去,如图：
（图片来自 这里 ）

空间复杂度就是在交换元素时那个临时变量所占的内存

插入排序的优化，有两种方案：

文章后面会给出这两种排序算法

由于插入排序也是相邻元素的比较，遇到相等的相邻元素时不会发生交换，也不会造成相等元素之间的相对位置发生变化

其原理是从未排序的元素中选出最小值(最大值)放在已排序元素的后面

空间复杂度就是在交换元素时那个临时变量所占的内存

选择排序是不稳定的，比如 3 6 3 2 4，第一次外层循环中就会交换第一个元素3和第四个元素2，那么就会导致原序列的两个3的相对位置发生变化

希尔排序算是改良版的插入排序算法，所以也称为希尔插入排序算法

其原理是将序列分割成若干子序列（由相隔某个 增量 的元素组成的），分别进行直接插入排序；接着依次缩小增量继续进行排序，待整个序列基本有序时，再对全体元素进行插入排序，我们知道当序列基本有序时使用直接插入排序的效率很高。
上述描述只是其原理，真正的实现可以按下述步奏来：

希尔排序的效率取决于 增量值gap 的选取，这涉及到数学上尚未解决的难题，但是某些序列中复杂度可以为O(N 1.3)，当然最好肯定是O(N)，最坏是O(N 2)

空间复杂度就是在交换元素时那个临时变量所占的内存

希尔排序并不只是相邻元素的比较，有许多跳跃式的比较，难免会出现相同元素之间的相对位置发生变化，所以希尔排序是不稳定的

理解堆排序，就必须得先知道什么是堆？

二叉树的特点：

当父节点的值总是大于子结点时为 最大堆 ；反之为 最小堆 ，下图就为一个二叉堆

一般用数组来表示堆，下标为 i 的结点的父结点下标为(i-1)/2；其左右子结点分别为 (2 i + 1)、(2 i + 2)

怎么将给定的数组序列按照堆的性质，调整为堆？

这里以建立最小堆为示例，

很明显对于其叶子结点来说，已经是一个合法的子堆，所以做堆调整时，子节点没有必要进行，这里只需从结点为A[4] = 50的结点开始做堆调整，即从（n/2 - 1）位置处向上开始做堆调整：

由于每次重新恢复堆的时间复杂度为O(logN)，共N - 1次重新恢复堆操作，再加上前面建立堆时N / 2次向下调整，每次调整时间复杂度也为O(logN)，二次操作时间相加还是O(N logN)。故堆排序的时间复杂度为O(N * logN)。

空间复杂度就是在交换元素时那个临时变量所占的内存

由于堆排序也是跨越式的交换数据，会导致相同元素之间的相对位置发生变化，则算法不稳定。比如 5 5 5 ,堆化数组后将堆顶元素5与堆尾元素5交换，使得第一个5和第三个5的相对位置发生变化

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

快速排序在应该是大家经常看到、听到的算法，但是真正默写出来是有难度的。希望大家看了下面 挖坑填数 方法后，能快速写出、快速排序。

其原理就这么几句话，但是现实起来并不是这么简单，我们采取流行的一种方式 挖坑填数分治法

对于序列： 72 6 57 88 60 42 83 73 48 85

数组变为： 48 6 57 88 60 42 83 73 88 85
再重复上面的步骤，先从后向前找，再从前向后找：

数组变为： 48 6 57 42 60 72 83 73 88 85
可以看出a[5]前面的数字都小于它，a[5]后面的数字都大于它。因此再对a[0…4]和a[6…9]这二个子区间重复上述步骤就可以了

空间复杂度，主要是递归造成的栈空间的使用:

快速排序的优化主要在于基准数的选取

快速排序也是跨越式比较及交换数据，易导致相同元素之间的相对位置发生变化，所以快速排序不稳定

前面也说了二分查找排序是改进的插入排序，不同之处在于，在有序区间查找新元素插入位置时，为了减少比较次数提高效率，采用二分查找算法进行插入位置的确定
具体步骤，设数组为a[0…n]：

二分查找插入位置，因为不是查找相等值，而是基于比较查插入合适的位置，所以必须查到最后一个元素才知道插入位置。
二分查找最坏时间复杂度：当2^X>=n时，查询结束，所以查询的次数就为x，而x等于log2n（以2为底，n的对数）。即O(log2n)
所以，二分查找排序比较次数为：x=log2n
二分查找插入排序耗时的操作有：比较 + 后移赋值。时间复杂度如下：

二分查找排序在交换数据时时进行移动，当遇到有相等值插入时也只会插入其后面，不会影响其相等元素之间的相对位置，所以是稳定的

白话经典算法排序
冒泡排序选择排序
快速排序复杂度分析
优化的插入排序

⑹ java的都学习哪些内容

学习java是个不错的选择，java在it行业需求的人才每年占上百万个，并且平均每个月薪资也是在1.8W左右。

如果想达到工作标准可以参考下面的内容：

1.Java SE部分 初级语法，面向对象，异常，IO流，多线程，Java Swing，JDBC，泛型，注解，反射等。

2.数据库部分，基础的sql语句，sql语句调优，索引，数据库引擎，存储过程，触发器，事务等。

3. 前端部分， HTML5 CSS3 JS， HTML DOM Jquery BootStrap等。

4. Java EE部分，Tomcat和Nginx服务器搭建，配置文件，Servlet，JSP，Filter，Listener，http协议，MVC等。

5. 框架部分，每个框架都可以分开学，在去学如何使用SSM 或者SSH框架，如何搭建，如何整合。开发中为什么会用框架，Rest是啥？Spring为啥经久不衰，底层如何实现等。

6.23种设计模式，掌握常用的，比如单例模式的多种实现，责任链模式，工厂模式，装饰器模式等，了解常用场景。

7. 基础算法和数据结构，八大排序算法，查找算法。

8. 熟练使用maven等构建工具，git等版本控制工具，熟悉常用linux命令，log4j，bug，junit单元测试，日志打印工具，Redis等NoSql。

互联网行业目前还是最热门的行业之一，学习IT技能之后足够优秀是有机会进入腾讯、阿里、网易等互联网大厂高薪就业的，发展前景非常好，普通人也可以学习。

想要系统学习，你可以考察对比一下开设有相关专业的热门学校，好的学校拥有根据当下企业需求自主研发课程的能力，能够在校期间取得大专或本科学历，中博软件学院、南京课工场、南京北大青鸟等开设相关专业的学校都是不错的，建议实地考察对比一下。

祝你学有所成，望采纳。

⑺ 数据结构-八大排序算法的时间复杂度 稳定性

1：直接插入排序：
最好：待排序已经有序， 从前往后走都不用往里面 插入。 时间复杂度为o(n)
最坏：待排序列是逆序，每一次都要移位插入。 时间复杂度o(n^2)
是稳定排序

2：希尔排序：
最好：缩小增量的插入排序，待排序已经有序。时间复杂度o(n）
一般：平均时间复杂度o(n ^{1.3)，最差也是时间复杂度o(n} 1.3)
不稳定排序

3：冒泡排序：
最好：待排序已经有序。时间复杂度o(n）
最坏：待排序是逆序。时间复杂度o(n^2）
稳定排序

4：快速排序：
最好：待排序无序。时间复杂度o(nlogn)
最坏: 待排序已经有序，基准定义在开始。 时间复杂度为o(n^2)
不稳定排序

5：直接选择排序：
无论好坏:o(n^2)
稳定排序

6：堆排序：
无论好坏：时间复杂度o(nlogn)
不稳定排序

7：归并排序：

稳定排序

8：基数排序：
无论好坏:o(d(n+r)) ，r为基数，d为位数.
稳定排序

⑻ iOS算法系列（二）- 八大排序算法

排序算法也算是老生常谈了，如果你大学专业是计算机或软件，甚至你参加过国二国三都会学到排序算法，如果我没猜错的话你接触的第一个算法是冒泡。
排序算法老生常谈，但确实多少大厂面试题中的必考题。
废话不多说，开始正题
常见的八种排序算法他们的关系如下：

递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：
插入排序在对几乎已经排好序的数据操作时， 效率高， 即可以达到线性排序的效率
但插入排序一般来说是低效的， 因为插入排序每次只能将数据移动一位

希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。

说基数排序之前，我们简单介绍桶排序：
算法思想：是将阵列分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递回方式继续使 用桶排序进行排序）。桶排序是鸽巢排序的一种归纳结果。当要被排序的阵列内的数值是均匀分配的时候，桶排序使用线性时间（Θ（n））。但桶排序并不是 比较排序，他不受到 O(n log n) 下限的影响。
简单来说，就是把数据分组，放在一个个的桶中，然后对每个桶里面的在进行排序。
例如要对大小为[1..1000]范围内的n个整数A[1..n]排序

各种排序的稳定性，时间复杂度、空间复杂度、稳定性总结如下图：