排序算法复习（上篇）-爱代码爱编程

排序算法概述

排序就是将一组对象按照某种逻辑顺序重新排列的过程。比如，订单按照日期排序的——这种排序很可能使用了某种排序算法。在计算时代早期，大家普遍认为30% 的计算周期都用在了排序上。如果今天这个比例降低了，可能的原因之一是如今的排序算法更加高效，而并非排序的重要性降低了。现在计算机的广泛使用使得数据无处不在，而整理数据的第一步通常就是进行排序。几乎所有的计算机系统都实现了各种排序算法以供系统和用户使用。

即使你只是使用标准库中的排序函数，学习排序算法仍然有三大实际意义：

1. IT从业人员必备技能，也是互联网公司面试的必考点；

2. 类似的技术也能有效解决其他类型的问题；

3. 排序算法常常是我们解决其他问题的第一步。

排序在商业数据处理和现代科学计算中有着重要的地位，它能够应用于事物处理、组合优化、天体物理学、分子动力学、语言学、基因组学、天气预报和很多其他领域。其中一种排序算法（快速排序）甚至被誉为20 世纪科学和工程领域的十大算法之一。

数据结构和算法中，关于排序有十大算法，包括冒泡排序，简单选择排序，简单插入排序，归并排序，堆排序，快速排序、希尔排序、计数排序，基数排序，桶排序。

一般在面试中最常考的是 快速排序和归并排序，并且经常有面试官要求现场写出这两种排序的代码。对这两种排序的代码一定要信手拈来才行。对于其他排序可能会要求比较各自的优劣、各种算法的思想及其使用场景，还有要知道算法的时间和空间复杂度。

接下来将由易到难学习这十种算法：

1.冒泡排序

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

基本思路：

1、比较相邻的元素。如果第一个比第二个大(小)，就交换它们两个；

2、对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大(小)的数；

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

重复步骤1~2，直到排序完成。

*冒泡降序示例：*

原始数组

 

 

 

 

 

2.简单选择排序

选择排序的思想其实和冒泡排序有点类似，都是在一次排序后把最小的元素放到最前面。但是过程不同，冒泡排序是通过相邻的比较和交换。而选择排序是通过对整体的选择。

举个例子，对5,3,8,6,4这个无序序列进行简单选择排序，首先要选择5以外的最小数来和5交换，也就是选择3和5交换，一次排序后就变成了3,5,8,6,4.对剩下的序列继续进行选择和交换，最终就会得到一个有序序列。其实选择排序可以看成冒泡排序的优化，因为其目的相同，只是选择排序只有在确定了最小数的前提下才进行交换，大大减少了交换的次数。

具体步骤

首先，找到数组中最大（小）的那个元素；

其次，将它和数组的第一个元素交换位置（如果第一个元素就是最大（小）元素那么它就和自己交换）；

再次，在剩下的元素中找到最大（小）的元素，将它与数组的第二个元素交换位置。如此往复，直到将整个数组排序。

简单选择排序（降序）示例

原始数组：

3.简单插入排序

插入排序不是通过交换位置而是通过比较找到合适的位置插入元素来达到排序的目的的。相信大家都有过打扑克牌的经历，特别是牌数较大的。在分牌时可能要整理自己的牌，牌多的时候怎么整理呢？就是拿到一张牌，找到一个合适的位置插入。这个原理其实和插入排序是一样的。

举个例子，我们将要收到5,3,4,,8,6这几张牌，我们先收到5这张牌，毫无疑问，这张牌的位置是正确的，没必要整理。接着收到了牌3，然后3要插到5前面，把5后移一位，变成3,5。接着又收到了牌4，现在我们会怎么做？把4插入到5前面，把5后移一位。

*具体步骤：*

• 对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

• 为了给要插入的元素腾出空间，我们需要将插入位置之后的已排序元素在都向右移动一位。

• 插入排序所需的时间取决于输入中元素的初始顺序。例如，对一个很大且其中的元素已经有序（或接近有序）的数组进行排序将会比对随机顺序的数组或是逆序数组进行排序要快得多。

总的来说，插入排序对于部分有序的数组十分高效，也很适合小规模数组。

简单插入排序（降序）示例

原始数组：

4.希尔排序

一种基于插入排序的快速的排序算法(请大家先学习插入排序，了解基本的插入排序的思想。对于大规模乱序数组插入排序很慢，因为元素只能一点一点地从数组的一端移动到另一端。例如，如果主键最小的元素正好在数组的尽头，要将它挪到正确的位置就需要N-1 次移动。

希尔排序为了加快速度简单地改进了插入排序，也称为缩小增量排序，同时该算法是冲破O(n^2）的第一批算法之一。

希尔排序是把待排序数组按一定增量的分组，对每组使用直接插入排序算法排序；然后缩小增量继续分组排序，随着增量逐渐减少，每组包含的元素越来越多，当增量减至 1 时，整个数组恰被分成一组，排序便完成了。这个不断缩小的增量，就构成了一个增量序列。

希尔排序（降序）示例

*常用的增量序列有：*

希尔增量序列 ：{N/2, (N / 2)/2, ..., 1}，其中N为原始数组的长度，这是最常用的序列，但却不是最好的

Hibbard序列：{2^k-1, ..., 3,1}

Sedgewick序列：{... , 109 , 41 , 19 , 5，1} 表达式为

5.归并排序

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。

若将两个有序表合并成一个有序表，称为2-路归并，与之对应的还有多路归并。

对于给定的一组数据，利用递归与分治技术将数据序列划分成为越来越小的半子表，在对半子表排序后，再用递归方法将排好序的半子表合并成为越来越大的有序序列。

为了提升性能，有时我们在半子表的个数小于某个数（比如15）的情况下，对半子表的排序采用其他排序算法，比如插入排序。

归并排序（降序）示例

 

 

6.快速排序

快速排序被誉为20 世纪科学和工程领域的十大算法之一。快速排序（Quicksort）是对冒泡排序的一种改进，也是采用分治法的一个典型的应用。

首先任意选取一个数据（比如数组的第一个数）作为关键数据，我们称为基准数，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序，也称为分区（partition）操作。在实际实现时，一般会在原数组上直接操作。

通过一趟快速排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

为了提升性能，有时我们在分割后独立的两部分的个数小于某个数（比如15）的情况下，会采用其他排序算法，比如插入排序。

快速排序原理

 

 

快速排序中的基准数

基准的选取：最优的情况是基准值刚好取在无序区的中间，这样能够最大效率地让两边排序，同时最大地减少递归划分的次数，但是一般很难做到最优。基准的选取一般有三种方式，选取数组的第一个元素，选取数组的最后一个元素，以及选取第一个、最后一个以及中间的元素的中位数（如4 5 6 7, 第一个4, 最后一个7, 中间的为5, 这三个数的中位数为５, 所以选择5作为基准）。

Dual-Pivot快排：两个基准数的快速排序算法，其实就是用两个基准数, 把整个数组分成三份来进行快速排序，在这种新的算法下面，比经典快排从实验来看节省了10%的时间。