Yang's Blog HomeArchivesTagsCategories
几种经典的排序算法
|JavaScript
Word count: 1.5k|Reading time: 6 min

冒泡排序

冒泡排序实现思路

思路：

  1. 依次比较相邻的数字，如果前一个比后一个大，那么就交换。 即 小数放在前，大数放在后边。
  2. 然后比较第2个数和第3个数，小数在前，大数在后，依次类推则将最大的数滚动到最后边。
  3. 开始第二趟，将第二大的数移动至倒数第二位
  4. 依次类推…..

最后需要 第 （n-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
31
32
33
34
35
36
37
38
39
40
class ArrayList {
  array = []
  // 用于插入数据
  insert(item) {
    this.array.push(item)
  }
  swap(m,n) {
    let temp = this.array[m]
    this.array[m] = this.array[n]
    this.array[n] = temp
  }

 // 冒泡排序  （核心代码在这里）
  bubblesSort() {
    if (this.array === null || this.array.length < 2) { return }
    // 这里注意需要 length -1 。 原因是 如果是最后一个数会有bug，因为没有 第最后一个数+1的数
    // 也可以理解将 length -1 为 比较的次数
    for (let j = this.array.length - 1; j >= 0; j--) {
      for (let i = 0; i < j; i++) {
        if (this.array[i] > this.array[i + 1]) {
          this.swap(i, i + 1)
        }
      }
    }
  }


let list = new ArrayList()
list.insert(12)
list.insert(2)
list.insert(45)
list.insert(123)
list.insert(481)
list.insert(56)
console.log(list.array);   // [ 12, 2, 45, 123, 481, 56 ]


// 调用冒泡排序
list.bubblesSort()
console.log(list.array);  // [ 2, 12, 45, 56, 123, 481 ]Copy

选择排序

选择排序实现思路

思路：

从第一个数开始与后面的每个数进行比较，找出最小的（默认是升序），然后交换，以此类推，直到排序结束。

代码实现步骤思路：

  1. 先取出第一个数的下标值为变量 min ， 循环遍历数组的长度
  2. 在循环中 用第一个数 分别比较每个数，最后将最小的数的下标值赋值给 min
  3. 将俩个数交换。这样就实现了第一个数为最小值
  4. 最后在整体套个循环，循环上面的思路即可

代码实现

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
class ArrayList {
  array = [];

  // 用于插入数字
  insert(item) {
    this.array.push(item);
  }

  // 交换两个数字
  swap(m, n) {
    let temp = this.array[m];
    this.array[m] = this.array[n];
    this.array[n] = temp;
  }



  // 选择排序
  selectSort() {
    // 外部的循环表示 : 从0的位置开始取出数据，直到倒数第二个数的位置，即 length - 2
    for (let j = 0; j < this.array.length - 1; j++) {
      let min = j;
      // 内部的循环表示：从 min+1位置开始，和后面的数进行比较
      for (let i = min + 1; i < this.array.length; i++) {
        if (this.array[min] > this.array[i]) {
          min = i;
        }
      }
      this.swap(min, j);
    }
  }
  
}

let list = new ArrayList();
list.insert(12);
list.insert(2);
list.insert(45);
list.insert(123);
list.insert(481);
list.insert(56);
console.log(list.array); // [ 12, 2, 45, 123, 481, 56 ]


// 调用选择排序
list.selectSort();
console.log(list.array); // [ 2, 12, 45, 56, 123, 481 ]Copy

插入排序

插入排序思路

插入排序是简单排序中效率最好的一种

插入排序也是学习其他高级排序的基础，比如快速排序，

插入排序思想的核心 局部有序（部分有序）

思路:

  • 从 i 等于 1 开始变量，拿到当前数 current，与前面的数进行比较
  • 用while进行循环，如果前面的数大于当前的数，那么就进行交换。
  • 最好在外部套个循环，直到未排序的数没有了，那么排序就结束。

代码实现

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
class ArrayList {
  array = [];

  // 用于插入数字
  insert(item) {
    this.array.push(item);
  }


  //  插入排序
  insertSort() {
    for (let i = 1; i < this.array.length; i++) {
      let j = i; // 获取当前的下标值，存起来。
      let current = this.array[i];  // 获取当前的数，存起来
    // 由于不确定循环次数，所有用while
      while (this.array[j - 1] > current && j > 0) { 
      // 如果当前数的前一个比当前数大，就交换。
        this.array[j] = this.array[j - 1];
        j--;
      }
      // 将j位置的数，放到当前位置。
      this.array[j] = current;
    }
  }
}

let list = new ArrayList();
list.insert(12);
list.insert(2);
list.insert(45);
list.insert(123);
list.insert(481);
list.insert(56);
console.log(list.array);  // [ 12, 2, 45, 123, 481, 56 ]

// 调用 插入排序
list.insertSort();
console.log(list.array); // [ 2, 12, 45, 56, 123, 481 ]Copy

快速排序

快速排序思路

思路核心: 分而治之,即分成若个部分，逐个解决

思路:

  • 在数组中，选择一个数作为”基准”（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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class ArrayList {
  array = [];

  // 用于插入数字
  insert(item) {
    this.array.push(item);
  }

  // 快速排序
  quickSort() {
    const quick = (array) => {
      if (array.length <= 1) {return array;}
      let pivotIndex = Math.floor(array.length / 2);
      let pivot = array.splice(pivotIndex, 1)[0];
      let left = [];
      let right = [];
      for (let i = 0; i < array.length; i++) {
        if (array[i] > pivot) {
          right.push(array[i]);
        } else {
          left.push(array[i]);
        }
      }
      return quick(left).concat([pivot], quick(right));
    };
    return this.array = quick(this.array);
  }

}

let list = new ArrayList();
list.insert(12);
list.insert(2);
list.insert(45);
list.insert(123);
list.insert(481);
list.insert(56);
console.log(list.array);

// 调用快速排序
list.quickSort();
console.log(list.array);
Copy

归并排序

归并排序思路

归并排序也是采用 分而治之 的思想

将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

思路:

代码实现

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
class ArrayList {
  array = [];

  // 用于插入数字
  insert(item) {
    this.array.push(item);
  }

  // 归并排序
  mergeSort() {
    const mergerSorts = (array) => {
      if (array.length === 1) {return array;}
      let left = array.slice(0, Math.floor(array.length / 2));
      let right = array.slice(Math.floor(array.length / 2));
      const merge = (a, b) => {
        if (a.length === 0) return b;
        if (b.length === 0) return a;
        return a[0] < b[0] ? [a[0]].concat(merge(a.slice(1), b)) : [b[0]].concat(merge(a, b.slice(1)));
      };
      return merge(mergerSorts(left), mergerSorts(right));

    };
    return this.array = mergerSorts(this.array);
  }
}

let list = new ArrayList();
list.insert(12);
list.insert(2);
list.insert(45);
list.insert(123);
list.insert(481);
list.insert(56);
console.log(list.array);


// 调用归并排序
list.mergeSort();
console.log(list.array);
JavaScript