快速排序算法浅析

    xiaoxiao2021-03-25  17

    一、思想

    快速排序,关键在不断切分,而每次切分一个数组的过程是,

    以最左侧元素a为基准,数组为从lo下标到hi下标

    i初始值为lo  ,j初始值为hi + 1

    从最左侧元素+1开始和最左侧元素a比较,如果大于a,且计数i小于最右侧hi,则向下走,否则一直循环

    最右侧元素和a比较,如果小于a,且计数j大于最左侧ho,则向下走,否则一直循环

    如果i大于等于j的情况,则跳出整个大循环,

    否则,进行交换下标 为i  和 下标为j的元素

    如果跳出大循环,则将首元素和下标为j的元素交换,并返回切分元素j

    下次切分从  lo  j-1    j+1 和 hi开始

    ===============================================================================================

    切分程序描述

    i  = lo,j = hi + 1;

    while

    {

    找到左侧大于首元素的值

       while  如果满足while条件,则一直循环,不满足则找到

    找到右侧小于首元素的值   

    while  如果满足while条件按,则一直循环,不满足则找到

    交换 左右两侧的值

    exch

    }

    交换首元素和我们定位到的j元素

    exch

    返回j

    =====================================================================================================

    真正程序

    a为待排序数组

    sort(a,0,a,length -1)

    private static void sort(Comparable[] a,int lo,int hi)

    {

    int(hi <= lo) return;

    int j = partition(a,lo,hi);

    sort(a,lo,j-1);

    sort(a,j+1,hi)

    }

    private static int partition(Comparable[] a,int lo,int hi)

    {

      int i= lo,j=hi +1;

    Comparable v =a[lo];

    while(true)

    {

    while(less(a[++i],v))  if(i == hi) break;

    while(less(v,a[--j])) if(j == lo) break;

    if(i >= j)break;

    exch(a,i,j);

    }

    exch(a,lo,j);

    return j

    }

    //算法引用  算法第四版

    转载请注明原文地址: https://ju.6miu.com/read-200037.html

    最新回复(0)