排序算法

  • 2021-12-12
  • 次

在这里插入图片描述

比较类排序

– 冒泡排序（内外循环）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function bubbleSort(arr) {
	for(var i=0, n=arr.length;i<n;i++) {
		var flag = 0 // 优化
		for(var j=0;j<n-i-1;j++) {
			if(arr[j+1]<arr[j]) {
				var t = arr[j+1]
				arr[j+1]=arr[j]
				arr[j]=t
				flag = 1
			}
		}
		if(flag === 0) break
	}
	return arr
}

双向冒泡排序法（鸡尾酒排序）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function bubbleTwoWaySort(arr) {
	var t, left = 0, right = arr.length - 1
	while(left < right) {
		for(var j = left;j <= right;j++) {
			if(arr[j+1]<arr[j]) {
				t = arr[j+1]
				arr[j+1]=arr[j]
				arr[j]=t
			}
		}
		left++
		if(left >= right) break
		for(var k = right; k >= left;k--) {
			if(arr[k-1] > arr[k]) {
				t = arr[k-1]
				arr[k-1] = arr[k]
				arr[k] = t
			}
		}
		right--
	}
	return arr
}

考虑这样的一个序列：(2,3,4,5,1) 。如果使用鸡尾酒排序，一个来回就可以搞定；而冒泡排序则需要跑四趟。
其根本原因在于冒泡是单向的，如果从左向右冒泡，对于小数靠后就会很不利（一趟只能挪一个位置，那就需要多次循环。这种数又被称之为乌龟）；相应的，如果从右向左冒泡，对于大数靠前又会很不利（靠前的一只大乌龟）。鸡尾酒排序的优点就在于这里，由于在序列中左右摇摆（为此鸡尾酒排序又称之为 shaker sort），两种较差的局面就能得到规避，以此在性能上带来一些提升。

– 选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function selectSort(arr) {
	for(var i = 0, n = arr.length;i < n-1;i++){
		var min = i
		for(var j = i + 1;j < n;j++){
			if(arr[j]<arr[min]){
				min = j
			}
		}
		if(min !== i) {
			var temp = arr[i]
			arr[i] = arr[min]
			arr[min] = temp
		}
	}
	return arr
}

– 插入排序

1
2
3
4
5
6
7
8
9
10
11
12
function insertSort(arr) {
	for(var i = 1, n = arr.length; i < n ; i++) {
		var j = i - 1
		var current = arr[i]
		while(current < arr[j] && j >= 0) {
			arr[j+1] = arr[j]
			j--
		}
		arr[j+1] = current
	}
	return arr
}

– 折半插入排序
减少搜索次数，但数据交换次数不变

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function insertSort2 (arr) {
  for (let i = 1, n = arr.length; i < n; i++) {
    let right = i
    let left = 0
    let mid
    var current = arr[i]
    while (left <= right) {
      mid = Math.floor(left + (right - left) / 2)
      if (current < arr[mid]) right = mid - 1
      else left = mid + 1
    }
    for (var j = i - 1; j >= left; j--) arr[j + 1] = arr[j]
		arr[j+1] = current
  }
  return arr
}

– 希尔排序（又称缩小增量排序）（本质还是插入排序）
将待排序列按照某种规则分成几个子序列，分别对这几个子序列进行直接插入排序。这个规则的体现就是增量的选取，如果增量是1， 那就是直接插入排序。

首先，我们来回忆一下，插入排序的优点，它有两个优点：
对于小数列的速度很快（所以被用来做其他高级排序在小数列情况下的优化实现）
依赖输入，对于接近有序的数列很快
希尔排序就是充分利用了这两个优点，来优化插入排序。那么，希尔排序做了哪些改动呢：

  1. 将数组分隔成更小的数组
    希尔排序假设一个值 h, 将数列中,间隔为 h 的元素，作为一个新的子数列，这时，将整个大的数列分成了若干小数列，然后挨个处理子数列。因为 优点1，所以希尔排序会表现得很快。然后减小 h 的值，直到 1。
  2. 对基本有序的大数列排序
    当 h=1 的时候，就是对整个数组运行一遍插入排序，数组有序。因为之前的操作，使得整个数列已经处于基本有序的状态了。这时充分利用了 优点2，排序也会表现得很快。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function shellSort(arr) {
	var len = arr.length;
	// gap一直到1（直接插入排序）
    for (var gap = Math.floor(len / 2); gap > 0; gap = Math.floor(gap / 2)) {
        for (var i = gap; i < len; i++) {
            var j = i;
            var current = arr[i];
            while (j - gap >= 0 && current < arr[j - gap]) {
                 arr[j] = arr[j - gap];
                 j = j - gap;
            }
            arr[j] = current;
        }
    }
    return arr;
}

– 归并排序(重点在于合并)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function mergeSort(arr) {
	if(arr.length === 1) {
		return arr
	}
	var arr1 = mergeSort(arr.slice(0, arr.length / 2))
	var arr2 = mergeSort(arr.slice(arr.length / 2))
	return merge(arr1, arr2)
}
function merge(arr1, arr2) {
	var result = []
	var p1 = 0, p2 = 0
	while(p1 < arr1.length && p2 < arr2.length) {
		if(arr1[p1] < arr2[p2]){
			result.push(arr1[p1])
			p1++
		} else {
			result.push(arr2[p2])
			p2++
		}
	}
	return result.concat(arr1.slice(p1).concat(arr2.slice(p2)))
}

空间复杂度为O(1)的归并： 在merge的时候使用插入排序，- > -用时间换取空间(小声哔哔)
– 快速排序
取巧写法

1
2
3
4
5
6
7
8
9
10
11
function quickSort(arr) {
	if(arr.length <= 1) return arr
	var [current] = arr.splice(0,1)
	var arr1 = arr.filter(item => item <= current)
	var arr2 = arr.filter(item => item > current)
	return [
		...quickSort(arr1),
		current,
		...quickSort(arr2)
	]
}

常规写法(性能比上面的高)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function quickSort(arr, left, right) {
	if(left < right) {
		var mid = pritation(arr, left, right)
		quickSort(arr, left, mid-1)
		quickSort(arr, mid+1, right)
	}
}
function pritation(arr, left, right) {
	var i = left
	var j = right
	var temp = arr[left]
	while(i < j) {
		while(i < j && arr[j]>=temp) j--
		if(i<j) arr[i++] = arr[j]
		while(i < j && arr[i]<temp) i++
		if(i<j) arr[j--] = arr[i]
	}
	arr[i] = temp
	return i
}

另一种不错的写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
function quickSort2(ary, comparator = (a, b) => a - b) {
  return partition(ary, comparator)
}
function partition(ary, comparator, start = 0, end = ary.length - 1, ) {
  if (start >= end) {
    return
  }

  var pivotIndex = Math.floor(Math.random() * (end - start + 1) + start)
  var pivot = ary[pivotIndex]

  swap(ary, pivotIndex, end)

  for (var i = start - 1, j = start; j < end; j++) {
    if (comparator(ary[j], pivot) < 0) {
      i++
      swap(ary, i, j)
    }
  }

  swap(ary, i + 1, end)
  partition(ary, comparator, start, i)
  partition(ary, comparator, i + 2, end)
  return ary
}

非递归方法实现快排（使用栈）（函数递归开销大）

1
2
3
4
5
6
7
8
9
10
11
function quickSort2(arr, left, right) {
	var stack = [] //使用数组的push、pop方法实现栈效果
	stack.push(right, left)
	while(stack.length > 0) {
		var l = stack.pop(), r = stack.pop()
		if(l < r) {
			var mid = pritation(arr, l, r)
			stack.push(mid-1, l, r, mid+1)
		}
	}
}

– 堆排序(利用递归，反正只要把最大值或者最小值放到根节点就好了)
大顶堆：父亲大孩子小
小顶堆：父亲小孩子大

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
function heapSort(arr) {
	// 建堆
	for(var i = Math.floor(arr.length / 2); i >= 0; i--) {
		maxHeapify(arr, i, arr.length)
	}
	// 已经将最大值放在根节点了
	// 进行堆排序，将根节点与叶子节点交换，重新建堆
	for(var j = arr.length - 1; j>= 0 ; j--) {
		var t = arr[0]
		arr[0] = arr[j]
		arr[j] = t
		maxHeapify(arr, 0, j-1) // 排好序的不需参与建堆
	}
}
function maxHeapify(arr, i, size) {
	// 父亲i, 孩子2i+1和2i+2
	var l = 2*i + 1, r = 2*i + 2, largest = i
	if (l <= size && arr[l] > arr[largest]) {
        largest = l
    }
    if (r <= size && arr[r] > arr[largest]) {
        largest = r
	}
	if(largest !== i) {
		var t = arr[i]
		arr[i] = arr[largest]
		arr[largest] = t
        maxHeapify(arr, largest, size)
	}
}

非比较类排序

– 计数排序
找到最小值和最大值，建立从最小值到最大值的数的count（数组对象），遍历数组，count[key]++，再遍历count输出排好序的数组。
优点：O(n+k)
缺点：数据量大或者数据跨度大（例如数组[1,100000000,999]）的时候，消耗内存空间、时间大

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function countingSort (arr) {
	let n = arr.length
	if (n <= 1) return arr
	let min = Math.min.apply(null, arr)
	let max = Math.max.apply(null, arr)
	if (min === max) return arr
	let count = {}
	for (let i = 0; i < n; i++) {
		count[arr[i]] = count.hasOwnProperty(arr[i]) ? count[arr[i]] + 1 : 1
	}
	let res = []
	for (let i = min; i <= max; i++) {
		while(count[i]--) {
			res.push(i)
		}
	}
	return res
}

– 桶排序
将数据分组，对每一组内分别排序，再合并
比如对1-100岁人员按照岁数排序，可以分为1-20岁一组，20-40岁一组，内部排好序后合并。
数据输入：数组以及桶的个数bucket
得到每组范围(max-min+1)/bucket
此排序主要适用于均匀分布的数字数组，在这种情况下能够达到最大效率

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
function bucketSort(arr, bucket) {
	var n = arr.length;
	var result = [];
	if(n <= 1) return arr;
	bucket = bucket || 1;
	// 找到数组最大和最小值
	var min = Math.min.apply(null, arr), max = Math.max.apply(null, arr);
	if(min === max) return arr;
	// 每一个桶的范围
	var f = (max - min + 1) / bucket;
	var mybucket = new Array(bucket);
	for(var i = 0; i < n; i++) {
		var index = Math.floor((arr[i] - min)/f);
		mybucket[index] = mybucket[index] || [];
		var currbucket = mybucket[index];
		currbucket.push(arr[i]);
		var k = currbucket.length - 2;
		while(k >= 0 && currbucket[k] > arr[i]) {
			currbucket[k+1] = currbucket[k];
			k--;
		}
		currbucket[k+1] = arr[i]
	}
	for(var i = 0; i < bucket; i++) {
		if(mybucket[i])
			result = result.concat(mybucket[i])
	}
	return result
}

– 基数排序
基数排序是一种非比较型的整数排序算法。其基本原理是，按照整数的每个位数分组。在分组过程中，对于不足位的数据用0补位。
基数排序按照对位数分组的顺序的不同，可以分为LSD（Least significant digit）基数排序和MSD（Most significant digit）基数排序。

LSD基数排序，是按照从低位到高位的顺序进行分组排序。MSD基数排序，是按照从高位到低位的顺序进行分组排序。上述两种方式不仅仅是对位数分组顺序不同，其实现原理也是不同的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
function lsdSort(arr) {
	var n = arr.length;
	if(n<=1) return arr;
	var bucket = new Array(10)
	var result = arr
	var max = Math.max.apply(null, arr)
	// 根据max的位数确定要进行多少次桶排序
	var count = max.toString().length;
	for(var i = 0; i < count; i++) {
		for(var j = 0; j < n; j++) {
			// i=0 -> 个位
			// i=1 -> 十位
			var curr = Math.floor(result[j]/(Math.pow(10,i))) % 10
			bucket[curr] = bucket[curr] || []
			bucket[curr].push(result[j])
		}
		result = []
		for(var j = 0; j < 10; j++) {
			if(bucket[j]) {
				result = result.concat(bucket[j])
			}
		}
		// 重置桶
		bucket = new Array(10)
	}
	return result
}

MSD:最开始时也是遍历所有元素，取最大值，得到最大位数，建立10个桶。这时从百位取起。不足三位，对应位置为0.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
function msdSort(arr, times) {
	var n = arr.length;
	if(n<=1) return arr;
	var bucket = new Array(10)
	var result = []
	var max = Math.max.apply(null, arr)
	var min = Math.min.apply(null, arr)
	if(max === min) return arr;
	// 根据max的位数确定要进行多少次桶排序
	var count = times || max.toString().length;
	// 只需要取最高位，其他递归
	for(var j = 0; j < n; j++) {
		var curr = Math.floor(arr[j]/(Math.pow(10,count-1))) % 10
		// 取该位数
		bucket[curr] = bucket[curr] || []
		bucket[curr].push(arr[j])
	}
	// console.log(bucket)
	// 遍历桶，多于一个数的递归排序
	for(var j = 0; j < 10; j++) {
		if(bucket[j]) {
			result = result.concat(msdSort(bucket[j], count - 1))
		}
	}
	return result
}

【参考】
常用12大排序算法之十二：鸡尾酒（双向冒泡或改进冒泡）排序算法

算法系列之五 希尔排序

感谢您的阅读，本文由 Astar 版权所有。如若转载，请注明出处：Astar（http://example.com/2021/12/12/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95/）
设计模式
javascript基础篇（汇总）