常用排序算法汇总

发表于

1. 冒泡排序

思想

循环数组，比较当前元素和下一个元素，如果当前元素比下一个元素大，交换位置，这样最后一个元素就是最大数。

继续重复上面的操作，不循环已经排好的元素。

优化：当一次循环没有冒泡时，说明已经排序好了，可以停止循环。

复杂度

时间复杂度： O(n2)

空间复杂度:O(1)

稳定

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function bibbleSort(array){
    for(var j = 0; j<array.length; j++){
        let complete = true; //循环停止标识符
        for(var i = 0; i<array.length - 1 - j; i++){
            //比较相邻元素  (注意array.length要减一)
            if(array[i] > array[i+1]){
                [array[i], array[i+1]] = [array[i+1], array[i]];
                complete = false;
            }
        }
        if(complete){
            break;
        }
    }
    return array
}
bubbleSort([9,10,222,34,5,56,234,2,33,0,456,3,44,5,22,3,44,67,34])
//输出  [0, 2, 3, 3, 5, 5, 9, 10, 22, 33, 34, 34, 44, 44, 56, 67, 222, 234, 456]

2. 快速排序

思想

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据比另一部分的所有数据要小，再按这种方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，使整个数据变成有序序列。
可以看出，快速排序用到了分治的思想（对小问题进行递归）

步骤

  • 选择一个基准元素target（一般选择第一个数）
  • 将比target小的元素移动到数组左边，比target大的元素移动到数组右边
  • 分别对target左侧和右侧的元素进行快速排序

复杂度

时间复杂度：平均O(nlogn)，最坏O(n2)，实际上大多数情况下小于O(nlogn)

空间复杂度: O(logn)（递归调用消耗）

不稳定

代码

  • 写法1： 简单、但消耗空间
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function quickSort(array){
    if(array.length < 2){
        return array
    }
    //选一个target
    const target = array[0];
    const left = [];
    const right = [];
    for(let i = 1; i < array.length; i++){
        if(array[i] < target){
            left.push(array[i]);
        }
        else right.push(array[i]);
    }
    return quickSort(left).concat([target], quickSort(right));
}
quickSort([9,10,222,34,5,56,234,2,33,0,456,3,44,5,22,3,44,67,34])
//输出  [0, 2, 3, 3, 5, 5, 9, 10, 22, 33, 34, 34, 44, 44, 56, 67, 222, 234, 456]
  • 写法2： 节省空间，但稍微复杂

记录一个索引l从数组最左侧开始，记录一个索引r从数组右侧开始

在l<r的条件下，找到右侧小于target的值array[r]，并将其赋值到array[l]

在l<r的条件下，找到左侧大于target的值array[l]，并将其赋值到array[r]

这样让l=r时，左侧的值全部小于target，右侧的值全部小于target，将target放到该位置

这种方法需要先知道数组的长度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function quickSort(array, start, end){
    if(end - start < 1){
        return
    }
    const target = array[start];
    let l = start;
    let r = end;
    while(l < r){
        while(l < r && array[r] >= target){
          r--;
        }
        array[l] = array[r];
        while (l < r && array[l] < target) {
          l++;
        }
        array[r] = array[l];
    }
    array[l] = target;
    quickSort(array, start, l - 1);
    quickSort(array, l + 1, end);
    return array;
}
quickSort([9,10,222,34,5,56,234,2,33,0,456,3,44,5,22,3,44,67,34], 0, 18)
//输出  [0, 2, 3, 3, 5, 5, 9, 10, 22, 33, 34, 34, 44, 44, 56, 67, 222, 234, 456]

3. 插入排序

思想

将左侧序列看成一个有序序列，每次将一个数字插入该有序序列。

插入时，从有序序列最右侧开始比较，若比较的数较大，后移一位。

复杂度

时间复杂度： O(n2)

空间复杂度:O(1)

稳定

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function insertSort(array){
    for(let i = 0; i < array.length; i++){
        let target = i;
        for(let j = i-1; j >= 0; j--){
            if(array[j] > array[target]){
                [array[target], array[j]] = [array[j], array[target]];
                //一定要把target的索引交换, 否则会有大量浪费的比较
                target = j;
            }
            else break;
        }
    }
    return array
}
insertSort([9,10,222,34,5,56,234,2,33,0,456,3,44,5,22,3,44,67,34])
//输出  [0, 2, 3, 3, 5, 5, 9, 10, 22, 33, 34, 34, 44, 44, 56, 67, 222, 234, 456]

4. 选择排序

思想

每次循环选取一个最小的数字放到前面的有序序列中。

复杂度

时间复杂度： O(n2)

空间复杂度:O(1)

不稳定

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function selectionSort(array){
    for(let i = 0; i < array.length - 1; i++){
        let minIndex = i;
        for(let j = i + 1; j < array.length; j++){
            if(array[j] < array[minIndex]){
                //索引号一定要修改  否则无法真正调换两个元素
                minIndex = j;
            }
        }
        [array[minIndex], array[i]] = [array[i], array[minIndex]];
    }
    return array
}
selectionSort([9,10,222,34,5,56,234,2,33,0,456,3,44,5,22,3,44,67,34])
//输出  [0, 2, 3, 3, 5, 5, 9, 10, 22, 33, 34, 34, 44, 44, 56, 67, 222, 234, 456]

5. 堆排序 (较难)

思想

创建一个大顶堆，大顶堆的堆顶一定是最大的元素。

交换第一个元素和最后一个元素，让剩余的元素继续调整为大顶堆。

从后往前以此和第一个元素交换并重新构建，排序完成。

堆的概念

堆排序是一种树形选择排序，在排序过程中可以把元素看成是一颗完全二叉树。

每个节点都大（小）于它的两个子节点，当每个节点都大于等于它的两个子节点时，就称为大顶堆，也叫堆有序； 当每个节点都小于等于它的两个子节点时，就称为小顶堆。

复杂度

时间复杂度： O(nlogn)

空间复杂度:O(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
function heapSort(array){
    //创建大顶堆
    createMaxHeap(array);
    //交换第一个和最后一个元素, 然后重新调整
    for(let i = array.length-1; i > 0; i--){
        [array[i], array[0]] = [array[0], array[i]];
        adjust(array, 0, i);
    }
    return array;
}
//构建大顶端, 从第一个非子叶结点开始下沉操作
function createMaxHeap(array){
    const len = array.length;
    const start = parseInt(len / 2) - 1;
    for(let i = start; i >= 0; i--){
        adjust(array, i, len);
    }
}
//将第target个元素进行下沉，孩子节点有比他大的就下沉
function adjust(array, target, len) {
    for (let i = 2 * target + 1; i < len; i = 2 * i + 1) {
        // 找到孩子节点中最大的
        if (i + 1 < len && array[i + 1] > array[i]) {
            i = i + 1;
        }
        // 下沉
        if (array[i] > array[target]) {
            [array[i], array[target]] = [array[target], array[i]]
            target = i;
        } else {
            break;
        }
    }
}
heapSort([9,10,222,34,5,56,234,2,33,0,456,3,44,5,22,3,44,67,34])
//输出  [0, 2, 3, 3, 5, 5, 9, 10, 22, 33, 34, 34, 44, 44, 56, 67, 222, 234, 456]

6. 归并排序

思想

分治法的一个典型应用。

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

分割:

  • 将数组从中点进行分割，分为左、右两个数组
  • 递归分割左、右数组，直到数组长度小于2

归并:

如果需要合并，那么左右两数组已经有序了。

创建一个临时存储数组temp，比较两数组第一个元素，将较小的元素加入临时数组

若左右数组有一个为空，那么此时另一个数组一定大于temp中的所有元素，直接将其所有元素加入temp

复杂度

时间复杂度： O(nlogn)

空间复杂度: O(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
function mergeSort(array){
    if(array.length < 2){
        return array
    }
    const mid = Math.floor(array.length / 2);
    const front = array.slice(0, mid);
    const end = array.slice(mid);
    return merge(mergeSort(front), mergeSort(end));
}
function merge(front, end){
    const temp = [];
    while(front.length && end.length){
        if(front[0]<end[0]){
            temp.push(front.shift());
        }
        else temp.push(end.shift());
    }
    while(front.length){
        temp.push(front.shift());
    }
    while(end.length){
        temp.push(end.shift());
    }
    return temp
}
mergeSort([9,10,222,34,5,56,234,2,33,0,456,3,44,5,22,3,44,67,34])
//输出  [0, 2, 3, 3, 5, 5, 9, 10, 22, 33, 34, 34, 44, 44, 56, 67, 222, 234, 456]
  • 写法2： 记录数组的索引，使用left、right两个索引来限定当前分割的数组。
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
function mergeSort(array, left, right, temp) {
    if (left < right) {
    const mid = Math.floor((left + right) / 2);
    mergeSort(array, left, mid, temp)
    mergeSort(array, mid + 1, right, temp)
    merge(array, left, right, temp);
    }
    return array;
}
function merge(array, left, right, temp) {
    const mid = Math.floor((left + right) / 2);
    let leftIndex = left;
    let rightIndex = mid + 1;
    let tempIndex = 0;
    while (leftIndex <= mid && rightIndex <= right) {
    if (array[leftIndex] < array[rightIndex]) {
        temp[tempIndex++] = array[leftIndex++]
    } else {
        temp[tempIndex++] = array[rightIndex++]
    }
    }
    while (leftIndex <= mid) {
    temp[tempIndex++] = array[leftIndex++]
    }
    while (rightIndex <= right) {
    temp[tempIndex++] = array[rightIndex++]
    }
    tempIndex = 0;
    for (let i = left; i <= right; i++) {
    array[i] = temp[tempIndex++];
    }
}
mergeSort([9,10,222,34,5,56,234,2,33,0,456,3,44,5,22,3,44,67,34], 0, 18, [])
//输出  [0, 2, 3, 3, 5, 5, 9, 10, 22, 33, 34, 34, 44, 44, 56, 67, 222, 234, 456]
Snapline wechat
扫码关注我的公众号“约翰柠檬的唱片店”
Buy me a cup of Coffee