快速排序

快速排序是最效率极高的一种排序方法,正因为它效率高,所以也受到了面试官的青睐,同样成了程序员必会的内容。O(∩_∩)O哈哈~

它的思想是选一个基准,然后把小于基准的值放在左边,大于基准的值放在右边(假设从小到大排序)。然后分别递归左边和右边的部分,当所有的递归完毕后就是已经排好序的结果了。

市面上流传最广的快速排序是阮一峰老师博客中写的,我们这笔直接拿过来记录一下,原文在这里

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var quickSort = function(arr) {
  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));
};

阮一峰老师的快速排序选择的是最中间的元素作为基准,左边和右边的都定义了一个新的数组来接收,最后把数组连接起来。这个快速排序的优点是思路很明确,缺点是因为定义了新的数组所以空间复杂度比较高。那如何降低空间复杂度呢?其实只要操作元数组就可以了,这里给出另一种快速排序的实现:

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
function sort(arr,low,high){
// 用i和j记录下初始的最低位和最高位 temp记录下基准 这里假设是起始位置
var i = low,j = high,temp = arr[i];
while (i < j) {// 如果低位的小于高位的时候那么对立面的值进行交换
while (i < j && temp <= arr[j]) {// 扫描右边 如果右边的的有比temp小的需要交换
j--;
}
// 判断i < j为了避免不需要交换的情况 下同
if (i < j) {// 如果右边的有交换的情况则放在左边的位置
arr[i] = arr[j];
i++;
}
while (i < j && arr[i] < temp) {// 扫描左边 如果左边的的有比temp大的需要交换
i++;
}
if (i < j) {// 如果左边的有交换的情况则放在有边的位置
arr[j] = arr[i];
j--;
}
}
// 上面循环结束的时候i位置左边的都比temp小 右边的都比temp大 这只temp给当前位置
arr[i] = temp;
if (low < i) {
sort(arr,low,i - 1);// 递归遍历左侧
}
if (j < high) {
sort(arr,j + 1,high);// 递归遍历右侧
}
return arr;
}

function quickSort(arr){// 为了给sort传初始值 而封装的一层
return sort(arr,0,arr.length - 1);
}

var arr = [8,3,10,7,5,6,4,2,1,9];
quickSort(arr);
console.log(arr);// [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

这个快速的时间复杂度要比阮一峰老师的稍微低一点,不过比阮一峰老师的快速排序稍微难理解一点。其实我们在《JavaScript数据结构与算法》读书笔记一文中也有快速排序的记录,那个快速排序与这个有一点点的不同,那个排序的基准选择的中间值,然后每次循环直接交换左侧的和右侧的元素,整体思路相差无几,感兴趣的可以在那篇文章中搜一下快速排序。

-------------本文结束 感谢您的阅读-------------
0%