快速排序

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

function partition(D, low, high) {
  let i; // 小于基准值的下标
  let j; // 大于基准值的下标
  let s; // 基准值的下标
  while (high > low) {
    // 当数组只有 1 个元素时，结束递归
    i = low;
    j = high;
    s = D[low]; // 基准值取原数组的第一个元素
    while (i < j) {
      // 遍历数组全部元素
      while (s <= D[j]) {
        // 从数组尾部开始，寻找小于等于基准值的元素
        j--;
      }
      // 把右边的值放到左边
      D[i] = D[j];
      // 从数组头部开始，寻找大于基准值的元素
      while (s > D[i] && i < j) {
        i++;
      }
      // 把左边的值放到刚才右边的位置，完成“交换”
      D[j] = D[i];
    }
    // 当 i = j 时，此时数组已排序完，把基准值放到结束的位置上
    D[i] = s;
    // 递归左边部分
    partition(D, low, i - 1);
    // 递归右边部分
    low = i + 1;
  }
}

function quicksort(D) {
  partition(D, 0, D.length - 1);
}

// 调用
const a = [1,3,2,4,11,222,66,8,7,6]
quicksort(a);
console.log(a)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

function quickSort(arr) {
    // 当数组只有 1 个元素时，递归结束
    if (arr.length <= 1) { 
      return arr; 
    }
    // 取数组中位数作为基准值，并将其与原数组分离
    var pivotIndex = Math.floor(arr.length / 2);
    var pivot = arr.splice(pivotIndex, 1)[0];
    var left = [];  // 基准的左边：小于基准的元素
    var right = [];  // 基准的右边：大于基准的元素
    for (var 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));
    // return [...quickSort(left), pivot, ...quickSort(right)];
};

const result = quickSort([1,3,2,4,11,222,66,8,7,6])