快速排序



概念

有一个无序的数字数组, 从中选取一个元素作为基准值, 依次取其他元素与基准值进行比较, 比基准值小则放在左边, 反之发在右边, 然后从两侧再次选取基准值重复这个过程

实现

function quickSort(arr, left, right) {
    var len = arr.length,
        partitionIndex,
        left = typeof left != 'number' ? 0 : left,
        right = typeof right != 'number' ? len - 1 : right;

    if (left < right) {
        partitionIndex = partition(arr, left, right);
        quickSort(arr, left, partitionIndex - 1);
        quickSort(arr, partitionIndex + 1, right);
    }
    return arr;
}

function partition(arr, left ,right) {     // 分区操作
    var pivot = left,                      // 设定基准值（pivot）
        index = pivot + 1;
    for (var i = index; i <= right; i ++) {
        if (arr[i] < arr[pivot]) {
            swap(arr, i, index);
            index ++;
        }        
    }
    swap(arr, pivot, index - 1);
    return index - 1;
}

function swap(arr, i, j) {
  var temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

function partition2(arr, low, high) {
  let pivot = arr[low];
  while (low < high) {
    while (low < high && arr[high] > pivot) {
      -- high;
    }
    arr[low] = arr[high];
    while (low < high && arr[low] <= pivot) {
      ++ low;
    }
    arr[high] = arr[low];
  }
  arr[low] = pivot;
  return low;
}

function quickSort2(arr, low, high) {
  if (low < high) {
    let pivot = partition2(arr, low, high);
    quickSort2(arr, low, pivot - 1);
    quickSort2(arr, pivot + 1, high);
  }
  return arr;
}

复杂度

空间复杂度: O(logn)

平均时间复杂度: O(nlogn)

最好情况: O(nlogn)

最坏情况: O(n^2)