快速排序的时间复杂度为O(N*logN)。

算法思路

在快速排序中需要有一个Partition函数，这个方法是在数组中选择一个数字，然后把数组中的数字分为两个部分，比选择的数字小的函数移到数组的左边，比选择的数字大的数字移到数组的右边。这个函数的实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function partition(list, start, end){
  var mid = Math.floor((start + end)/2);
  swap(list, mid , end);
  var small = start - 1;
  for(let i = start; i < end; i++) {
    if (list[i] < list[end]){
      small++;
      if(small !== i){
        swap(list, i, small);
      }
    }
  }
  small++;
  swap(list, small, end);
  return small;
}
function swap(list,i,j){
  let tmp=list[i];
  list[i]=list[j];
  list[j]=tmp;
}

算法解释

我来解释一下这个函数。

在数组中选取中间的数，然后从前到后遍历，如果某个数比选定的数小，则交换位置。

一个很重要的变量是small，这个变量是用来统计比listend小的数，当list[i]<list[end]，small加一，然后将所有比list[end]小的数，全都交换到前面去。

最后small的位置存放的是选定的数，在这个数前面的数全是小于它，后面的全部大于它。接下需要的就是使用一个递归函数，对选定数之前的数组和选定数之后的数组再进行排序。

1
2
3
4
5
6
7
8
9
10
11
12
function quickSort(list, start, end){
  if(start === end){
    return;
  }
  var index = partition(list, start, end);
  if (index > start){
    quickSort(list, start, index - 1);
  }
  if (index < end){
    quickSort(list, index + 1, end);
  }
}

partition方法应用

在快速排序中的partition方法能用到的地方很多，比如，在剑指offer的面试题29中：数组中出现次数超过一半的数字。也用到了partition。

剑指offer29题

这道题可以先对数组做一次partition，判断返回的数是否正好在n/2位置，则这个数就是我们要找的数；如果返回的数在大于n/2，则中位数在这个数的左边；如果返回的数在小于n/2，则中位数在这个数的右边。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function moreThanHalfNum(list, length) {
  var start = 0;
  var end = list.length - 1;
  var mid = Math.floor((start + end)/2);
  var index = partition(list, length, start, end);
  while(index !== mid){
    if(index > mid) {
      end = index - 1;
      index = partition(list, length, start, end);
    } else {
      start = index + 1;
      index = partition(list, length, start, end);
    }
  }
  var result = list[mid];
  return result; 
}

剑指offer30题

再比如在剑指offer的面试题30：最小的k个数，也用到了partition。因为在partition中，将小于选定数的数都放在选定数的前面，大于选定数的数都放在选定数的后面，因此这道题要找出最小的k个数，只需要找到partition的返回值index===k-1即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function getLeastNumbers(list,k){
  var start = 0;
  var end = list.length - 1;
  var result=[];
  var index = partition(list, length, start, end);
  while(index !== k - 1) {
    if (index > k - 1){
      end = index - 1;
      index = partition(list, length, start, end);
    } else {
      start = index + 1;
      index = partition(list, length, start, end);
    }
  }
  for(let i=0;i<k;i++){
    result.push(list[i]);
  }
  console.log(result);
}