- 快速排序(Quicksort)是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。
- 它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
简单的说,就是:
- 先从数列中取出一个数作为基准数
- 所有小于基准数的元素,都移到基准数的左边;所有大于基准数的元素,都移到基准数的右边。
- 对基准数左边和右边的两个子集,不断重复第一步和第二步,直到所有子集只剩下一个元素为止。
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);
}
}
总结
- i = l; j = r; 将基准数挖出形成第一个坑a[i]。
- j--由后向前找比它小的数,找到后挖出此数填前一个坑a[i]中。
- i++由前向后找比它大的数,找到后也挖出此数填到前一个坑a[j]中。
- 再重复执行2,3二步,直到 i == j,将基准数填入a[i]中。
网友评论