算法 | 常见的排序算法及其优化（含图示和JS实现）

Posted on Edited on In , Symbols count in article: 7.3k Reading time ≈ 7 mins.

冒泡排序

冒泡排序是通过重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成

算法思路

（以升序为例）

  • 比较相邻元素，初始为索引为0和索引为1的元素，如果第一个比第二个大，就交换这两个元素
  • 对每一对相邻元素重复同样的工作，直到最后一对，索引为arr.length - 2 和 arr.length - 1，这样 arr.length - 1索引处的元素将会是最大的
  • 重复步骤1和2，得到索引为arr.length - 2为剩余元素中最大的
  • 重复步骤1-3，直到排序完成

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function bubbleSort(arr) {
    for (let i = arr.length; i > 0; i--) {    // 用i来设置最后一组的边界
        for (let j = 0; j < i; j++) {
            if (arr[j] < arr[j-1]) {      // 如果顺序不对就交换
                [arr[j], arr[j-1]] = [arr[j-1], arr[j]];   // 交换
            }
        }
    }
    return arr;
}

// test
const arr = [2,7,4,3,8,9,10,1,5,2,3];
bubbleSort(arr);   // [1, 2, 2, 3, 3, 4, 5, 7, 8, 9, 10]

/*
	复杂度分析：
		时间复杂度： O(n^2)
		空间复杂度： 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
    function bubbleSortA(arr) {
        for (let i = arr.length; i > 0; i--) {
            let flag = false;   // flag用于标识此轮是否有交换行为
            for (let j = 0; j < i; j++) {
                if (arr[j-1] > arr[j]) {
                    flag = true;   // flag === true就表示有
                    [arr[j], arr[j-1]] = [arr[j-1], arr[j]];
                }
            }
            
            if (flag === false) {   // 这一轮没有交换行为 就表示全部都有序了 直接返回arr 
                return arr;
            }
        };
        return arr;
    }

    /*
    	复杂度分析：
    		时间复杂度： 最好O(n),只需要循环一次，最坏O(n^2)
    		空间复杂度： O(1)
    		
    	稳定性分析：冒泡排序并不会破坏元素的相对位置
    		稳定
    */

    // test
    const arr = [2,7,4,3,8,9,10,1,5,2,3];
    bubbleSortA(arr);   // [1, 2, 2, 3, 3, 4, 5, 7, 8, 9, 10]

  • 内层优化：在每一层循环的时候，记住这一层循环最后一次交换的位置，这样就说明后面的是有序的不用重复比较交换了

    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
    function bubbleSortB(arr) {
        let i = arr.length, pos;  // 用pos记录最后一次交换的位置
        while (i > 0) {
            let flag = false;   // flag用于标识此轮是否有交换行为
            for (let j = 0; j < i; j++) {
                if (arr[j-1] > arr[j]) {
                    flag = true;   // flag === true就表示有
                    pos = j;       // 目前最后一次交换在j的位置
                    [arr[j], arr[j-1]] = [arr[j-1], arr[j]];
                }
            };
            i = pos;    // 边界用pos代替
            
            if (flag === false) {   // 说明此轮没有交换行为
                return arr;
            }
        }
        return arr;
    }


    // test
    const arr = [2,7,4,3,8,9,10,1,5,2,3];
    bubbleSortB(arr);   // [1, 2, 2, 3, 3, 4, 5, 7, 8, 9, 10]


    /*
    	复杂度分析：
    		时间复杂度： O(n^2)
    		空间复杂度： O(1)
    		
    	稳定性分析：冒泡排序并不会破坏元素的相对位置
    		稳定
    */

选择排序

算法思路

  • 首先在未排序的数组中找到最大（小）的元素，放在排序数组的起始位置
  • 再从剩余的元素中找到最大（小）的元素，放在已经排序的末尾
  • 重复步骤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
function selectSort(arr) {
    for(let i = 0; i < arr.length; i++) {   // i表示排序数组的末尾索引
        let minValue = arr[i], minIndex = i;   // 用于记录未排序数组的最小元素和对应的索引
        for (let j = i+1; j < arr.length; j++) {
            if (arr[j] < minValue) {   // 通过遍历的方式查找
                minValue = arr[j];
                minIndex = j;
            }
        }
        [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];   // 找到后把排序数组的末尾索引元素和未排序数组中最小的元素进行交换
    }
    return arr;
}

// test
const arr = [2,7,4,3,8,9,10,1,5,2,3];
selectSort(arr);   // [1, 2, 2, 3, 3, 4, 5, 7, 8, 9, 10]


/*
	复杂度分析：
		时间复杂度： O(n^2)
		空间复杂度： 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
function selectSortA(arr) {
    for (let left = 0, right = arr.length - 1; left < right; left++, right--) {
        // 用于记录最大值和最小值的索引
        let minIndex = left, maxIndex = right;
        
        // 找到每次遍历的最大值和最小值的索引
        for (let index = left; index <= right; index++) {
            if (arr[index] < arr[minIndex]) minIndex = index;
            if (arr[index] > arr[maxIndex]) maxIndex = index;
        }
        
        // 交换
        [arr[left], arr[minIndex]] = [arr[minIndex], arr[left]];
        
        //此处是先排最小值的位置，所以得考虑最大值（arr[maxIndex]）在最小位置（left）的情况
        // 如果不考虑这里的话，因为前面已经交换过了，所以会导致无效交换，反而把最大值的value交换回来了
        if (left === maxIndex) {
            maxIndex = minIndex;
        }
        
        // 交换
        [arr[right], arr[maxIndex]] = [arr[maxIndex], arr[right]];
    }
    
    return arr;
};

// test
const arr = [2,7,4,3,8,9,10,1,5,2,3];
console.log(selectSortA(arr));   // [1, 2, 2, 3, 3, 4, 5, 7, 8, 9, 10]

插入排序

工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入

算法思路

  • 初始化：将第一个元素看作是有序数组，将第一个元素之后的元素看作是未排序序列
  • 遍历未排序序列，并依次插入到有序数组的合适位置（这里需要注意的是，插入到排序数组合适位置之后排序数组的其他元素的位置是如何处理的？）
  • 返回排序数组

算法实现

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 insertSort(arr) {
    for (let i = 1; i < arr.length; i++) {
        let value = arr[i];   // 记录未排序数组的第一个元素
        let position = i;     // 记录此刻的位置
        while (position >= 0 && arr[position - 1] > value) {   // 把此刻的元素插入到排序数组的合适位置
            [arr[position], arr[position - 1]] = [arr[position-1], arr[position]];
            position--;
        };
    };
    return arr;
}

// test
const arr = [2,7,4,3,8,9,10,1,5,2,3];
insertSort(arr);   // [1, 2, 2, 3, 3, 4, 5, 7, 8, 9, 10]


/*
	复杂度分析：
		时间复杂度： O(n^2)
		空间复杂度： 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
37
function insertSortA(arr) {
	for (let i = 1; i < arr.length; i++) {
        let value = arr[i];  // 记录当前元素
        let position = i;   // 记录当前位置
        let insertIndex = searchInsert(arr.slice(0, i), value);   // 利用二分查找找到要插入的位置
        
        // 找到位置后把后面的元素都往后面移动
        while (insertIndex !== position && position > insertIndex) {
            arr[position] = arr[position-1];
            position--;
        };
        arr[insertIndex] = value;
    }  
    return arr;
}

// 利用二分查找找到要插入的位置
function searchInsert(nums, target) {
    let left = 0, right = nums.length - 1;

    while (left <= right) {
        let mid = Math.floor((left + right) / 2);

        if (nums[mid] === target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1; 
        } else {
            right = mid -1;
        };
    };
    return right + 1;
}

// test
const arr = [2,7,4,3,8,9,10,1,5,2,3];
insertSortA(arr);   // [1, 2, 2, 3, 3, 4, 5, 7, 8, 9, 10]

归并排序

算法步骤

  • 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
  • 设两个指针，最初位置为两个已经排好序序列的起始位置
  • 比较两个指针所指向的元素，选择相对较小的元素放入合并空间，并移动指针
  • 重复步骤3直到指针到达末尾
  • 将另一序列剩下的元素直接合并到序列尾部

算法实现

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
function mergeSort(arr) {
    if (arr.length === 1) return arr;   // 只有一个元素不用比较了
    
    // 找到中点分隔数组
    let mid = Math.floor(arr.length / 2);
    let left = arr.slice(0, mid);
    let right = arr.slice(mid);
    
    return merge(mergeSort(left), mergeSort(right));
}

// 合并
function merge(left, right) {
    // 给合并数组分配空间
    let res = [];
    
    // 判断指针指向元素的大小，把小的放入res数组中
    while (left.length && right.length) {
        if (left[0] < right[0]) {
            res.push(left.shift())
        } else {
            res.push(right.shift())
        }
    }
    // 判断是否有元素剩余
    res = left.length ? [...res, ...left] : [...res, ...right];
    return res;
}

// test
const arr = [2,7,4,3,8,9,10,1,5,2,3];
mergeSort(arr);   // [1, 2, 2, 3, 3, 4, 5, 7, 8, 9, 10]

/*
	复杂度分析：
		时间复杂度： O(nlogn)
		空间复杂度： O(n)
		
	稳定性分析：归并排序并没有破坏相对位置
		稳定
*/

快速排序

算法思路

  • 找到一个元素，作为基准
  • 剩余元素重新排序，比基准小的放在左边，比基准大的放在右边
  • 递归左边和右边，得到结果

算法实现

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 quickSort(arr) {
    // 设置递归终止条件 arr只有一个元素或者没有元素 直接返回arr
    if (arr.length <= 1) return arr;
    
    // 找到基准点
    let mid = Math.floor(arr.length - 1);
    let pivot = arr[mid];
    arr.splice(mid, 1);  // 从数组中删除基准
    
    // 分配空间用于存放比基准大和小的元素
    let left = [], right = [];
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] < pivot) {
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        };
    };
    
    // 返回结果为 左 + 基准 + 右
    // 左和右还要递归
    return [...quickSort(left), pivot, ...quickSort(right)];
};

// test
const arr = [2,7,4,3,8,9,10,1,5,2,3];
mergeSort(arr);   // [1, 2, 2, 3, 3, 4, 5, 7, 8, 9, 10]

/*
	复杂度分析：
		时间复杂度： O(nlogn)
		空间复杂度： O(logn)
		
	稳定性分析：快速排序一直在打乱相对位置
		不稳定
*/

堆排序

算法思路

  • 构造大顶堆，把堆顶元素和最后一个元素交换（相当于把最大的元素放在最后面了），堆大小减去1
  • 交换后，把剩余的元素继续构造大顶堆，即把剩余元素最大的元素选出来放在堆顶，重复步骤1
  • 继续重复步骤1和2，直至堆大小为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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
// 实现最大堆的构建
/*
	注意最大堆的特点：所有节点都大于其子节点
*/

var len;
function buildMaxHeap(array) {
     len = array.length;
     for (let i = Math.floor(len / 2); i >= 0; i--) {
         heapify(array, i);
     };
    return array;
}


function heapify(arr, i) {
    let left = 2 * i + 1,    // 如果存在，左子节点index为2 * i + 1
        right = 2 * i + 2,   // 如果存在，右子节点index为2 * i + 2
        largest = i;
    
    if (left < len && arr[left] > arr[largest]) {
        largest = left;
    }
    
    if (right < len && arr[right] > arr[largest]) {
        largest = right;
    }
    
    if (largest !== i) {
        [arr[i], arr[largest]] = [arr[largest], arr[i]];
        heapify(arr, largest);
    }
}


function heapSort(arr) {
    buildMaxHeap(arr);
    
    for (let i = arr.length-1; i>0; i--) {
        [arr[0], arr[i]] = [arr[i], arr[0]];
        len--;
        heapify(arr, 0);
    };
    return arr;
}

// test
const arr = [2,7,4,3,8,9,10,1,5,2,3];
heapSort(arr);   // [1, 2, 2, 3, 3, 4, 5, 7, 8, 9, 10]

/*
	复杂度分析
	时间复杂度： O(nlogn)
*/

参考

十大经典排序算法