摘要：前面介绍了七大算法的思想与实现步骤，下面来做一个归总。直到无序区中的数为零，结束排序。步骤以从小到大为例，排序数组大小为。比较完以后则排序结束。堆排序思想堆排序是采用树的形式的数据结构来进行排序的，其中每一个堆都是完全二叉树。
前面介绍了七大算法的思想与实现步骤，下面来做一个归总。
| 排序方法 | 平均复杂度 | 最坏复杂度 | 最好复杂度 | 辅助空间 | 稳定性 | |
|---|---|---|---|---|---|---|
| 直接选择排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 稳定 | |
| 冒泡排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 稳定 | |
| 直接插入排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 稳定 | |
| 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 稳定 | |
| 快速排序 | O(nlogn) | O(n^2) | O(nlogn) | O(1) | 不稳定 | |
| 希尔排序 | O(nlogn)~O(n^2) | O(n^1.3) | O(n^2) | O(logn)~O(n) | 不稳定 | |
| 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不稳定 |
直接选择排序，整体思想是将数据分成两个区域，有序区与无序区。排序的时候是每次从无序区中选择出最小的数，然后插入到有序区中的最末尾，从而形成更大的有序区。直到无序区中的数为零，结束排序。
步骤假设排序数组为a[0...n-1];
首先有序区中的个数为0，令i = 0。从无序区中选择最小的数，加入到有序区a[i]中。使得有序区为a[0..i],无序区为a[i...n-1]
完成后 i++ ,然后继续前面的步骤，直到 i = n-1 为止。使得全部数都在有序区中。
冒泡排序 思想冒泡排序主要是相邻的两个数两两进行比较，拿从小到大说明，进行冒泡排序后会将大的数沉到底部，将小得数浮到顶部。所以冒泡说法由此得名。
步骤以从小到大为例，排序数组大小为n。
第N = 0趟排序开始都从a[0]开始与其下面的相邻的数进行比较，如果大于相邻的数则交换他们的位置。
继续与下一个相邻的数进行比较，大于相邻的就交换，最后进行比较n-1次后，第N = 0趟排序结束，最大的数就在数组的a[n-1]处。
重复前面的步骤，直到 N = n-1,排序结束。
直接插入排序 思想直接插入排序的基本思想是:将需要排序的关键数与前面已经排好序的数据从后往前进行比较，使其插入到合适的位置。
步骤排序数组为a[0...n]
将a[0]作为起始数据，从a[1]开始作为关键字向前进行比较，若小于前面所遇到的比较数，则交换两个比较数的位置，否则直接进行下一个关键字的比较。
重复前面的步骤，直到将a[n]作为关键字进行比较。比较完以后则排序结束。
归并排序 思想归并排序是一个效率相对较高的排序算法，它采用的是分治的思想，将待排序的序列分成若干组，保证每组都有序，然后再进行合并排序，最终使整个序列有序。
步骤将待排序的序列采用分治思想将其划分成若干组，使其有序，其中可采用递归进行划分。
将有序的组分别进行归并操作，其中借助一个辅助数组，将左右划分的有序组从头开始进行比较，将较小的数加入到辅助数组中，且较小的所在有序数组向后自增，再与原来比较的数进行比较。
重复上面2的步骤，直到所有数据比较完毕，或者将还有剩余数未比较的有序数据直接按原有的顺序加入到辅助数组中,最后将已经排好序的辅助数组加入到原有数组的相应位置。
重复上面的2、3步骤，直到所有的左右划分归并完毕。
快速排序 思想快速排序的主要思想是：将一个待排序序列分成两个部分，以其中的一个数据作为分界线，其中一部分小于这个分界线的数据，另一部分大于这个分界线的数据。因为采用递归的思想，再对这两个序列进行快速排序，直到所以的数据都是有序的。
步骤假设待排序的数组为a[0...n-1]
一般都将第一个数a[i] (i = 0) 作为关键数，即快速排序的分界数。先从数组的后面开始即初值j = n-1，逐个向前进行遍历与选的的关键数进行比较(j--)，若大于等于关键数则继续遍历，否则将其与关键数所在的位置进行交换，并停止遍历且i++记录此时的i、j。
停止前面的遍历，再从数组的第i个位置开始向后进行遍历，逐个与关键数进行比较(i++)，若小于等于关键数则继续遍历，否则将其与关键数所在的位置进行交换，并停止遍历且j--记录此时的i、j。
重复上面的步骤，直到i==j就结束本次快速排序。
此时已经将其按关键数分成两个部分，再重复前面的步骤，对划分的部分进行快速排序，直到划分的组中的数据个数为1即此时所有数据有序。
希尔排序 思想希尔排序是记录增量来进行分组，再对分组内部进行直接插入排序，随着增量的不断减小，直到增量减小到1时，即每个分组中的数据量为1，此时排序结束。
步骤设待排序的数组为a[0...n-1]
一般开始取增量数d=n/2。从a[0]~a[d-1]将数组中数据之间的间隔为增量数d的倍数归为相同组。
依次对每组中的数据进行直接插入排序，使其有序。
再增量数d=d/2，重复上面的步骤，直到d=1为止。
堆排序 思想堆排序是采用树的形式的数据结构来进行排序的，其中每一个堆都是完全二叉树。堆排序分为大根堆与小根堆，大根堆（小根堆）表示在完全二叉树中，所用的非叶子节点都大于等于（小于等于）他们左右子节点（存在）。所以堆的顶点不是最大数就是最小数。这样的话我们就可以借助这种性质，每次都取出大根堆（小根堆）的顶点数，形成有序序列。
步骤首先生成小根堆或大根堆，这里以小根堆为例。我们可以将每一个非叶子节点都看做是一个最小的完全二叉树，将他们都生成小根堆，从最后一个非叶子节点开始，把其当做是根节点，逐步向前进行创建小根堆。
然后就是取出形成的小根堆得顶点值，将其与堆中第N(N=n)个节点互换位置，即a[N-1]。
此时小根堆被破坏，再重新生产小根堆N--，但此时要生成的数的范围为a[0...N-1]。
重复上面的步骤2、3，直到N=1，即a[0]，排序结束。
如有不足之处欢迎指出，全部代码已经放到github上，有需要的可以下载。
github地址：https://github.com/idisfkj/Ar...
关注文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/64847.html
摘要：编程思想第版这本书要常读，初学者可以快速概览，中等程序员可以深入看看，老鸟还可以用之回顾的体系。以下视频整理自慕课网工程师路径相关免费课程。 我自己总结的Java学习的系统知识点以及面试问题，目前已经开源，会一直完善下去，欢迎建议和指导欢迎Star： https://github.com/Snailclimb/Java-Guide 笔者建议初学者学习Java的方式：看书+视频+实践（初...
摘要：单一职责原则开闭原则里氏替换原则依赖倒置原则接口隔离原则迪米特法则组合聚合复用原则单一职责原则高内聚低耦合定义不要存在多于一个导致类变更的原因。建议接口一定要做到单一职责，类的设计尽量做到只有一个原因引起变化。使用继承时遵循里氏替换原则。 单一职责原则 开闭原则 里氏替换原则 依赖倒置原则 接口隔离原则 迪米特法则 组合/聚合复用原则 单一职责原则（Single Responsi...
摘要：在我们做系统设计时，经常会设计接口或抽象类，然后由子类来实现抽象方法，这里使用的其实就是里氏替换原则。 1.开闭原则（Open Close Principle/OCP） 定义：一个类、模块和函数应该对扩展开放，对修改关闭。 开放-封闭原则的意思就是说，你设计的时候，时刻要考虑，尽量让这个类是足够好，写好了就不要去修改了，如果新需求来，我们增加一些类就完事了，原来的代码能不动则不动。这个...
摘要：全栈数据之门前言自强不息，厚德载物，自由之光，你是我的眼基础，从零开始之门文件操作权限管理软件安装实战经验与，文本处理文本工具的使用家族的使用综合案例数据工程，必备分析文件探索内容探索交差并补其他常用的命令批量操作结语快捷键，之门提高效率光 showImg(https://segmentfault.com/img/bVK0aK?w=350&h=350); 全栈数据之门 前言 自强不息，...
阅读 422·2021-11-22 14:45
阅读 2905·2021-10-15 09:41
阅读 1282·2021-10-11 10:58
阅读 2142·2021-09-04 16:45
阅读 2414·2021-09-03 10:45
阅读 3083·2019-08-30 15:53
阅读 1111·2019-08-29 12:28
阅读 1993·2019-08-29 12:14
