排序

冒泡排序

冒泡排序就是重复“从序列右边开始比较相邻两个数字的大小，再根据结果交换两个数字的位置”这一操作的算法。

在冒泡排序中，第1轮需要比较n-1次，第2轮需要比较n-2次……第n-1轮需要比较1次。因此，总的比较次数为（n-1）+（n-2）+…+1≈n2/2。
这个比较次数恒定为该数值，和输入数据的排列顺序无关。不过，交换数字的次数和输入数据的排列顺序有关。
假设出现某种极端情况，如输入数据正好以从小到大的顺序排列，那么便不需要任何交换操作；
反过来，输入数据要是以从大到小的顺序排列，那么每次比较数字后便都要进行交换。
因此，冒泡排序的时间复杂度为O（n2）。

由于6＜7，所以交换这两个数字。

完成后，天平往左移动一个位置，比较两个数字的大小。此处4＜6，所以无须交换。

继续将天平往左移动一个位置并比较数字。重复同样的操作直到天平到达序列最左边为止。

简而言之就是通过两两比较将最小值挪到数组最左边。

选择排序

选择排序就是重复“从待排序的数据中寻找最小值，将其与序列最左边的数字进行交换”这一操作的算法。

选择排序使用了线性查找来寻找最小值，因此在第1轮中需要比较n-1个数字，第2轮需要比较n-2个数字……到第n-1轮的时候就只需比较1个数字了。
因此，总的比较次数与冒泡排序的相同，都是（n-1）+（n-2）+…+1≈n2/2次。
每轮中交换数字的次数最多为1次。如果输入数据就是按从小到大的顺序排列的，便不需要进行任何交换。
选择排序的时间复杂度也和冒泡排序的一样，都为O（n2）。


简而言之，数组分成两块，一块已排序一块未排序，不断遍历将未排序数组中的最小值放进已排序的数组中。

插入排序

插入排序是一种从序列左端开始依次对数据进行排序的算法。
在排序过程中，左侧的数据陆续归位，而右侧留下的就是还未被排序的数据。
插入排序的思路就是从右侧的未排序区域内取出一个数据，然后将它插入到已排序区域内合适的位置上。

在插入排序中，需要将取出的数据与其左边的数字进行比较。
就跟前面讲的步骤一样，如果左边的数字更小，就不需要继续比较，本轮操作到此结束，自然也不需要交换数字的位置。
然而，如果取出的数字比左边已归位的数字都要小，就必须不停地比较大小，交换数字，直到它到达整个序列的最左边为止。具体来说，就是第k轮需要比较k-1次。
因此，在最糟糕的情况下，第2轮需要操作1次，第3轮操作2次……第n轮操作n-1次，所以时间复杂度和冒泡排序的一样，都为O（n2）。
和前面讲的排序算法一样，输入数据按从大到小的顺序排列时就是最糟糕的情况。


首先，我们假设最左边的数字5已经完成排序，所以此时只有5是已归位的数字。
接下来，从待排数字（未排序区域）中取出最左边的数字3，将它与左边已归位的数字进行比较。
若左边的数字更大，就交换这两个数字。
重复该操作，直到左边已归位的数字比取出的数字更小，或者取出的数字已经被移到整个序列的最左边为止。

接下来是第3轮。和前面一样，取出未排序区域中最左边的数字4，将它与左边的数字5进行比较。
由于5＞4，所以交换这两个数字。交换后再把4和左边的3进行比较，发现3＜4，因为出现了比自己小的数字，所以操作结束。

遇到左边的数字都比自己小的情况时，不需要任何操作即可完成排序。重复上述操作，直到所有数字都归位。
简而言之，也是分排序和未排序部分，将未排序的第一个元素插入已排序的部分中。

堆排序

堆排序的特点是利用了数据结构中的堆（大顶堆）。
从降序排列的堆中取出数据时会从最大的数据开始取，所以将取出的数据反序输出，排序就完成了。



堆排序一开始需要将n个数据存进堆里，所需时间为O（nlogn）。
排序过程中，堆从空堆的状态开始，逐渐被数据填满。
由于堆的高度小于log2n，所以插入1个数据所需要的时间为O（logn）。
每轮取出最大的数据并重构堆所需要的时间为O（logn）。
由于总共有n轮，所以重构后排序的时间也是O（nlogn）。
因此，整体来看堆排序的时间复杂度为O（nlogn）。
这样来看，堆排序的运行时间比之前讲到的冒泡排序、选择排序、插入排序的时间O（n2）都要短，但由于要使用堆这个相对复杂的数据结构，所以实现起来也较为困难。

归并排序

序列分成长度相同的两个子序列，当无法继续往下分时（也就是每个子序列中只有一个数据时），就对子序列进行归并。
归并指的是把两个排好序的子序列合并成一个有序序列。该操作会一直重复执行，直到所有子序列都归并为一个整体为止。

把6和4合并，合并后的顺序为[4, 6]。

3和7同理。
合并这种含有多个数字的子序列时，要先比较首位数字，再移动较小的数字。由于4＞3，所以移动3。同样地，再次比较序列中剩下的首位数字。

递归执行上面的操作，直到所有的数字都合为一个整体为止。

归并排序中，分割序列所花费的时间不算在运行时间内（可以当作序列本来就是分割好的）。
在合并两个已排好序的子序列时，只需重复比较首位数据的大小，然后移动较小的数据，因此只需花费和两个子序列的长度相应的运行时间。
也就是说，完成一行归并所需的运行时间取决于这一行的数据量。
看一下上面的图便能得知，无论哪一行都是n个数据，所以每行的运行时间都为O（n）。
而将长度为n的序列对半分割直到只有一个数据为止时，可以分成log2n行，
因此，总共有log2n行。也就是说，总的运行时间为O（nlogn），这与前面讲到的堆排序相同。

快速排序

快速排序算法首先会在序列中随机选择一个基准值（pivot），然后将除了基准值以外的数分为“比基准值小的数”和“比基准值大的数”这两个类别，再将其排列成以下形式。
[比基准值小的数] 基准值 [比基准值大的数]
接着，对两个“[ ]”中的数据进行排序之后，整体的排序便完成了。对“[ ]”里面的数据进行排序时同样也会使用快速排序。

将其他数字和基准值进行比较。小于基准值的往左移，大于基准值的往右移。


把基准值4插入序列。这样，4左边就是比它小的数字，右边就是比它大的数字。
两边的排序操作也和前面的一样。

快速排序是一种“分治法”。
它将原本的问题分成两个子问题（比基准值小的数和比基准值大的数），然后再分别解决这两个问题。
子问题，也就是子序列完成排序后，再像一开始说明的那样，把他们合并成一个序列，那么对原始序列的排序也就完成了。
不过，解决子问题的时候会再次使用快速排序，甚至在这个快速排序里仍然要使用快速排序。
只有在子问题里只剩一个数字的时候，排序才算完成。
像这样，在算法内部继续使用该算法的现象被称为“递归”。
实际上前一节中讲到的归并排序也可看作是一种递归的分治法。
每行中每个数字都需要和基准值比较大小，因此每行所需的运行时间为O（n）。由此可知，整体的时间复杂度为O（nlogn）。如果运气不好，每次都选择最小值作为基准值，那么每次都需要把其他数据移到基准值的右边，递归执行n行，运行时间也就成了O（n2）。这就相当于每次都选出最小值并把它移到了最左边，这个操作也就和选择排序一样了。此外，如果数据中的每个数字被选为基准值的概率都相等，那么需要的平均运行时间为O（nlogn）。