《JavaScript算法》常见排序算法思路与代码实现
冒泡排序
通过相邻元素的比较和交换，使得每一趟循环都能找到未有序数组的最大值或最小值。
最好：O(n),只需要冒泡一次数组就有序了。
最坏： O(n²)
平均： O(n²)
*单项冒泡
function bubbleSort(nums) {
for (let i=0 , len=nums.length; i<len-1; i++) {
//如果一轮比较中没有需要交换的数据，则说明数组已经有序，主要是为了对[5，1，2，3，4]之类的数组进行优化。
let mark = true;
for (let j = 0; j < len-i-1; i++) {
if (nums[j] > nums[j+1]) {
[nums[j],nums[j+1]] = [nums[j+1],nums[j]]
mark = false
}
}
if (mark) return nums
}
}
双向冒泡
普通的冒泡排序在一趟循环中只能找出一个最大值或最小值，双向冒泡则是多一轮循环既找出最大值也找出最小值
function bubbleSort_twoWays(nums) {
let low = 0
let high = nums.length - 1
while(low < high) {
let mark = true
// 找到最大值放到到右边
for (let i=low; i<high; i++) {
if(nums[i] > nums[i+1]) {
[nums[i],nums[i+1]] = [nums[i+1],nums[i]]
mark = false
}
}
high--
// 找到最小值放到左边
for(let j=high;j>low;j--) {
if(nums[j] < nums[j-1]) {
[nums[j],nums[j-1]] = [nums[j-1],nums[j]]
mark = false
}
}
low++
if(mark) return nums
}
}
选择排序
和冒泡排序相似，区别在于选择排序是将每一个元素和它后面的元素进行比较和交换。
最好： O(n²)
最坏： O(n²)
平均： O(n²)
function selectSort(nums) {
for (let i = 0, len = nums.length; i < len; i++) {
for (let j = i + 1; j < len; j++) {
if (nums[i] > nums[j]) {
[nums[i], nums[j]] = [nums[j], nums[i]]
}
}
}
return nums
}
插入排序
以第一个元素作为有序数组，其后的元素通过在这个已有序的数组中找到合适的位置并插入。
最好： O(n)，原数组已经是升序的。
最坏： O(n²)
平均： O(n²)
function insertSort(nums) {
for (let i = 1,len = nums.length;i < len; i++) {
let temp = nums[i]
let j = i
while (j >= 0 && temp < nums[j-1]) {
nums[j] = nums[j-1]
j--
}
nums[j] = temp
}
return nums
}
快速排序
选择一个元素作为基数（通常是第一个元素），把比基数小的元素放到它左边，比基数大的元素放到它右边（相当于二分），再不断递归基数左右两边的序列。
最好： O(n * logn)，所有数均匀分布在基数的两边，此时的递归就是不断地二分左右序列。
最坏： O(n²)，所有数都分布在基数的一边，此时划分左右序列就相当于是插入排序。
平均： O(n * logn)
- 快速排序之填坑
从右边向中间推进的时候，遇到小于基数的数就赋给左边（一开始是基数的位置），右边保留原先的值等之后被左边的值填上
计数排序
以数组元素值为键，出现次数为值存进一个临时数组，最后再遍历这个临时数组还原回原数组。因为 JavaScript 的数组下标是以字符串形式存储的，所以计数排序可以用来排列负数，但不可以排列小数。
最好： O(n + k)，k是最大值和最小值的差。
最坏： O(n + k)
平均： O(n + k)
function countingSort(nums) {
let arr = []
let max = Math.max(...nums)
let min = Math.min(...nums)
// 装桶
for (let i=0, len=nums.length; i<len; i++) {
let temp = nums[i]
arr[temp] = arr[temp] + 1 || 1
}
let index = 0
//还原数组
for (let i=min; i<=max; i++) {
while(arr[i]>0) {
nums[index++] = i
arr[i]--
}
}
return nums
}
希尔排序
通过某个增量 gap，将整个序列分给若干组，从后往前进行组内成员的比较和交换，随后逐步缩小增量至 1。希尔排序类似于插入排序，只是一开始向前移动的步数从 1 变成了 gap。
最好： O(n * logn)，步长不断二分。
最坏： O(n * logn)
平均： O(n * logn)
function shellSort(nums) {
let len = nums.length
// 初始步数
let gap = parseInt(len / 2)
// 逐渐缩小步数
while (gap) {
// 从第gap个元素开始遍历
for (let i = gap; i < len; i++) {
//逐步和前面其他成员进行比较和交换
for (let j = i - gap; j >= 0; j -= gap) {
if (nums[j] > nums[j + gap]) {
[nums[j], nums[j + gap]] = [nums[j + gap], nums[j]]
} else {
break
}
}
}
gap = parseInt(gap / 2)
}
return nums
}