正文

请到「今天看啥」查看全文

] = nums [ j - 1 ];

j --;

}

nums [ j ] = temp ;

}

}

快速排序

选择一个元素作为基数（通常是第一个元素），把比基数小的元素放到它左边，比基数大的元素放到它右边（相当于二分），再不断递归基数左右两边的序列。

最好： O ( n * logn ) ，所有数均匀分布在基数的两边，此时的递归就是不断地二分左右序列。
最坏： O ( n ²) ，所有数都分布在基数的一边，此时划分左右序列就相当于是插入排序。
平均： O ( n * logn )

参考学习链接：
算法 3：最常用的排序——快速排序
三种快速排序以及快速排序的优化

快速排序之填坑

从右边向中间推进的时候，遇到小于基数的数就赋给左边（一开始是基数的位置），右边保留原先的值等之后被左边的值填上。

function quickSort(nums) {
  // 递归排序基数左右两边的序列
  function recursive(arr, left, right) {
    if(left >= right)  return;
    let index = partition(arr, left, right);
    recursive(arr, left, index - 1);
    recursive(arr, index + 1, right);
    return arr;
  }
  // 将小于基数的数放到基数左边，大于基数的数放到基数右边，并返回基数的位置
  function partition(arr, left, right) {
    // 取第一个数为基数
    let temp = arr[left];
    while(left < right) {
      while(left < right && arr[right] >= temp)  right--;
      arr[left] = arr[right];
      while(left < right && arr[left] < temp)  left++;
      arr[right] = arr[left];
    }
    // 修改基数的位置
    arr[left] = temp;
    return left;
  }
  recursive(nums, 0, nums.length-1);
}

快速排序之交换

从左右两边向中间推进的时候，遇到不符合的数就两边交换值。

function quickSort1(nums) {
  function recursive(arr, left, right) {
    if(left >= right)  return;
    let index = partition(arr, left, right);
    recursive(arr, left, index - 1);
    recursive(arr, index + 1, right);
    return arr;
  }
  function partition(arr, left, right) {
    let temp = arr[left];
    let p = left + 1;
    let q = right;
    while(p <= q) {
      while(p <= q && arr[p] < temp)  p++;
      while(p <= q && arr[q] > temp)  q--;
      if(p <= q) {
        [arr[p], arr[q]] = [arr[q], arr[p]];
        // 交换值后两边各向中间推进一位
        p++;
        q--;
      }
    }
    // 修改基数的位置
    [arr[left], arr[q]] = [arr[q], arr[left]];
    return q;
  }
  recursive(nums, 0, nums.length-1);
}

归并排序

递归将数组分为两个序列，有序合并这两个序列。

最好： O ( n * logn )
最坏： O ( n * logn )
平均： O ( n * logn )

参考学习链接：
图解排序算法(四)之归并排序

function mergeSort(nums) {
  // 有序合并两个数组
  function merge(l1, r1, l2, r2) {
    let arr = [];
    let index = 0;
    

请到「今天看啥」查看全文