前端必备排序算法

た入场券 2023-02-12 14:22 20阅读 0赞

\*\*

## 前端必备排序算法 ##

\*\*  
冒泡排序  
时间复杂度：O(n2) 空间复杂度：O(1)

选择排序  
时间复杂度：O(n2) 空间复杂度：O(1)

//思路：第一遍，从数组中选出最小的，与第一个元素进行交换；
    //第二遍，从第二个元素开始，找出最小的，与第二个元素进行交换，以此循环，完成排序。
    const arr = [22,12,4,45,3,87,77,43,55,42];
    function selectionSort() { 
        for(let i = 0 ; i < arr.length ; i++){ 
            let index = i;
            for(let j = i+1 ; j < arr.length ; j++){ 
                if(arr[index] > arr[j]){ 
                    index = j;
                }
            }
            swap(arr,index,i);
        }
        return arr;
    }
    //将目前数组中最小的元素放到第i个位置
    function swap(arr,index,i) { 
        let temp = arr[index];
        arr[index] = arr[i];
        arr[i] = temp;
    }
    console.log(selectionSort(arr));

快速排序  
时间复杂度：O(nlog2n) 空间复杂度：O(nlog2n)

//思路：找到一个基数，然后将比基数小的数放在基数的左边，将比基数大的放在基数的右边。
    //之后进行递归那两组已经归类好的数组
    const arr = [22,12,4,45,3,87,77,43,55,42];
    
    function quickSort(arr) { 
        if(arr.length <= 1){ 
            return arr;
        }
        let temp = arr[0];
        let right = [];
        let left = [];
        for(let i = 1 ; i < arr.length ; i++){ 
            if(arr[i]>temp){ 
                right.push(arr[i]);
            }else{ 
                left.push(arr[i]);
            }
        }
        return quickSort(left).concat([temp],quickSort(right));
    }
    console.log(quickSort(arr));

插入排序  
时间复杂度：O(n2) 空间复杂度：O(1)

//思路：首先，循环原数组，然后将当前位置的元素，插入到之前已排好的数组中，依次操作。
    const arr = [22,12,4,45,3,87,77,43,55,42];
    
    function insertSort(arr) { 
        for(let i = 0 ; i < arr.length ; i++){ 
            let temp = arr[i];
            for(let j = 0 ; j < i ; j++){ 
                if(temp < arr[j] && j === 0){ 
                    arr.splice(i,1);    //从索引为i的位置删除一项。
                    arr.unshift(temp);  //将元素temp增加到数组的开头
                    break;
                }else if(temp > arr[j] && temp < arr[j+1] && j < (i-1)){ 
                    arr.splice(i,1);
                    arr.splice(j+1,0,temp); //在索引为j+1的位置插入temp
                    break;
                }
            }
        }
        return arr;
    }
    
    console.log(insertSort(arr));

希尔排序 归并排序 堆排序  
稳定的排序算法：  
冒泡排序 归并排序 基数排序