前段时间复习了一遍大学的数据结构课程（中国大学MOOC），老师循序渐进地讲解了数据结构、排序算法的原理、思路、以及解决的办法，觉得讲得很好。而且排序算法是其中基础中的基础，平时面试的时候还可能经常问到，所以有必要总结一下。

比较好的文章

十大经典排序算法（动图演示）

冒泡排序

冒泡排序是基础中的基础，其思路是，一次比较相邻的两个元素，如果其大小相反，则交换其位置，直到整个数组都是正确的顺序。按理来说要让整个数组都是顺序排序的，就需要遍历n-1遍。

一个优化的点是，可以在交换函数里加上一个判断。如果遍历一遍之后没有数据要交换，则理解为所有元素都是有序的，则可以直接退出排序

代码

1
2
3
4
5
6
7
8
9
10

Array.prototype.bubbleSort = function() {
    const len = this.length;
    for(let i = 0; i < len - 1; i++) {
        for(let j = i+1; j < len; j++) {
            if (this[i] > this[j]) {
				this.swap(i, j)
			}
        }
    }
}

插入排序

打扑克牌的时候，起牌的过程就是一次插入排序。牌库是未排序的数组，每次拿出牌库中的第一张牌，然后把该牌放到手上正确的位置（手上的牌一直都是有序的），直到牌库被抽空；

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13

Array.prototype.insertSort = function() {
    const len = this.length;
    for(let i = 1; i < len; i++) {
        for (let j = i; j > 0; j--) {
           if (this[j] < this[j-1]) {
				this.swap(j, j-1);
			} else {
				// 如果已经找到位置，则直接退出循环
				break;
			}
        }
    }
}

选择排序

选择排序也可以从扑克牌中找到。当我们想整理扑克牌的时候，一般是会把扑克牌铺开，正面朝上，然后在乱序的牌中找到最小的一张，拿在手上。直到乱序的牌被选完。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12

Array.prototype.selectSort = function(reverse = false) {
    const len = this.length;
    for (let i = 0; i < len; i++) {
        let minIndex = i;
		for (let j = i; j < len; j++) {
			if (this[j] < this[minIndex]) {
				minIndex = j;
			}
		}
		this.swap(i, minIndex);
    }
}

堆排序

堆排序是对选择排序的一个优化。选择排序在乱序的数组中选择一个最小的元素，必须要遍历一遍乱序的数组，时间复杂度则必定是O(n), 而“在乱序数组中选取最小元素”这个思想，用最小堆来实现，则时间复杂度则可以降低到O(nlogn)。

快速排序

在说快速排序之前，需要了解一下逆序对的概念

逆序对

假设i < j，则数组arr[i] > arr\[j] 则 (i,j)称之为逆序对；
冒泡排序、等排序虽然比对了很多次，但是真正交换的次数只是无序数组中逆序对的数量。

• 定理：任意N个不同元素组成的序列平均具有N(N-1)/4个逆序对。
• 定理：任何仅以交换相邻元素来排序的算法，其平均时间复杂度为Ω(N²)。

这意味着，要提高算法效率，我们必须

• 每次消去不止一个逆序对！
• 每次交换相隔较远的2个元素

所以，快速排序的思想是，减少比对的次数，找到逆序队之后再交换。

思想

1. 先选择一个中间数，一般找乱序数组的第一位。
2. 设两个指针，分别在剩下乱序数组的最左边和最右边。
3. 俩指针分别向中间移动（左指针向右移动，右指针向左移动），如果左指针指向值大于中间数，则停止遍历。如果右指针指向的值小于中间数，也停止遍历。如果左指针与右指针都停止遍历，则交换。直到左指针在右指针右边（即两指针相遇）
4. 将中间数与左指针交换。
5. 将数组从中间数作为分隔，分为左右两边。分别递归进行快速排序

希尔排序

比较另类

思想

1. 定义增量序列，如5、3、2、1
2. 先对乱序数组按序列5划分为N个数组a1、a2、a3…..
3. 分别对a1[0]、a2[0]、a3[0]…排序，然后依次对a1[1]、a2[1]、a2[3]….依次类推。
4. 再用增量序列3对上一步排序的数组进行划分，重复第二步骤

最终得到一个有序的数组

说实话并不太理解其原理。反正只要增量序列选取得正确，希尔排序算法确实是可以生效的。目前公认的比较合适的增量序列是：Hibbard、Sedgewick。是什么可能并不重要了。大概记录一下思路就好

归并排序

思路是这样的：

假设有两个有序数组a1、a2。现在要把这俩合并成大数组，只需要设置两个指针p1、p2，分别指向a1、a2两个数组的头部。比较p1、p2。取较小的指针，并且把较小指针向后挪一位。直到两个指针都完成遍历。就能把两个有序数组合并成为一个有序数组了。

而归并排序的意思就是。把一个乱序的数组平均分成两个数组、对分出来的两个数组递归归并排序。直到二分的数组只有一个值时，这个数组就是有序的。最终可以得到一个有序的数组

归并排序不管数据顺序是怎样的，都会把其递归，等分，合并。所以其时间复杂度和空间复杂度都固定O(nlogn)。是很稳定的排序算法。

总结