JavaScript实现排序算法(2)——快速排序

1
2
3
4
5
6
(从小到大排序)
1. 设定一个分界值(分界值任意,一般是数列首值,或数列中间值);
2. 将不大于分界值的数置于分界值左边,大于分界值的数置于分界值右边,从而将数列以分界值为分割点,分割为左右两个数列.
3. 对左右两个数列,分别重复上面的步骤.
4. 左、右两个数列各数据排序完成后,整个数列的排序也就完成了

1
2
3, 4, 6, 5, 7, 1, 2

1
2
3
4
3, 4, 6, 5, 7, 1, 2
s  i
   c

1
2
3
4
3, 4, 6, 5, 7, 1, 2
s  i
      c

1
2
3
4
3, 4, 6, 5, 7, 1, 2
s  i
         c

1
2
3
4
3, 4, 6, 5, 7, 1, 2
s  i
            c

1
2
3
4
3, 4, 6, 5, 7, 1, 2
s  i
               c

1
2
3
4
3, 1, 6, 5, 7, 4, 2
s     i
                  c     

1
2
3
3, 1, 2, 5, 7, 4, 6
s        i

1
2
3
2, 1, 3, 5, 7, 4, 6
      s

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
44
45
46
47
48
49
50
51
const arr = [3, 4, 6, 5, 7, 1, 2];

// 交换方法
function swap(arr, i, j) {
  let temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

// 快排主函数
function quickSort(arr, left, right) {
  let len = arr.length,
      l = typeof left === 'number' ? left : 0,
      r = typeof right === 'number' ? right : len - 1;
  if (l < r) {
    // 由分区函数划分完后,获得分界值的索引
    const separator = separate(arr, l, r);
    // 以分界值索引为分割点,分割为两个子数组,递归调用quickSort主函数进行快排
    quickSort(arr, l, separator - 1);
    quickSort(arr, separator + 1, r);
  }
  return arr;
}


/**
 * 分区函数
 * 根据分界值(数组首值),将不大于分界值的数划分到分界值左边,大于分界值的数划分到分界值右边
 * */
function separate(arr, left, right) {
  // separator为分界值索引,设定为待分区数组的首位
  // index为交换位,每交换一次,index+1
  let separator = left,
          index =  left + 1;
  // 缓存分界值
  const separatorValue = arr[separator];
  // 遍历待分区数组(分界值除外)
  for (let c = index; c <= right; c++) {
    // 如果当前值不大于分界值,交换当前值与交换位index值
    if (arr[c] <= separatorValue) {
      swap(arr, c, index);
      // 每交换一次,index+1
      index++;
    }
  }
  // 最后交换分界值和上一个交换位的值(就是最后交换的值),达到不大于分界值的项都在分界值左边
  swap(arr, separator, index - 1);
  // 返回分界值在原数组arr的索引
  return index - 1;
}

1
2
3
5, 3, 4, 6, 4*, 2, 1
p               ↑

1
2
5, 3, 2, 6, 4*, 4, 1