2018-03-01快速排序

作者: 天驱丶 | 来源:发表于2018-03-01 02:11 被阅读14次

    学习分而治之(divide and conquer, D&C)——快速排序

    书中先讲了一个小案例,如果将一块长方形土地均匀分成方块,且分出的方块要尽可能大

    两个要点:

    • 找出基线条件,这种条件必须尽可能简单
    • 不断将问题分解,直到符合基线条件(递归条件

    案例分析
    基线条件:一条边是另一条边的整数倍
    递归条件:长边整除短边划出区域,剩余区域继续调用基线条件和递归条件

    答案:1680 * 640的土地,按短边整数倍长分出2640640的区域,剩余区域为640400; 第二步分出240240区域,剩余区域为240160;第三步分出160160区域,剩余区域为160*80;因为160为80整数倍,所以可均匀分出的方块边长为80

    ps: 该结论可搜索欧几里得算法

    快速排序
    • 对于[]或者[1]这类数组,是不需要排序的,这是快速排序的基线条件

    对于[33, 15, 10]这种数组应该怎么做呢?
    首先,从数组种选择一个元素,这个元素被称为基准值(pivot)
    然后根据剩余元素对比基准值,可分成小于基准值的数组和大于基准值的数组(递归条件)
    最后,将两个数组再用此方法排序,直到满足基线条件,将两个数组和基准值相结合
    得到[15, 10], 33, []
    再将[15, 10]做排序得[10], 15, []
    相结合得[10, 15, 33]

    案例分析
    基线条件:数组长度小于2
    递归条件:选择其中一个元素作为基准值,与剩余元素比对,分割成小于和大于两个数组

    答案(js版本):

    function qsort(arr) {
      if (!(arr instanceof Array)) throw new Error('arr is not a Array');
      if (arr.length < 2) return arr;
      var pivot = arr[0];
      var less = [];
      var greater = [];
      for (i = 1; i < arr.length; i++) {
        if (arr[i] < pivot) less.push(arr[i]);
        else greater.push(arr[i])
      }
      return qsort(less).concat([pivot]).concat(qsort(greater));
    }
    

    更新

    快速排序最坏情况时间复杂度为O(n^2)
    当基准值为第一个元素时,输入一个有序数组,其调用栈数为O(n),每次调用栈时间为O(n),其时间复杂度为O(n) * O(n) = O(n ^ 2)

    改良

    function qsort(arr) {
      if (!(arr instanceof Array)) throw new Error('arr is not a Array');
      if (arr.length < 2) return arr;
      var index = Math.floor(arr.length / 2);
      var pivot = arr[index]; // 基准值取中间元素
      var less = [];
      var greater = [];
      for (i = 0; i < arr.length; i++) {
        if (i === index) continue;
        if (arr[i] < pivot) less.push(arr[i]);
        else greater.push(arr[i])
      }
      return qsort(less).concat([pivot]).concat(qsort(greater));
    }
    

    更新 03-04

    改良v2
    对于有重复数据的数组,快排也对这部分数据进行了排序,其实这是没有必要的

    function qsort(arr) {
      if (!(arr instanceof Array)) throw new Error('arr is not a Array');
      if (arr.length < 2) return arr;
      var index = Math.floor(arr.length / 2);
      var pivot = arr[index]; // 基准值取中间元素
      var less = [];
      var greater = [];
      var equal = [];
      for (i = 0; i < arr.length; i++) {
        if (i === index) continue;
        var item = arr[i];
        if (arr[i] < pivot) less.push(item);
        else if (arr[i] > pivot) greater.push(item);
        else equal.push(item)
      }
      return qsort(less).concat(equal).concat([pivot]).concat(qsort(greater));
    }
    

    相关文章

      网友评论

        本文标题:2018-03-01快速排序

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