快速排序

• 快速排序（Quicksort）是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。
• 它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
  简单的说，就是：

1. 先从数列中取出一个数作为基准数
2. 所有小于基准数的元素，都移到基准数的左边；所有大于基准数的元素，都移到基准数的右边。
3. 对基准数左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。

function quickSort(arr,l,r){
  if(l < r){
    var i = l, 
        j = r,    //  左右两边分别设置两个指针
        x = arr[i];  //  用x记住第一个数
    while (i < j) {
      while (i < j && arr[j] > x)
        j--;  //  如果右面的指针比基准数大，指针左移，否则指针停止移动，此时指针所指数值比关键字小
      if (i < j)
        arr[i++] = arr[j];  //  将上面筛选出的比基准数小的数放到前面，指针右移
      while(i < j && arr[i]<x)
        i++;  //  如果左面的指针比基准数小，指针右移，否则指针停止移动，此时指针所指数值比关键字大
      if (i < j)
        arr[j--] = arr[i];  //  将上面筛选出的比基准数大的数放到后面，指针左移
    }
    arr[i] = x;  //  基准数放在正确位置
    quickSort(arr, l, i-1);
    quickSort(arr, i+1, r);
  }
}

总结

1. i = l; j = r; 将基准数挖出形成第一个坑a[i]。
2. j--由后向前找比它小的数，找到后挖出此数填前一个坑a[i]中。
3. i++由前向后找比它大的数，找到后也挖出此数填到前一个坑a[j]中。
4. 再重复执行2，3二步，直到 i == j，将基准数填入a[i]中。