C++ 经典排序算法

1.1.概述

冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。

它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。 这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端，故名。

1.2.算法原理： 冒泡排序算法的运作如下：（从后往前）

1.比较相邻的元素。如果第一个比第二个大，就交换他们两个。

2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。

3.针对所有的元素重复以上的步骤，除了最后一个。

4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

1.3.参考代码：

1.4.效率分析： 相对于简单选择排序，冒泡排序交换次数明显更多。它是通过不断地交换把最大的数冒出来。冒泡排序平均时间和最坏情况下（逆序）时间为o（n^2）。最佳情况下虽然不用交换，但比较的次数没有减少，时间复杂度仍为o（n^2）。此外冒泡排序是稳定的。

2.快速排序

2.1.概述：

快速排序是冒泡排序的一种改进，那么我们想了，既然冒泡排序第一轮排完了是最大值冒出来了，那么我们期望，能不能先随机选定一个值，然后依次与序列中的数进行对比，把小于该值的和大于该值的数据分割成独立的两个部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。这就是快速排序，我们把选定的那个值称为中心值，如果中心值为序列中的最大值，那么其实就相当于冒泡排序了。

2.2.参考代码：

2.3.效率分析

快速排序时间与划分是否对称有关。快速排序的平均时间复杂度为o（n*logn），至于为什么是o（n*logn）。且常数因子很小，所以就平均时间而言，快速排序是很好的内部排序方法。在待排序序列有序或逆序时不宜选用快速排序。 最佳情况下，每次划分都是对称的，由于中心值不再考虑，所以得到的两个子问题的大小不可能大于n/2，同时一趟快速排序时间为o（n），所以运行时间递归表达式： T（n）<=2T(n/2)+o(n)。 最坏情况下，每次划分都很不对称，T(n)=T(n-1)+o(n),可以用递归树来解，第i层的代价为n-i+1.总共有n层。把每一层代价加起来有n-1个n相加。所以这个递归式的解为T（n）=o（n^2）,此时就是冒泡排序。

3.直接选择排序

3.1.概述 直接选择排序也是一种简单的排序方法，它的基本思想是：第一次从A[0]~A[n-1]中选取最小值，与A[0]交换，第二次从A{1}~A[n-1]中选取最小值，与A[1]交换，....，第i次从A[i-1]~A[n-1]中选取最小值，与A[i-1]交换，.....，第n-1次从A[n-2]~A[n-1]中选取最小值，与A[n-2]交换,总共通过n-1次,得到一个按排序码从小到大排列的有序序列.

3.2.参考代码

3.3.效率分析 容易看出，要插入的记录个数为n-1，其中关键字的比较次数和记录移动次数是依赖于给出的待排序序列是否基本有序。在最佳情况下（待排序序列有序），比较次数和移动次数时间为o（1），所以时间复杂度为o（n）。在最坏情况下（待排序序列逆序）和平均时间均为o（n^2）.我们可以看出，直接插入排序适合记录数比较少、给定序列基本有序的情况。早了解和熟悉了排序过程后，我们发现，直接插入排序是一种稳定的原地排序算法。

4.折半插入排序

4.1.概述

折半插入排序是对直接插入排序的简单改进，对于直接插入排序而言，当第i-1趟需要将第i个元素插入前面的0~i-1个元素序列中时，总是需要从i-1个元素开始，逐个比较每个元素，直到找到它的位置。这显然没有利用前面0~i-1个元素已经有序这个特点，而折半插入排序则改进了这一点。

对于折半插入排序而言，当需要插入第i个元素时，它不会逐个进行比较每个元素，而是：

（1）计算0~i-1索引的中间点，也就是用i索引处的元素和(0+i-1)/2索引处的元素进行比较，如果i索引处的元素值大，就直接在(0+i-1)/2~i-1半个范围内进行搜索；反之在0~(0+i-1)/2半个范围内搜索，这就是所谓的折半；

（2）在半个范围内搜索时，按照（1）的方法不断地进行折半搜索，这样就可以将搜索范围缩小到1/2、1/4、1/8…，从而快速的确定插入位置；

4.2.参考代码:

4.3.效率分析 折半插入排序是对直接插入排序的一种改进，这种改进只考虑了关键字比较次数，并没有减少移位次数，所以平均时间和最坏情况下（待排序序列逆序）时间复杂度o（n^2）,如果记录数量很大的话，这两种情况下是优于直接插入排序。再来看一下最佳情况（待排序序列有序），此时关键字比较次数并不为o（1），时间复杂度为o（n*log2n）。（其中折半查找时间复杂度o(log2n)，这个在以后写查找的时候再分析，这里不做详细讲解。）。所以在记录数较小、待排序序列基本有序情况下直接插入排序优于折半插入排序。此外，折半插入排序是不稳定的原地排序，实现起来也较复杂。

看了这么多比较经典的排序算法，有没有觉得算法真的是一个神奇的“道具”。稍微一改优化就能大大提升效率。针对不同的情况选择最优的算法，提高效率也正是我们在项目中所追求的。如果小伙伴们有更多的有趣和经典的算法，也欢迎给老九君留言哦，我们都会不断的完善和补充！

老九学堂出品