第二章 排序

2-2 冒泡排序

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

• 说明：
  总的比较次数：（n-1）+（n-2）+…+1≈n^2/2。
  时间复杂度为：O（n^2）.

2-3 选择排序

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

-说明：
选择排序使用了线性查找来寻找最小值，
总的比较次数为：
（n-1）+（n-2）+…+1≈n^2/2。
时间复杂度：O（n^2）。

2-4 插入排序

• 定义：
  插入排序是一种从序列左端开始依次对数据进行排序的算法。
  在排序过程中，需要将取出的数据与其左边的数字进行比较，交换数字，直到它比左边的数字大为止。

• 说明：
  对于插入排序来说， 输入数据按从大到小的顺序排列时就是最糟糕的情况。

时间复杂度：O（n^2）。

2-5 堆排序

从降序排列的堆中取出数据时会从最大的数据开始取，所以将取出的数据反序输出，排序就完成了。

• 说明：
  整体来看堆排序的时间复杂度为O（nlogn）。
  这样来看，堆排序的运行时间比之前讲到的冒泡排序、选择排序、插入排序的时间O（n2）都要短，但由于要使用堆这个相对复杂的数据结构，所以实现起来也较为困难。

总的来说是强行在数组中使用了堆结构。

2-6 归并排序

-定义：
归并排序算法会把序列分成长度相同的两个子序列，当无法继续往下分时（也就是每个子序列中只有一个数据时），就对子序列进行归并。

• 说明：
  归并排序中，分割序列所花费的时间不算在运行时间内（可以当作序列本来就是分割好的）。
  在合并两个已排好序的子序列时，只需重复比较首位数据的大小，然后移动较小的数据，因此只需花费和两个子序列的长度相应的运行时间。
  也就是说，完成一行归并所需的运行时间取决于这一行的数据量。

总的运行时间为O（nlogn）。

2-7 归并排序

快速排序算法首先会在序列中随机选择一个基准值（pivot），然后将除了基准值以外的数分为“比基准值小的数”和“比基准值大的数”这两个类别，再将其排列成以下形式。

[比基准值小的数] 基准值 [比基准值大的数]

• 说明：
  快速排序是一种“分治法”。它将原本的问题分成两个子问题（比基准值小的数和比基准值大的数），然后再分别解决这两个问题。

整体的时间复杂度为O（nlogn）。