算法-数组排序

[dcharlie123]

冒泡排序

function bubbleSort(arr){
  for(let i = 0; i<arr.length-1;i++){
    for(let j =  0; j<arr.length-i-1;j++){
      if(arr[j]>arr[j+1]){
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
  return arr
}

最好情况：当序列已经有序，每次比较和交换操作都不会进行，只需要进行n-1次比较，时间复杂度为O(n)。
最坏情况：当序列完全逆序，需要进行n-1轮比较和n-1次交换操作，时间复杂度为O(n^2)。
平均情况：需要进行的比较和交换操作的次数在所有情况中的平均值，时间复杂度也是O(n^2)。

选择排序

function selectionSort(arr){
    // i<arr.length-1因为下面j=i+1
    for(let i = 0; i<arr.length-1;i++){
        // 设置当前索引为最小索引
        let minIndex = i
        for(let j = i + 1;j<arr.length;j++){
            if(arr[minIndex]>arr[j]){
                minIndex = j
            }
        }
    }
    if(i!==minIndex){
        [arr[i],arr[minIndex]]=[arr[minIndex],arr[i]]
    }
    return arr
}

选择排序是一种简单易懂的排序算法。

它的基本思想是遍历整个列表，每次找出最小的元素，并且将它移到列表的最左边，重复这个过程直到整个列表都有序排列。

在平均情况下，选择排序的时间复杂度为 O(n^2)，在最坏情况下与最好情况下都为 O(n^2)。

选择排序在数据规模较小时非常适用，在数据规模较大时不够高效。

插入排序

function insertSort(arr){
    for(let i = 1;i<arr.length;i++){
        let j=i-1;
        let temp = arr[i];
        // 与前面部分进行比较
        while(j >= 0 && arr[j] > temp){
            arr[j + 1] = arr[j]
            j--
        }
        arr[j+1]=temp
    }
    return arr;
}

插入排序是一种简单而直观的排序算法，它可以快速地对部分有序的数组进行排序。

插入排序通过比较相邻的元素并在需要时将其交换，来实现从小到大的排列。

插入排序的时间复杂度在最好情况下是线性O(n)，最坏情况下是O(n^2)。

总而言之，如果数组部分有序，插入排序可以比冒泡排序和选择排序更快。

但是如果数组完全逆序，则插入排序的时间复杂度比较高，不如快速排序或归并排序。
因此，在选择排序算法时，应该根据需要选择合适的算法。

归并排序

function mergeSort(arr){
    if(arr.length <= 1){
        return arr
    }
    const mid = Math.floor(arr.length/2)
    const left = arr.slice(0,mid)
    const right = arr.slice(mid)
    return merge(mergeSort(left),mergeSort(right))
}
function merge(left,right){
    const result=[];
    while(left.length && right.length){
        if(left[0]<=right[0]){
            result.push(left.shift())
        }else{
            result.push(right.shift())
        }
    }
    while(left.length){
        result.push(left.shift())
    }
    while(right.length){
        result.push(right.shift())
    }
    return result
}

快速排序

function quickSort(arr){
    if(arr.length <= 1){
        return arr
    }
    const pivotIndex = Math.floor(arr.length/2)
    const pivot = arr.splice(pivotIndex,1)[0];
    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).concat([pivot],quickSort(right))
}

堆排序

参考文章：sisterAn/JavaScript-Algorithms#60

// 建堆
function buildMaxHeap(arr){
    const len = arr.length;
    // Math.floor(len/2) 获取最后一个非叶子节点
    for(let i=Math.floor(len/2);i>=0;i--){
        heapify(arr,i,len);
    }
}

function heapify(arr,i,len){
    let left = 2*i+1;
    let right = 2*i+2;
    let largest = i;
    // 堆其实可以用一个数组表示，给定一个节点的下标 i （i从1开始） ，那么它的父节点一定为 A[i/2] ，左子节点为 A[2i] ，右子节点为 A[2i+1]
    if(left<len && arr[left]>arr[largest]){
        largest = left;
    }
    if(right<len && arr[right]>arr[largest]){
        largest = right;
    }
    if(largest !== i){
        swap(arr,i,largest);
        heapify(arr,largest,len);
    }
}
// 交换
function swap(arr,i,j){
    const temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}
// 排序
function heapSort(arr){
    buildMaxHeap(arr);
    for(let i=arr.length-1;i>0;i--){
        // 第一个排序好放最后
        swap(arr,0,i);
        // 除去最后一个进行堆调整
        heapify(arr,0,i);
    }
    return arr;
}