快排

debug中

let arr = [3,7,2,1];

function quickSort(arr, left, right) {
  if (left >= right) {
    return arr;
  }

  let pivotIndex = partition(arr, left, right);
  quickSort(arr, left, pivotIndex - 1);
  quickSort(arr, pivotIndex + 1, right);

  return arr;
}


function partition(arr, left, right) { // 两件事:1.根据pivot分成两块2.返回pivot索引
    let pivot = arr[left];
    while (left < right) {
      while (left < right && arr[right] >= pivot) { //右边大于等于就忽略 找到比pivot小的值,和pivot相等的值不是比pivot小的值,如果这里是>,则pivot左边可能会有和pivot值相等的数值,而且可能不会和pivot紧挨着. 例如3,2,3,3 经过partition还是3,2,3,3
        right--;
      }
      arr[left] = arr[right];
      while (left < right && arr[left] <= pivot) { //左边小于等于就忽略
        left++;
      }
      arr[right] = arr[left];
    }
    arr[left] = pivot;
    return left;
  }



// 注意是arr.length-1 索引值
quickSort(arr, 0, arr.length-1);

第二版

function quickSort(arr, left = 0, right = arr.length - 1) {
    if(left < right) {
        let pivotIndex = partition(arr, left, right);
        quickSort(arr, left, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, right);
    }
    // 当left>right或left=right时，不需要操作 在快排过程中的quickSort返回的部分排序的arr没有用处，所以不会存储。也不会对最终返回的完成排序的arr造成影响
    // 最外层的总的quickSort返回的arr是最终排完序的arr
    return arr;
}

function partition(arr, left, right) {
    let pivot = arr[left];
    while(left < right) {
        while (left < right && arr[right] >= pivot) {
            right--;
        }
        arr[left] = arr[right];
        while (left < right && arr[left] <= pivot) {
            left++;
        }
        arr[right] = arr[left];
    }
    arr[left] = pivot;

    return left;
}

let arr = [2,3,34,1,312,3]

quickSort(arr);