重新认识下快速排序

Posted on

简介

自从用上了lodash以后，这些基础的算法都很少碰了，现在重温了一下。快速排序的话核心就是分而治之。

步骤

先把核心的比较部分拆分出来，叫partition:

1
2
3
4
5
6
7
8
9
10
11
12
function partition(arr,left,right){
  let i = left, j, pivot = arr[right];

  for (j = left;j<=right;j++){
    if (arr[j] < pivot){
      swap(arr,i,j);
      i++;
    }
  }
  swap(arr,i,right);
  return i;
}
  1. 设比较值。pivot是随机抽取的比较值，国内多是数组中位数，国外多是最后一个数。
  2. 比较。然后从最左开始循环跟pivot进行比较，如果遇到arr[j]比pivot小的数，就会把它跟arr[i]进行对换(swap是交换函数)，并且进行i++。
  3. 分组。如此一直到j == right的时候，i不一定也会到达right，这个时候可以确保的是i的位置以及i以下的位置的值都是比pivot小的，i+1就是临界墙，所以把i+1返回去进行下一轮比较。
1
2
3
4
5
6
7
8
9
function quicksort(arr,left,right){
  if (left < right){
    partitionIndex = partition(arr,left,right);

    quicksort(arr,left,partitionIndex-1);
    quicksort(arr,partitionIndex+1,right);
  }
  return arr;
}
  1. 递归出口。来到主函数，首先可以知道递归出口是left >= right。
  2. 分而治之。根据partition获得得临界点，我们就可以把数组再分为两部分去进行partition，要注意临界点的数其实已经确定是比左边的都大，比右边的都小，所以它不需要再丢回去比较了。
  3. 最后返回的就是排序完成的数组。