美文网首页@IT·互联网程序员
3.一步一步分解快排

3.一步一步分解快排

作者: KaelQ | 来源:发表于2016-08-06 17:23 被阅读325次

    1.原理

    Quick Sort 属于交换排序,是对冒泡算法进行的改造。

    基本原理:分治法和填坑法

    • 分治法:
      1. 首先将问题转化为子问题,取数组的第一个元素key,然后将数组里的所有元素小于key的放在左边,大于key的放在右边。
      • 此时再次重复这个过程,去小于key的元素,取第一个元素key2,然后将数组的所有元素小于key2的放在左边,大于key2的放在右边。
      • 再次重复.......直到全部排序好。
    • 填坑法
      1. 用于数组排序,取第一个元素key,然后将a[0]空出来,然后i=0,j=n。
      2. 设置大循环,保证i<j。
      3. 设置子循环,从后往前找,如果大于key就执行j--。
      4. 设置判定语句,如果小于key,将a[j]的值填入a[i]。
      5. 设置子循环,从前往后找,如果小于key就执行j++。
      6. 设置判定语句,如果大于key,就将a[i]的值填入a[j]。
      7. 大循环结束,将key值填入a[i]。
    • 填坑法第一步,设值,key,i,j



    • 从后往前第一次小循环



    • 从前往后第一次小循环



    • 从后往前第二次小循环



    • 结束大循环,将key值填入a[i]。


    2.java写法

    • 分为两部分:分治递归quicksort和partition方法。
      实现填坑法partition():
    private static int partition(int a[], int i, int j) {
            int key = a[i];//key值
            while (i < j) {
                while (i < j && a[j] > key)// 从右向左小循环
                    j--;
                if (a[j] <= key)//判定填充
                    a[i] = a[j];
                while (i < j && a[i] < key)// 从左向右小循环
                    i++;
                if (a[i] >= key)//判定填充
                    a[j] = a[i];
            }
            a[i] = key;// 把轴元素放在轴所在地位置
            return i;// 返回轴所在的位置
        }
    

    实现递归的quicksort():

    private void quickSort(int data[], int low, int high) {// 递归
            int q;
            if (low < high) {
                q = partition(data, low, high);
                quickSort(data, q + 1, high);//对q左边进行分类
                quickSort(data, low, q - 1);//对q右边进行分类
            }
        }
    

    3.时间复杂度

    • 对于划分成子问题求解的问题,公式为:
      T(n) = a*T(n/b)+f(n)

    • 最好的情况,每次划分都是按照折半划分,快排的a=b=2,f(n)为partition()的规模。公式为:
      T(n) = 2*T(n/2)+f(n)
      例如 3,2,4。
      复杂度为T(n) = O(nlogn)

    • 最坏的情况,每次划分都是:
      T(n) = T(n-1)+T(1)+f(n)
      例如 2,3,4。
      复杂度为T(n) = O(n^2)

    相关文章

      网友评论

        本文标题:3.一步一步分解快排

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