1.冒泡排序
开始学习排序算法时，通常都先学冒泡算法，因为它在所有排序算法中最简单。冒泡排序原理是比较相邻的两个项，如果前一项大于后一项，则交换他们。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| function bubbleSort(array) {
const { length } = array;
for (let i = 0; i < length; i++) {
for (let j = 0; j < length - 1; j++) {
if (array[j] > array[j + 1]) {
let num = array[j];
array[j] = array[j + 1];
array[j + 1] = num;
}
}
}
return array;
}
|
2.选择排序
选择排序算法是一种原址比较排序算法。选择排序原理是找到数据结构中的最小值并将其放置在第一位，接着找到第二小的值并将其放在第二位，以此类推。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| function selectionSort(array) {
const { length } = array;
let indexMin;
for (let i = 0; i < length - 1; i++) {
indexMin = i;
for (let j = i; j < length; j++) {
if (array[indexMin] > array[j]) {
indexMin = j;
}
}
if (i !== indexMin) {
let num = array[i];
array[i] = array[indexMin];
array[indexMin] = num;
}
}
return array;
}
|
3.插入排序
插入排序每次排一个数组项，以此方式构建最后的排序数组。假定第一项已经排序了。接着， 第二项和第一项进行比较，第二项是应该待在原位还是插到第一项之前呢?这样，头两项就已正确排序，接着和第三项比较(它是该插入到第一、第二还是第三的位置呢)，以此类推。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| function insertionSort(array) {
const { length } = array;
let temp;
for (let i = 1; i < length; i++) {
let j = i;
temp = array[i];
while (j > 0 && (array[j - 1] > temp)) {
array[j] = array[j - 1];
j--;
}
array[j] = temp;
}
return array;
}
|
4.归并排序
归并排序是一种分而治之算法。其思想是将原始数组切分成较小的数组，直到每个小数组只 有一个位置，接着将小数组归并成较大的数组，直到最后只有一个排序完毕的大数组。
由于是分治法，归并排序也是递归的。我们要将算法分为两个函数:第一个负责将一个大数 组分为多个小数组并调用用来排序的辅助函数。我们来看看在这里声明的主要函数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| function mergeSort(array) {
if (array.length > 1) {
const { length } = array;
const middle = Math.floor(length / 2);
const left = mergeSort(array.slice(0, middle));
const right = mergeSort(array.slice(middle, length));
array = merge(left, right);
}
return array;
}
function merge(left, right) {
let i = 0;
let j = 0;
const result = [];
while (i < left.length && j < right.length) {
result.push(left[i] < right[j] ? left[i++] : right[j++]);
}
return result.concat(i < left.length ? left.slice(i) : right.slice(j));
}
|
5.快速排序
快速排序也许是最常用的排序算法，和归并排序一样，快速排序也使用分而治之的方法，将原始数组 分为较小的数组(但它没有像归并排序那样将它们分割开)。
快速排序的原理也比较简单：首先，从数组中选择一个值作为主元(pivot)，也就是数组中间的那个值；创建两个指针(引用)，左边一个指向数组第一个值，右边一个指向数组最后一个值。移 动左指针直到我们找到一个比主元大的值，接着，移动右指针直到找到一个比主元小的值，然后 交换它们，重复这个过程，直到左指针超过了右指针。这个过程将使得比主元小的值都排在主元 之前，而比主元大的值都排在主元之后；接着，算法对划分后的小数组(较主元小的值组成的子数组，以及较主元大的值组成的 子数组)重复之前的两个步骤，直至数组已完全排序。
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 quickSort(array) {
if (array.length <= 1) {
return array;
}
let left = 0,right = array.length - 1;
let mid = Math.floor(array.length / 2);
while (left < right) {
while (array[left] < array[mid] && left < mid) {
left++;
}
while (array[right] > array[mid] && right >= mid) {
right--;
}
if (left < right) {
let num = array[left];
array[left] = array[right];
array[right] = num;
left++;
right--;
}
}
let leftArray = quickSort(array.slice(0, left));
let rightArray = quickSort(array.slice(left));
return [...leftArray, ...rightArray];
}
|
6.计数排序
计数排序使用一个用来存储每个元素在原始数组中出现次数的临时数组。在所有元素都计数完成后，临时数组已排好序并可迭代以构建排序后的结果数组。(它是一个整数排序算法)
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
31
32
| function countingSort(array) {
if (array.length <= 1) {
return array;
}
let maxValue = findMaxValue(array);
let counts = new Array(maxValue + 1);
array.forEach((num) => {
if (!counts[num]) {
counts[num] = 0;
}
counts[num]++;
});
let sortedIndex = 0;
counts.forEach((count, i) => {
while (count > 0) {
array[sortedIndex++] = i;
count--;
}
});
return array;
}
function findMaxValue(array) {
let maxValue = array[0];
for (let i = 1; i < array.length; i++) {
if (array[i] > maxValue) {
maxValue = array[i];
}
}
return maxValue;
}
|
7.桶排序
桶排序也是分布式排序算法，它将元素分为不同的桶(较小的数组)， 再使用一个简单的排序算法，例如插入排序(用来排序小数组的不错的算法)，来对每个桶进行 排序。然后，它将所有的桶合并为结果数组。
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
| function bucketSort(array, bucketSize = 5) {
if (array.length < 2) {
return array;
}
const buckets = createBuckets(array, bucketSize);
return sortBuckets(buckets);
}
function createBuckets(array, bucketSize) {
let minValue = array[0];
let maxValue = array[0];
for (let i = 1; i < array.length; i++) {
if (array[i] < minValue) {
minValue = array[i];
} else if (array[i] > maxValue) {
maxValue = array[i];
}
}
const bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;
const buckets = [];
for (let i = 0; i < bucketCount; i++) {
buckets[i] = [];
}
for (let i = 0; i < array.length; i++) {
const bucketIndex = Math.floor((array[i] - minValue) / bucketSize);
buckets[bucketIndex].push(array[i]);
}
return buckets;
}
function sortBuckets(buckets) {
const sortedArray = [];
for (let i = 0; i < buckets.length; i++) {
if (buckets[i] != null) {
insertionSort(buckets[i]);
sortedArray.push(...buckets[i]);
}
}
return sortedArray;
}
function insertionSort(array) {
const { length } = array;
let temp;
for (let i = 1; i < length; i++) {
let j = i;
temp = array[i];
while (j > 0 && array[j - 1] > temp) {
array[j] = array[j - 1];
j--;
}
array[j] = temp;
}
return array;
}
|
8. 基数排序
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
| function radixSort(array, radixBase = 10) {
if (array.length < 2) {
return array;
}
const minValue = findMinValue(array);
const maxValue = findMaxValue(array);
let significantDigit = 1;
while ((maxValue - minValue) / significantDigit >= 1) {
array = countingSortForRadix(array, radixBase, significantDigit, minValue);
significantDigit *= radixBase;
}
return array;
}
function countingSortForRadix(array, radixBase, significantDigit, minValue) {
let bucketsIndex;
const buckets = [];
const aux = [];
for (let i = 0; i < radixBase; i++) {
buckets[i] = 0;
}
for (let i = 0; i < array.length; i++) {
bucketsIndex = Math.floor(
((array[i] - minValue) / significantDigit) % radixBase
);
buckets[bucketsIndex]++;
}
for (let i = 1; i < radixBase; i++) {
buckets[i] += buckets[i - 1];
}
for (let i = array.length - 1; i >= 0; i--) {
bucketsIndex = Math.floor(
((array[i] - minValue) / significantDigit) % radixBase
);
aux[--buckets[bucketsIndex]] = array[i];
}
for (let i = 0; i < array.length; i++) {
array[i] = aux[i];
}
return array;
}
function findMaxValue(array) {
let maxValue = array[0];
for (let i = 1; i < array.length; i++) {
if (array[i] > maxValue) {
maxValue = array[i];
}
}
return maxValue;
}
function findMinValue(array) {
let minValue = array[0];
for (let i = 1; i < array.length; i++) {
if (array[i] < minValue) {
minValue = array[i];
}
}
return minValue;
}
|
