桶排序快但是内存消耗大
冒泡排序节省内存但是排序速度慢
今天主角是 快速排序,快速排序和前面两种算法比较既不浪费空间又可以快一点排序。快速排序也是使用最广泛的排序算法

快速排序

Comparison Sorting Visualization 点击链接 点Quick Sort 按钮
快排,理解起来比较“麻烦”点, 见图示

  1. 随便找个数作为基数 图为7
  2. 从两边开始找,左边负责找比基数大的数,找到停止,右边找到比基数小的数停止
  3. 把两个找到的数交换位置,重复2 直到左右相遇
  4. 这时候,基数归位,这时候数列分成两个数列,左边比基数小,右边比基数大。
  5. 分别在两个数列重复1-4

在排序算法中遇到了“二分”这个思想,二分会在以后的学习中遇到。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function quicksort(arr) {
//if array is empty
if (arr.length === 0) { return [] }
var left = [];
var right = [];
var pivot = arr[0];
//go through each element in array
for (var i = 1; 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. 推荐一本书讲算法的生动有趣《 啊哈!算法 》我开始学习算法就是在这本书开始的,这本书算法的描述是c语言 。如果对c语言有遗忘推荐作者的另一本书《 啊哈C!思考快你一步
  2. 又一个排序算法可视化的网站
  3. 快速排序(Quicksort)的Javascript实现
  4. Understanding Quicksort, and taking advantage of JS’s native implementation - AntJanus