数据结构-------排序算法详解（面试必备）

数据结构——排序

对于各个排序的C++或者C的编程实现网上很容易找到，也有不少的帖子对这这些排序有总结，看了很多好多没有将例子的过程写清楚，仅仅是写了排序思想或者排序过程很简陋，不详细。

1、插入排序–O(n^2)
插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
算法步骤：
将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）
原始：5 4 1 3 6 7 8 2
第一趟：4 5 1 3 6 7 8 2
第二趟：1 4 5 3 6 7 8 2

2、希尔排序–O(nlog(n))
算法先将要排序的一组数按某个增量d分成若干组，每组中记录的下标相差d.对每组中全部元素进行排序，然后再用一个较小的增量对它进行，在每组中再进行排序。当增量减到1时，整个要排序的数被分成一组，排序完成。
注意：增量的选择尤为重要，一种参考h=3*d+1进行迭代。

说明一下：每一趟分组后进行排序，按照小到大顺序，交换位置
第一趟中： 592 72交换位置，但是该数据在原始数据的位置仍然不变。
（1，592）—-（6，72）交换后（1，72）—（6，592）
第二趟中：（1，72）–（3，874）–（5，283）–（7，911）–（9，820）
交换排序后（1，72）–（3，283）–（5，820）–（7，874）–（9，911）

3、选择排序—-O(n^2)
算法步骤：
1）首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
2）再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
3）重复第二步，直到所有元素均排序完毕。
例子：5 8 3 6 4
第一趟：用除去第一个元素5以外的其余元素的最小值（为3）来与5比较，最小的交换（5>3）
3 8 5 6 4
第二趟：同理，用除去第二个元素8以外的其余元素的最小值（为4）来与8比较
3 4 5 6 8

4、冒泡排序—-O(n^2)
算法步骤：
1）比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2）对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
3）针对所有的元素重复以上的步骤，除了最后一个。
4）持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
5 3 8 4 7 假设从小到大，从后面第一个开始：
5 3 4 8 7
3 5 4 8 7 —-第一次排序结束，最小的在前面
3 5 4 7 8
3 4 5 7 8 —-第二次排序结束，第二最小排好
结束

5、快速排序–O(nlogn)
其实其思想是来自冒泡排序，冒泡排序是通过相邻元素的比较和交换把最小的冒泡到最顶端，而快速排序是比较和交换小数和大数，这样一来不仅把小数冒泡到上面同时也把大数沉到下面。

6、归并排序–O(nlogn）
归并排序是另一种不同的排序方法，因为归并排序使用了递归分治的思想，所以理解起来比较容易。其基本思想是，先递归划分子问题，然后合并结果。把待排序列看成由两个有序的子序列，然后合并两个子序列，然后把子序列看成由两个有序序列。倒着来看，其实就是先两两合并，然后四四合并。。。最终形成有序序列。空间复杂度为O(n)，时间复杂度为O(nlogn)。

7、堆排序
基本思想：
a.将无需序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;
b.将堆顶元素与末尾元素交换，将最大元素”沉”到数组末端;
c.重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。

总结：常用的算法一般为快速排序、归并排序、希尔排序等。特别的，如果一个序列基本成有序，插入排序是最快的。

申明：这个总结是看各位大佬的博客或者帖子总结的，如有侵犯请告知。