这里列举几种,前端常见的几种排序算法,记忆巩固一下吧,后期慢慢更新。算法才是最重要的。

1.冒泡排序

  • 比较相邻的元素,如果前一个比后一个大,就把它们两个调换位置。
  • 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。
  • 针对所有的元素重复以上的步骤,除了最后一个。
  • 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
bubleSort.js
  • js
1
2
3
4
5
6
7
8
9
10
11
12
// 冒泡排序
function bubleSort(arr){
let len = arr.length;
for(let i = 0; i < len; i++){
for(let j = 0; j < len - 1 - i; j++){
if(arr[j] > arr[j+1]){
[arr[j], arr[j+1]] = [arr[j+1], arr[j]];
}
}
}
return arr;
}

2.快速排序

  • 选择 中间的值 做为 基准值,把数组拆分成左右俩个数组
  • 比基准值大的放到 右边数组,比基准值小的放到 左边数组
  • 最后 排序一下 然后 拼接成排序好的数组
quickSort.js
  • js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function quickSort(arr){
let len = arr.length,
leftArr = [],
rightArr = [],
cenVal = arr[Math.floor(len/2)];
for(let i = 0; i < len; i++){
if(arr[i] < cenVal){
leftArr.push(arr[i]);
} else {
rightArr.push(arr[i]);
}
}
leftArr.sort((a,b) => a - b > 0 );
rightArr.sort((a,b) => a - b > 0 );
return [...leftArr, ...rightArr];
}

3.插入排序

  • 默认数组第一个是已经排序好的,从第二个元素开始排序
  • 第二个元素和第一个元素比较 如果第二个元素比第一个小 那么 这俩个元素互换位置
  • 然后从第三个元素开始,和第一个,第二个比较,把第三个元素 插入到 该在的位置,这样前三个就是排好序的。
  • 从第四个开始 重复上述步骤
insertSort.js
  • js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
Array.prototype.move = function (old_index, new_index) {
if (new_index >= this.length) {
var k = new_index - this.length;
while ((k--) + 1) {
this.push(undefined);
}
}
this.splice(new_index, 0, this.splice(old_index, 1)[0]);
return this; // for testing purposes
};
// 插入排序
function insertSort(arr){
let len = arr.length,
orderIndex;
for(let i = 1; i < len; i++){
for(let j = (i - 1); j >= 0; j--){
if(arr[i] < arr[j]){
orderIndex = j;
}
}
arr.move(i,orderIndex);
}
return arr;
}

4.选择排序

  • 从第一个元素开始和后面的所有元素比较,记录最小的位置,然后交换位置
  • 从第二个元素开始和后面的所有元素比较,继续循环比较
  • 重复上述步骤
selectSort.js
  • js
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
// 选择排序法一

/* 把小的数放到前面,下次遍历的时候从排好的数开始
* 每个数和它后面的每个数比较,把小的数放在前面
* 下次循环从已经比较好的数开始进行
*/
function unKonwSort(arr){
let len = arr.length;
for(let i = 0; i < len; i++){
for(let j = i+1; j < len; j++ ){
if(arr[i] > arr[j]){
[arr[i], arr[j]] = [arr[j], arr[i]];
}
}
}
return arr;
}

//选择排序法二

/* 循环只保留下标,在一次循环完成后再交换
*
*/
function selectSort(arr){
let minIndex,
len = arr.length;
for(let i = 0; i < len; i++){
minIndex = i;
for(let j = i + 1; j < len; j++){
if(arr[j] < arr[minIndex] ){
minIndex = j
}
}
[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
}
return arr;
}

参考链接

掘金