非遞歸的快速排序、歸并排序

本文主要内容：

1.非遞歸的快速排序

2.歸并排序

3.非遞歸的歸并排序

4.簡單的排序總結

5.簡單的排序實驗

- 快速排序

Arrays.sort（基本資料類型的數組）,基本使用快排

優化點：（1）基準值的選擇

（2）做partition過程中是否考慮基準值相等的問題

（3）快排更适合對資料量比較大的場景使用，往往資料量比較小時，使用插入排序

• 如何用非遞歸實作快速排序？

自己使用棧記錄待排序區間的左右邊界（棧）

首先定義一個棧，将數組末尾元素及數組首元素一次放入棧中，當棧不為空時循環繼續，找到基準值，再依次往棧中放入元素。

• 歸并排序[左閉右開]

合并兩個有序數組的過程:首先将數組分為兩個區間然後分别排序，将兩個有序數組合并的過程。

（0）平均切分待排序區間，如果帶排序區間的左右兩個小區間已經有序，則按照合并有序數組的方式，使最終區間有序

（1）先找到中間位置，劃分左右兩個小區間

（2）分治的思想，先排序左右兩個小區間

（3）合并有序數組

時間複雜度：O(n*log(n))

空間複雜度：O(n)[申請一個額外的數組]

穩定性：穩定

優化點：（1）減少搬移的次數

（2）判斷左邊的最大的數與右邊最小的數

應用：Arrays.sort(引用資料類型的排序) 歸并排序

歸并排序是一種最常見的外部排序：不是所有的操作都需要借助記憶體的排序，如果資料量大到記憶體放不下了，用歸并排序來處理

記憶體有256M，現有10G的資料需要排序，怎麼處理？

（1）排序好256M的資料，10G資料可以分成40G的有序小檔案

（2）多路歸并（40路歸并）

歸并排序的非遞歸

• 排序總結

時間複雜度的角度：

（1）O(n^2) 插排/選擇/冒泡

（2）O(n*log(n))堆排/快排/歸并

（3）O(n^1.2) 希爾

空間複雜度的角度：

（1）O（1）：插排/選擇/冒泡/希爾/堆排

（2）O（log（n））：快排

（3）O（n）：歸并

穩定：插排/冒泡/歸并

資料不敏感：選擇/堆排/歸并

分治：快排/歸并 減治：插排/選擇/冒泡/堆排

簡單的排序實驗

代碼示範

public class Solution1 {
    //随機建立一個長度為10的數組
    public static int[] createArray(){
        Random random = new Random(20190829);
        int[] a = new int[10];
        for(int i = 0;i<a.length;i++){
            a[i] = random.nextInt(100);
        }
        return a;
    }
    //列印數組元素
    public static void showArray(int[] array){
        for(int i = 0;i<array.length;i++){
            System.out.print(array[i]+" ");
        }
    }
    //将數組中的兩個下标所代表的元素交換
    public static void swap(int[] array,int a,int b){
        int t = array[a];
        array[a] = array[b];
        array[b] = t;
    }
    public static int partition(int[] array,int left,int right){
        //首先定義基準值為數組最後一個元素
        int indexPartition = array[right];
        //定義low指向數組首元素，定義high指向數組尾元素，當low小于high時循環繼續
        int low = left;
        int high = right;
        while (low<high){
            while (low<high&&array[low]<=indexPartition){
                low++;
            }
            while (low<high&&array[high]>=indexPartition){
                high--;
            }
            //當兩邊都停止時，互相交換
            swap(array,low,high);
        }
        //low或high就為基準值
        swap(array,right,low);
        return low;
    }
    //快速排序非遞歸
    public static void quickSortNDG(int[] array){
        Stack<Integer> stack = new Stack<>();
        stack.push(array.length-1);
        stack.push(0);
        while (!stack.isEmpty()){
            int left = stack.pop();
            int right = stack.pop();
            if(left>right){
                continue;
            }
            int indexPartition = partition(array,left,right);
            //區間為：[left,indexPartition-1][indexPartition+1,right]
            stack.push(indexPartition-1);
            stack.push(left);

            stack.push(right);
            stack.push(indexPartition+1);
        }
    }
    //歸并排序
    public static void mergeSort(int[] array){
        //左閉右開
        mergeSortInternal(array,0,array.length);
    }

    public static void mergeSortInternal(int[] array,int left,int right){
        //數組中隻剩一個元素，或者沒有元素
        if(left+1>=right){
            return;
        }
        //[left,mid)[mid,right)
        int mid = (left+right)/2;
        mergeSortInternal(array,left,mid);
        mergeSortInternal(array,mid,right);
        //合并有序數組
        merge(array,left,mid,right);
    }

    public static void merge(int[] array,int left,int mid,int right){
        int length = right-left;
        int[] extra = new int[length];
        int pLeft = left;
        int pRight = mid;
        int pExtra = 0;
        while (pLeft<mid&&pRight<right) {
            if (array[pLeft] <= array[pRight]){
                extra[pExtra++] = array[pLeft++];
            } else {
                extra[pExtra++] = array[pRight++];
            }
        }
        while (pLeft < mid) {
            extra[pExtra++] = array[pLeft++];
        }
        while (pRight < right) {
            extra[pExtra++] = array[pRight++];
        }
        for (int i = 0; i < length; i++) {
            array[left+i] = extra[i];
        }
    }
    //歸并排序非遞歸
    public static void mergeFDG(int[] array){
        for(int i = 1;i<array.length;i = i*2){
            for(int j = 0;j<array.length;j = j+2*i){
                int low = j;
                int mid = j+i;
                int high = mid+i;
                if(mid>array.length){
                    continue;
                }
                if(high>array.length){
                    high = array.length;
                }
                merge(array,low,mid,high);
            }
        }
    }

    public static void main(String[] args) {
        int[] array = createArray();
        showArray(array);
        System.out.println();
        quickSortNDG(array);
        showArray(array);
        System.out.println();
        System.out.println("================================");
        mergeSort(array);
        showArray(array);
        System.out.println();
        mergeFDG(array);
        showArray(array);
        System.out.println();
    }
}
           

運作結果：

15 92 56 30 7 80 63 72 14 42 
7 14 15 30 42 56 63 72 80 92 
================================
7 14 15 30 42 56 63 72 80 92 
7 14 15 30 42 56 63 72 80 92 
           

//簡單的排序實驗
//需要寫一個接口、實作接口的類、主類
//注意在idea中填入參數
public interface Sorts {
    String name();
    void sort(int[] array);
}

public class insertSort implements Sorts {
    @Override
    public String name() {
        return "直接插入排序";
    }

    @Override
    public void sort(int[] array) {
        for(int i = 0;i<array.length-1;i++){
            //有序：[0,i] 無序：[i+1,array.length-1]
            int key = array[i+1];
            int j = 0;
            for(j = i;j>=0;j--){
                if(key>=array[j]){
                    break;
                }
                array[j+1] = array[j];
            }
            array[j+1] = key;
        }
    }
}

public class selectSort implements Sorts {
    @Override
    public String name() {
        return "選擇排序";
    }

    @Override
    public void sort(int[] array) {
        for(int i = 0;i<array.length;i++){
            //無序：[0,array.length-i) 有序：[array.length-i,array.length)
            int max = 0;
            for(int j = 1;j<array.length-i;j++){
                if(array[max]<array[j]){
                    max = j;
                }
                swap(array,max,array.length-i-1);
            }
        }
    }

    public static void swap(int[] array,int a,int b){
        int temp = array[a];
        array[a] = array[b];
        array[b] = temp;
    }
}

public class Runner {
    private static final Sorts[] sorts = {new insertSort()};
    public static void main(String[] args) {
        if(args.length<2){
            System.out.println("需要指定序列的順序以及資料量的大小");
            return;
        }
        String order = args[0];
        int size = Integer.parseInt(args[1]);
        int[] array;
        if(order.equals("順序")){
            array = buildOrderArray(size);
        }else if(order.equals("逆序")){
            array = buildReverseArray(size);
        }else {
            array = buildRandomArray(size);
        }
        testSort(array);
    }
    public static int[] buildOrderArray(int size){
        int[] array = new int[size];
        for(int i = 0;i<size;i++){
            array[i] = i;
        }
        return array;
    }
    public static int[] buildReverseArray(int size){
        int[] array = new int[size];
        for(int i = size;i>0;i--){
            array[i] = i;
        }
        return array;
    }
    public static int[] buildRandomArray(int size){
        int[] array = new int[size];
        Random random = new Random(20190903);
        for(int i = 0;i<size;i++){
            array[i] = random.nextInt(100);
        }
        return array;
    }
    public static void testSort(int[] origin){
        for(Sorts sort:sorts){
            int[] array = Arrays.copyOf(origin,origin.length);
            long begin = System.nanoTime();
            sort.sort(array);
            long end = System.nanoTime();
            int[] second = Arrays.copyOf(origin,origin.length);
            Arrays.sort(second);
            if(!Arrays.equals(array,second)){
                System.out.println("排序錯誤");
            }
            System.out.printf("%s: 排序消耗的時間是: %.4f 毫秒%n",
                    sort.name(), (end - begin) * 1.0 / 1000 / 1000);
        }
    }
}
           

//直接插入排序的運作結果為：
直接插入排序: 排序消耗的時間是: 0.0085 毫秒
//選擇排序的運作結果為：
選擇排序: 排序消耗的時間是: 0.0165 毫秒