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

快速排序

快速排序是对冒泡排序的一种改进,被认为是目前最好的一种内部排序方法.

快速排序的核心思想是分治思想,先分再合.

1 算法过程

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

2 排序演示

对下面的数列进行快速排序

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

我们需要设定一个分界值(这里设定数列首值3为分界值s),和两个指针,一个指针(这里叫c)用来遍历数列(除去分界值),另一个指针(这里叫i)用来确定交换位.

排序开始,c指向4,i指向4,比较c和s

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

4大于3,不发生交换,c指针向右移一位,i指针不动

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

6大于3,不发生交换,c指针向右移一位,i指针不动

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

5大于3,不发生交换,c指针向右移一位,i指针不动

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

7大于3,不发生交换,c指针向右移一位,i指针不动

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

1小于3,交换c和i所指向的数值(不是交换指针哈),即交换1和4,i向右移一位(只要发生了交换,i就向右移一位),c向右移一位

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

2小于3,交换c和i所指向的数值,即交换2和6,i向右移一位

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

再交换s和i-1所指向的数值

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

此时,就实现了把数列不大于分界值(3)的数置于分界值左边,大于分界值的数置于分界值右边.

对分界值左右两个数列重复上面的步骤(递归定义),就可以实现数列从小到大的排序.

3 代码实现

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;
}

4 时间复杂度

快速排序的分界值选取是任意的,因此快速排序也带有偶然性,时间复杂度好坏,是由选取的分界值来决定的.

• 最好的情况下,我们每次选取的分界值,都正好是待排数列的中间数,此时可以确保每一次分割都能把数列分为两半,进而只需递归log(n)次,此时,快速排序的时间复杂度为O(nlog(n)).

• 最坏的情况下,我们每次选取的分界值,都正好是待排数列的最小或最大值,此时,快速排序退化成了未优化过的冒泡排序,需要比较n(n-1)/2次,时间复杂度为O(n^2);

• 平均时间复杂度为O(nlog(n)).

5 稳定性

快速排序是不稳定的,可以看个例子:

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

假设5是分界值,[3]比5小的子数列,当前比较值是2

2比5小,交换2与4

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

可以看到 此时4*到了4的前面.

最后

以上就是微笑含羞草为你收集整理的JavaScript实现排序算法(2)——快速排序的全部内容，希望文章能够帮你解决JavaScript实现排序算法(2)——快速排序所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。