JavaScript 实现四种常见排序算法

港控/mmm° 2022-05-25 06:46 154阅读 0赞

介绍4种常见排序算法，将 JavaScript 的实现过程做一个分享：`冒泡排序`、`选择排序`、`插入排序`、`快速排序`。

此处首先定义一个 swap 函数，实现了数组中元素调换的功能，在后面的排序算法都是直接调用这个函数的~

//将数组 arr 中下标为 i 和 j 调换位置
    function swap(arr, i, j) { 
        var temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }

#### 冒泡排序(Bubble Sort) ####

--------------------

基本思路：

1.  比较相邻的元素，如果前一个比后一个大，就把它们两个调换位置。
2.  对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
3.  针对所有的元素重复以上的步骤，除了最后一个。
4.  持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

// 最差时间复杂度 ---- O(n^2)
    // 最优时间复杂度 ---- 如果能在内部循环第一次运行时,使用一个旗标来表示有无需要交换的可能,可以把最优时间复杂度降低到O(n)
    // 平均时间复杂度 ---- O(n^2)
    // 所需辅助空间 ------ O(1)
    // 稳定性 ------------ 稳定
    function sort(arr) { 
        //外循环每次运行都可以将最大的值“起泡”到数组最后
        for(var i = 0; i < arr.length - 1; i++) {
            //内循环 依次比较相邻的两个元素，使较大的那个后移
            for(var j = 0; j < arr.length - 1 - i; j++) {
                if(arr[j] > arr[j + 1]) {   //如果条件改为 arr[j] >= arr[j + 1]，变为不稳定的排序算法
                    swap(arr, j, j + 1);
                }
            }
        }
        return arr;
    }

#### 选择排序(Select Sort) ####

--------------------

基本思路：  
1. 初始时在序列中找到最小（大）元素，放到序列的起始位置作为已排序序列；  
2. 然后，再从剩余未排序元素中继续寻找最小（大）元素，放到已排序序列的末尾；  
3. 以此类推，直到所有元素均排序完毕。

// 最差时间复杂度 ---- O(n^2)
    // 最优时间复杂度 ---- O(n^2)
    // 平均时间复杂度 ---- O(n^2)
    // 所需辅助空间 ------ O(1)
    // 稳定性 ------------ 不稳定
    function sort(arr) { 
        for(var i = 0; i < arr.length; i++) {
            var minIndex = i;
            for(var j = i; j < arr.length - i; j++)
            {
                if(arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            swap(arr, i, minIndex);
        }
        return arr;
    }

#### 插入排序(Insertion Sort) ####

--------------------

基本思路：  
1. 从第一个元素开始，该元素可以认为已经被排序  
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描  
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置  
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置  
5. 将新元素插入到该位置后  
6. 重复步骤2~5

// 最差时间复杂度 ---- 最坏情况为输入序列是降序排列的,此时时间复杂度O(n^2)
    // 最优时间复杂度 ---- 最好情况为输入序列是升序排列的,此时时间复杂度O(n)
    // 平均时间复杂度 ---- O(n^2)
    // 所需辅助空间 ------ O(1)
    // 稳定性 ------------ 稳定
    function sort(arr) { 
        for(var i = 0; i < arr.length; i++) {
            var get = arr[i];
            var j = i - 1;
            while(j >= 0 && arr[j] > get) {
                arr[j + 1] = arr[j];
                j --;
            }
            arr[j + 1] = get;
        }
        return arr;
    }

#### 快速排序(Quick Sort) ####

--------------------

基本思路：

1.  从序列中挑出一个元素，作为”基准”(pivot).
2.  把所有比基准值小的元素放在基准前面，所有比基准值大的元素放在基准的后面（相同的数可以到任一边），这个称为分区(partition)操作。
3.  对每个分区递归地进行步骤1~2，递归的结束条件是序列的大小是0或1，这时整体已经被排好序了。

// 最差时间复杂度 ---- 每次选取的基准都是最大（或最小）的元素，导致每次只划分出了一个分区，需要进行n-1次划分才能结束递归，时间复杂度为O(n^2)
    // 最优时间复杂度 ---- 每次选取的基准都是中位数，这样每次都均匀的划分出两个分区，只需要logn次划分就能结束递归，时间复杂度为O(nlogn)
    // 平均时间复杂度 ---- O(nlogn)
    // 所需辅助空间 ------ 主要是递归造成的栈空间的使用(用来保存left和right等局部变量)，取决于递归树的深度，一般为O(logn)，最差为O(n) 
    // 稳定性 ---------- 不稳定
    
    function partition(arr, left, right) {   //划分函数
        var pivot = arr[right];     //每次基准选数组最后一位
        var tail = left - 1;        
        for(var i = left; i < right; i++) {     //遍历基准外的其他元素
            if(arr[i] < pivot) {    //把小于等于基准的元素放到前一个子数组的末尾
                swap(arr, ++tail, i);
            }
        }
        swap(arr, ++tail, right);   // 最后把基准放到前一个子数组的后边，剩下的子数组既是大于基准的子数组
        return tail;
    }
    
    function sort(arr, left, right) { 
        if(left >= right) return;   //递归终止条件 
    
        //设置left right 初始值
        left = !left ? 0 : left;
        right = !right ? arr.length - 1 : right;        
    
        var pivot_index = partition(arr, left, right);      //取第一次划分函数后的基准Index
    
        sort(arr, left, pivot_index - 1);       //递归运行基准Index前面的数组部分
        sort(arr, pivot_index + 1, right);      //递归运行基准Index后面的数组部分
        return arr;
    }