Javascript和O(n^2)时间复杂度的排序
O(n^2)时间复杂度的排序方法往往是入门算法的经典，在实际应用中使用的比较少，但是对于锻炼编程思维是有很大帮助的，而此类排序方法又以冒泡、选择和插入排序为典型代表，以下所有代码参考自慕课网刘波波老师的C++版本实现。
冒泡排序
这是实现起来最简单的排序算法，也是效率比较低的一类排序算法，但是很多编程语言都把它当做是否掌握了其基本语法的一个考验。它的实现就是使用两个循环遍历数组，然后在内层循环将大的数字和小的数字彼此交换位置，最终得到结果。
function bubbleSort(nums) {
var i, j, temp;
for (i = 0; i < nums.length - 1; i++)
for (j = 0; j < nums.length - 1 - i; j++)
//需要交换
if (nums[j] > nums[j + 1]) {
//交换
temp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = temp;
}
return nums;
}
选择排序
选择排序的思想很容易理解：我假设排在最前面的就是最小的数字，第二位的次之，以此类推，然后我遍历数组找到最小的、次小的...逐个填进去就行了。
function selectSort(arr) {
var len = arr.length;
for (var i = 0; i < len; i++) {
for (var j = i + 1; j < len; j++) {
if (arr[j] < arr[i]) {
// 解构赋值交换
[arr[i], arr[j]] = [arr[j], arr[i]];
}
}
}
return arr;
}
插入排序
插入排序的思想比较难理解些，不过算法导论类比了玩扑克时插入一张新牌的过程：即数组刚开始是有序的，每次新增一个新元素又变成一个更大的有序数组，最后得到最终的排序好的数组。
var insertSort = function(arr) {
let len = arr.length;
for (let i = 1; i < len; i++) {
//把执行体的条件移到循环体里去，精简代码体积
for (let j = i; j > 0 && arr[j] < arr[j - 1]; j--) {
[arr[j - 1], arr[j]] = [arr[j], arr[j - 1]];
}
}
return arr;
}
//优化版本
let insertSort2 = function(arr) {
let len = arr.length;
for (let i = 1; i < len; i++) {
let e = arr[i];//用e保存arr[i],减少交换次数
let j; // j保存元素e应该插入的位置,要排序就会变，不排就是i
for (j = i; j > 0 && arr[j - 1] > e; j--)
arr[j] = arr[j - 1];
arr[j] = e;
}
return arr;
}
后面有人提出了插入排序的改进版：希尔排序。
希尔排序
我们先把插入排序改造一下：
function insertSort(nums, step = 1) {
for (let i = step; i < nums.length; i++) {
let e = nums[i],
j
for (j = i; j >= step && e < nums[j - step]; j -= step) {
[nums[j], nums[j - step]] = [nums[j - step], nums[j]]
}
nums[j] = e
}
return nums
}
然后创建希尔排序函数：
function shellSort(nums) {
// 初始化最大步长：1/4/13/40...len的三分之一
let h = 1
while (h < parseInt(nums.length / 3)) h = 3 * h + 1
while (h >= 1) {
nums = insertSort(nums, h)
//逐步缩小步长
h = parseInt(h / 3)
}
return nums
}
结语
这四个排序算法里，大多数情况插入排序（希尔排序）的效率是最高的，因为它可以提前终止内层循环，而另外两个算法是需要执行完完整的两层循环过程。
