排序算法
直接插入排序
直接插入排序的思路是遍历过程中保持被遍历过的元素有序，每遍历到一个新元素时如不能保持已遍历元素有序，则为该新元素寻找合适的插入位置插入以保持遍历元素的有序性，当完成遍历时所有元素均有序。
假设初始列表items = [4, 2, 3, 1, 5]，非降序的直接插入排序过程如下：
- 初始已遍历内容为[4]，从i = 1开始，items[i = 1] = 2，[4] => 插入2 => [2, 4]
- items[i = 2] = 3，[2, 4] => 插入3 => [2, 3, 4]
- items[i = 3] = 1，[2, 3, 4] => 插入1 => [1, 2, 3, 4]
- items[i = 4] = 5，[1, 2, 3, 4] => 插入5 => [1, 2, 3, 4, 5]
代码实现：
function insertSort(items) {
let i, j, tmp;
for (i = 1; i < items.length; i++) {
if (items[i] < items[i - 1]) {
tmp = items[i];
items[i] = items[i - 1];
for (j = i - 1; j >= 0 && items[j] > tmp; j--) {
items[j + 1] = items[j];
}
items[j + 1] = tmp;
}
}
return items;
}
冒泡排序
经典排序算法，可总结成：“两两比较，两两交换”，每一轮比较和交换可以将一个最大或最小元素移动到对应的位置。
假设初始列表items = [4, 2, 3, 1, 5]，非降序的冒泡排序过程如下：
- [(2, 4), 3, 1, 5] => [2, (3, 4), 1, 5] => [2, 3, (1, 4), 5] => [2, 3, 1, (4, 5)]
- [(2, 3), 1, 4, 5] => [2, (1, 3), 4, 5] => [2, 1, (3, 4), 5]
- [(1, 2), 3, 4, 5] => [1, (2, 3), 4, 5]
- [(1, 2), 3, 4, 5] => [1, 2, 3, 4, 5]
流程里中括号内的小括号是进行比较和交换的元素，整个排序看起来像是目标元素从列表中向上“冒出”的过程，所以被称为冒泡排序。
代码实现：
function bubbleSort(items) {
let i, j, tmp;
for (i = 0; i < items.length - 1; i++) {
for (j = 1; j < items.length - i; j++) {
if (items[j] < items[j - 1]) {
tmp = items[j];
items[j] = items[j - 1];
items[j - 1] = tmp;
}
}
}
return items;
}
选择排序
选择排序的思路是在遍历过程中依次挑选出最大、次大、第三大...元素，并将其移动到对应的位置上，当然也可以反过来用挑选最小、次小、第三小...的方式。
假设初始列表items = [4, 2, 3, 1, 5]，非降序的选择排序过程如下：
- i = 0，找到最小元素的下标为3，交换后：[1, 2, 3, 4, 5]
- i = 1，...，[1, 2, 3, 4, 5]
- i = 2，...，[1, 2, 3, 4, 5]
- i = 3，...，[1, 2, 3, 4, 5]
代码实现：
function selectSort(items) {
let i, j, tmp;
for (i = 0; i < items.length - 1; i++) {
let k = i;
for (j = i + 1; j < items.length; j++) {
if (items[k] > items[j]) {
k = j;
}
}
tmp = items[k];
items[k] = items[i];
items[i] = tmp;
}
return items;
}
希尔排序
希尔排序是对直接插入排序的一种优化改进，做法是先挑选一个递减的delta序列，随后遍历delta序列时从待排序序列中按步长为delta的方式挑选子序列（共delta个）进行直接插入排序，直到delta = 1进行最后一次排序后，整个序列有序。
假设初始列表items = [4, 2, 6, 3, 1, 5, 8, 7]，非降序的希尔排序排序过程如下：
- 选择delta序列[3, 2, 1]
- delta = 3，对子序列[4, 3, 8]、[2, 1, 7]、[6, 5]分别排序得到[3, 4, 8]、[1, 2, 7]、[5, 6]，此时items = [3, 1, 5, 4, 2, 6, 8, 7]
- delta = 2，对子序列[3, 5, 2, 8]、[1, 4, 6, 7]分别排序得到[2, 3, 5, 8]、[1, 4, 6, 7]，此时items = [2, 1, 3, 4, 5, 6, 8, 7]
- delta = 1，对序列[2, 1, 3, 4, 5, 6, 8, 7]排序得到[1, 2, 3, 4, 5, 6, 7, 8]
代码实现：
function shellSort(items) {
let delta = [];
let n = items.length;
do {
delta.push(n = Math.floor(n / 2));
} while (n > 1);
let i, j, k, l, tmp;
for (i = 0; i < delta.length; i++) {
j = delta[i];
for (k = j; k < items.length; k++) {
if (items[k] < items[k - j]) {
tmp = items[k];
for (l = k - j; l >= 0 && tmp < items[l]; l -= j) {
items[l + j] = items[l];
}
items[l + j] = tmp;
}
}
}
return items;
}
快速排序
快速排序的思路是先从序列中选择一个元素作为“轴中数”，然后分别将大于轴中数的元素放到右侧，小于的元素放在左侧，接着对左侧和右侧的数再次采用快速排序，快速排序的终止条件是待排序序列长度不大于1。
假设初始列表items = [4, 2, 3, 1, 5]，非降序的快速排序过程如下：
- [4, 2, 3, 1, 5]:4 => [(1, 2, 3), 4, (5)]
- [1, 2, 3]:1、[5]:5 => [1, (2, 3), 4, 5]
- [2, 3]:2 => [1, 2, (3), 4, 5]
- [3]:3 => [1, 2, 3, 4, 5]
上述过程，中括号接冒号后面的值表示所选的轴中数（序列第一个元素），代码如下：
function quickSort(items) {
return _sort(items, 0, items.length - 1);
function _sort(items, low, high) {
if (low >= high) {
return items;
}
let i = low;
let j = high;
let pivot = items[low];
while (i < j) {
while (i < j && items[j] >= pivot) j--;
items[i] = items[j];
while (i < j && items[i] <= pivot) i++;
items[j] = items[i];
}
items[i] = pivot;
_sort(items, low, i - 1);
_sort(items, i + 1, high);
return items;
}
}
堆排序
对于长度为n的序列，大根堆的元素满足：Ai >= A2i, 2i+1(2i + 1 < n)，小根堆的元素满足：Ai <= A2i, 2i+1(2i + 1 < n)。可将序列转换为一颗完全二叉树，大根堆的约束是所有非叶子结点不小于其左右孩子结点，小根堆则是不大于。
堆排序过程是先将序列调整成大根堆或小根堆，然后取走堆的根元素并用最后面的元素填充到根元素位置，随后反复调整堆符合大（小）根堆的定义以及取走根元素与填充最后元素到根元素位置，直到堆为空。
假设初始列表items = [4, 2, 6, 3, 7, 1, 5]，他对应的完全二叉树如下：
|------4------|
| |
|---2---| |---6---|
| | | |
3 7 1 5
非降序的堆排序过程如下：
- 从items[floor(items.length / 2) - 1] = items[2] = 6开始向前调整，使其逐渐成为最大堆
- [4, 2, 6, 3, 7, 1, 5] => 6与1、5比较，不需要交换 => [4, 2, 6, 3, 7, 1, 5]
- [4, 2, 6, 3, 7, 1, 5] => 2与3、7比较，2与7交换 => [4, 7, 6, 3, 2, 1, 5]
- [4, 7, 6, 3, 2, 1, 5] => 4与7、6比较，4与7交换 => [7, 4, 6, 3, 2, 1, 5]，每一次交换需要考虑交换后的元素作为根的堆是否满足大根堆定义，不满足则需要继续交换，这里4与7交换后，4作为根的堆左右孩子分别为3、2，故无需调整
经过上面4步后，整个序列已经符合大根堆的定义，其对应的完全二叉树如下：
|------7------|
| |
|---4---| |---6---|
| | | |
3 2 1 5
接着进行后续步骤：
- 取走7，将5放在7的位置，并调整5作为根的堆成为大根堆，[7, 4, 6, 3, 2, 1, 5] => [5, 4, 6, 3, 2, 1]、[7] => [6, 4, 5, 3, 2, 1]、[7]
- [6, 4, 5, 3, 2, 1]、[7] => 取走6用1替代 => [1, 4, 5, 3, 2]、[6, 7] => 调整1作为根的堆成为大根堆 => [5, 4, 1, 3, 2]、[6, 7]
- [5, 4, 1, 3, 2]、[6, 7] => 取走5用2替代 => [2, 4, 1, 3]、[5, 6, 7] => 调整2作为根的堆成为大根堆 => [4, 3, 1, 2]、［5, 6, 7］
- ...与上类似
- 最终得到[]、[1, 2, 3, 4, 5, 6, 7]
代码如下：
function heapSort(items) {
let len = items.length;
for (let i = Math.floor(len / 2) - 1; i >= 0; i--) {
_fixHeap(items, i, len - 1);
}
for (let i = len - 1; i > 0; i--) {
let tmp = items[0];
items[0] = items[i];
items[i] = tmp;
_fixHeap(items, 0, i - 1);
}
return items;
function _fixHeap(items, s, m) {
let tmp = items[s];
for (let i = 2 * s + 1; i <= m; i = i * 2 + 1) {
if (i < m && items[i] < items[i + 1]) {
i++;
}
if (tmp >= items[i]) {
break;
}
items[s] = items[i];
s = i;
}
items[s] = tmp;
}
}
归并排序
归并排序的过程是多次将两个有序序列合并为一个有序序列，直到最后只剩下一个序列。
假设初始列表items = [4, 2, 6, 3, 1, 5, 8, 7]，非降序的归并排序排序过程如下（正向描述）：
- [4, 2, 6, 3, 1, 5, 8, 7] => 8个有序序列两两合并 => [(2, 4), (3, 6), (1, 5), (7, 8)]
- [(2, 4), (3, 6), (1, 5), (7, 8)] => 4个有序序列两两合并 => [(2, 3, 4, 6), (1, 5, 7, 8)]
- [(2, 3, 4, 6), (1, 5, 7, 8)] => 2个有序序列合并 => [(1, 2, 3, 4, 5, 6, 7, 8)]
代码采用的是递归方式，如下：
function mergeSort(items) {
if (items.length <= 1) {
return items;
}
let mid = Math.floor(items.length / 2);
let left = mergeSort(items.slice(0, mid));
let right = mergeSort(items.slice(mid));
let result = [];
let i = 0;
let j = 0;
while (i < left.length || j < right.length) {
if (i === left.length) {
result.push(right[j++]);
continue;
}
if (j === right.length) {
result.push(left[i++]);
continue;
}
if (left[i] < right[j]) {
result.push(left[i++]);
}
else {
result.push(right[j++]);
}
}
return result;
}