算法练习

排序

这篇是总结各种排序算法

冒泡排序

冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置， 重复 n 次，就完成了 n 个数据的排序工作。


const bubbleSort = (arr) =>{
    if (arr.length <= 1) return;
    for(let i = 0;i < arr.length;i++) {
        let flag = false;
        for(let j = 0;j < arr.length - i - 1;j++) {
            const temp = arr[j];
            arr[j] = arr[j+1];
            a[j+1] = temp;
            flag = true;
        }
    }
    if(!flag) {
        break;
    }
    console.log(arr)
}

插入排序


const insertionSort = (arr) => {
    if(arr.length <= 1) return;
    for(let i = 1; i < arr.length; i++) {
        const temp = arr[i];
        let j = i - 1;

        for(j;j >= 0; j--){
            if(arr[j] > temp) {
                arr[j+1] = arr[j]
            }else {
                break;
            }
        }
        arr[j+1] = temp;
    }
}

选择排序

const selectionSort = (arr) =>{
    if(arr.length <= 1) return;
    for(let i = 0;i < arr.length - 1;i++) {
        let minIdex = i;
        for(let j = 0;j < arr.length;j++) {
            if(arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        const temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}

归并排序


const mergeArr = (left,right) {
    let leftIndex = 0;
    let rightIndex = 0;
    let temp = [];
    while(left.length > leftIndex && right.length > rightIndex) {
        if(left[leftIndex] <= right[rightIndex]){
            temp.push(left[leftIndex])
            leftIndex++;
        }else{
            temp.push(right[rightIndex]);
            rightIndex++;
        }
    }
    //合并比较剩下的数组
    return temp.concat(left.slice(leftIndex).concat(right.slice(rightIndex)))
}

const mergeSort = (arr) => {
    if(arr.length <= 1) return;
    const middle = Math.floor(arr.length/2);
    const left = arr.slice(0,middle);
    const right = arr.slice(middle);
    return mergeArr(mergeSort(left),mergeSort(right));
}

快排


const swap = (arr, i, j) => {
    const temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp
}

const partition = (arr,pivot,left,right) => {
    const pivotVal = arr[pivot];
    let startIndex = left;
    for(let i = left;i < right;i++) {
        if(arr[i] < pivotVal) {
            swap(arr,i,startIndex)
            startIndex++  //小于基准数的数组的索引
        }
    }
    swap(arr,startIndex,pivot)
    return startIndex
}

const quickSort = (arr,left,right) => {
    if (left < right){
        let pivot = right; //基准元素，开始以最右边的元素为基准元素
        let partitionIndex = partition(arr,pivot,left,right);
        quickSort(arr,left,partition - 1 < left ? left : partition - 1);
        quickSort(arr,partition + 1 > right ? right : partitionIndex - 1,right);
    }
    
}
赞 赏