排序算法(2)—归并排序,快速排序
in 数据结构 with 0 comment

排序算法(2)—归并排序,快速排序

in 数据结构 with 0 comment

一.归并排序

分治思想
思想:将两个有序的数组归并成一个有序数组。

原地归并的抽象方法

(下面两种归并方法用到):
创建一个适当大小的数组,然后将两个有序数组一个个有序的放入所创建的数组中(在此造成了额外的空间存储问题)。

方法签名:merge(array,lo,hi),将子数组a[lo...mid],a[mid+1...hi]归并,并将结果放入大a[lo...hi].

原地归并的抽象方法:

    private static int[] aux ;
    
    public static void mergeSort(int[] a, int lo, int mid, int hi){
        int i = lo,j = mid+1;
        for(int k = 0; k<=hi; k++)
            aux[k] = a[k] ;
        for(int k = lo; k<=hi; k++)
            if(i>mid)    
                a[k] = aux[j++];
            else if(j>hi)    
                a[k] = aux[i++];
            else if(a[j]<a[i])
                a[k] = aux[j++];
            else    
                a[k] = aux[i++];
    }

自顶向下的归并排序

此类排序使用标准的递归方式进行

实现如下:

    //消除输入依赖
    public static void sort(int[] arr)
    {
        aux = new int[arr.length];  创建的额外数组存储新的排序好的数组
        sort(arr, 0, arr.length-1);
    }
    
    private static void sort(int[] a, int lo, int hi)
    {
        if(hi<=lo)    return;
        int mid = lo+(hi-lo)/2;
        
        sort(a,lo,mid);
        sort(a,mid+1,hi);
        
        mergeSort(a,lo,mid,hi);  //调用原始归并的抽象方法
    }

复杂度

时间复杂度:NlogN
空间复杂度:N
对于长度为N的任意数组,需要1/2NlgN到NlgN次比较。
最多需要访问数组6NlgN次。

自底向上的归并排序

思想:先归并微型数组,然后再归并得到的子数组。(翻倍归并)

实现如下:

        public static void sortBU(int[] arr)
        {
        int N = arr.length;
        aux = new int[arr.length];
        for(int size = 1; size < N; size = size+size)
            for(int lo = 0; lo<N-size; lo += size+size)
                mergeSort(arr, lo, lo+size-1, 
                        Math.min(lo+size+size-1, N-1));        
        }  //最后一个子数组的大小,只有在数组大小是size的偶数倍的时候才会等于size(否则它会比size小).
    

复杂度

时间复杂度:NlogN
空间复杂度:N
对于长度为N的任意数组,需要比较次数和访问数组次数与自顶向下相同。

二.快速排序

运用最为广泛的排序算法
同样是分治算法思想
思想:

根据切分元素,把数组分为两部分,左边小于(大于)切分元素,右边大于(小于)切分元素。

实现如下:

    private static void quickSort(int[] a, int lo,int hi)
    {
        if(lo>=hi) return;
        //partition()是切分方法
        int j = partition(a,lo,hi);
        quickSort(a,lo,j-1);
        quickSort(a,j+1,hi);        
    }

根据切分方法,可以将快速排序分为两类:

常规的切分    and   三向切分

1. 常规切分

    private static int partition(int[] a,int lo, int hi)
    {
        int i = lo,j = hi+1;
        int v = a[lo];
        while(true)
        {
            while(a[++i]<v)
                if(i == hi) break;
            while(v<a[--j]) 
                if(j == lo) break;
            if(i>=j) break;
            exch(a,i,j);
        }
        exch(a,lo,j);
        return j;
    }

复杂度:

时间复杂度:NlgN
空间复杂度:lgN
对于长度为N的**无重复**数组排序,平均需要~2NlnN次比较,一级1/6的交换。
最多需要N^2次比较,但那时可以用随机打乱数组来防止这种最坏情况。

2. 三向切分

常规切分的改进
对于存在大量相同数据的排序尤为有效快速
实现:

    private static void quick3waySort(int[] a, int lo, int hi){
        if(hi<=lo)
            return;
        int lt = lo,i = lo+1, gt = hi;
        int v = a[lo];
        while(i<=gt)
        {
            int flag = a[i] - v;
            //下面判断决定由小到大.
            if(flag<0)
                exch(a,lt++,i++);  //交换a[lt]和a[i]位置.
            else if(flag>0)
                exch(a,i,gt--);
            else
                i++;
        }
        quick3waySort(a, lo, lt-1);
        quick3waySort(a, gt+1, hi);
    }

复杂度:

时间复杂度:N~NlogN
空间复杂度:lgN
对于大小为N的数组,需要~(2ln2)NH次比较。H为由主键值出现频率定义的香农信息量。
它是对于包含大量重复数据的最优排序算法。

归并算法和快速算法比较

快速排序特点:原地排序,只需要一个很小的辅助栈,空间复杂度仅为lgN。
但是相对于归并排序此类的稳定排序,要更注意避免低劣性能的产生,经常会导致在实际运用中性能只有平方级别。

参照算法第四版


内容原创,转载请注明出处
Responses