快速排序

作者: 尤格萨隆 | 来源:发表于2019-07-30 23:08 被阅读0次
    • 快速排序(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]中。

    相关文章

      网友评论

        本文标题:快速排序

        本文链接:https://www.haomeiwen.com/subject/opaorctx.html