快捷導(dǎo)航

Java綜合整理堆排序?快速排序?歸并排序

更新時(shí)間：2022年01月19日 16:49:55 作者：小寫(xiě)丶H

堆排序是利用堆這種數(shù)據(jù)結(jié)構(gòu)而設(shè)計(jì)的一種排序算法，堆排序是一種選擇排序，它的最壞，最好，平均時(shí)間復(fù)雜度均為O(nlogn)，它也是不穩(wěn)定排序。首先簡(jiǎn)單了解下堆結(jié)構(gòu)

堆排序

時(shí)間復(fù)雜度：0（N*log(N)）
空間復(fù)雜度：0（1）
穩(wěn)定性：不穩(wěn)定

private static void heapSort(int[] arr) {
		//建堆
        crearHeap(arr);
        for (int i = 0; i < arr.length-1; i++) {
            int heapSize=arr.length-i;
            swap(arr,heapSize-1,0);
            heapSize--;
            shiftDown(arr,heapSize,0);
        }
        System.out.println(Arrays.toString(arr));
    }

    private static void crearHeap(int[] arr) {
    	// 從后往前遍歷(右邊非葉子節(jié)點(diǎn)開(kāi)始), 依次進(jìn)行向下調(diào)整
        for (int i = (arr.length-1-1)/2; i >=0 ; i--) {
            shiftDown(arr,arr.length,i);
        }
        
    }
	//向下調(diào)整，形成大堆
    private static void shiftDown(int[] arr, int size, int i) {
        int parent = i;
        int child = parent*2+1;
        while (child<size){
            if (child +1< size && arr[child +1]> arr[child]){
                child=child+1;
            }
            if (arr[child]>arr[parent]){
                swap(arr,child,parent);
            }else {
                break;
            }
            parent=child;
            child=parent*2+1;
        }
    }
	//交換
    private static void swap(int[] arr, int child, int parent) {
        int tmp =arr[child];
        arr[child] =arr[parent];
        arr[parent]=tmp;
    }

快速排序

時(shí)間復(fù)雜度:O(N^ logN) 最壞的時(shí)候O(N^2) 和基準(zhǔn)值密切相關(guān)
空間復(fù)雜度:0(logN) 最壞的時(shí)候O(N)
穩(wěn)定性:不穩(wěn)定

遞歸

private static void quick(int[] arr) {
        quickSortHelper(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }

    private static void quickSortHelper(int[] arr, int left, int right) {
        if (left>=right){
            //區(qū)間只有一個(gè)元素，或者零個(gè)元素
            return;
        }
        int index = partition(arr,left,right);
        quickSortHelper(arr,left,index-1);
        quickSortHelper(arr,index+1,right);
    }

    private static int partition(int[] arr, int left, int right) {
        int i=left;
        int j=right;
        int baseValue=arr[right];
        while (i<j){
            while (i<j && arr[i]<=baseValue){
                i++;
            }
            while (i<j && arr[j]>=baseValue){
                j--;
            }
            if (i<j){
                swap(arr,i,j);
            }
        }
        swap(arr,i,right);
        return i;
    }

    private static void swap(int[] arr, int i, int j) {
        int tmp =arr[i];
        arr[i]=arr[j];
        arr[j]=tmp;
    }

非遞歸

public static void quickSortByLoop(int[] arr) {
        Stack<Integer> stack =new Stack<>();
        stack.push(0);
        stack.push(arr.length-1);
        while (!stack.isEmpty()){
            int right = stack.pop();
            int left = stack.pop();
            if (left>=right){
                continue;
            }
            int index = partition(arr,left,right);
            //右子樹(shù)
            stack.push(index+1);
            stack.push(right);
            //左子樹(shù)
            stack.push(left);
            stack.push(index-1);
        }
        System.out.println(Arrays.toString(arr));
    }

    private static int partition(int[] arr, int left, int right) {
        int baseValue =arr[right];
        int i =left;
        int j =right;
        while (i<j){
            while (i<j && arr[i]<=baseValue){
                i++;
            }
            while (i<j && arr[j]>=baseValue){
                j--;
            }
            if (i<j){
                swap(arr,i,j);
            }
        }
        swap(arr,i,right);
        return i;
    }

    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

歸并排序

時(shí)間復(fù)雜度:O(NlogN)
空間復(fù)雜度:O(N）如果是鏈表，可以為O(1)
穩(wěn)定性:穩(wěn)定

遞歸

public static void mergeSort(int[] arr){
        mergeSortHelper(arr,0,arr.length);
        System.out.println(Arrays.toString(arr));
    }

    private static void mergeSortHelper(int[] arr, int left, int right) {
        if (right-left<=1){
            return;
        }
        int mid = (right+left)/2;

        mergeSortHelper(arr,left,mid);
        mergeSortHelper(arr,mid,right);
        merge(arr,left,mid,right);
    }

    private static void merge(int[] arr, int left, int mid, int right) {
        int cur1 =left;
        int cur2 =mid;
        //兩個(gè)數(shù)組合并后的結(jié)果
        int[] output=new int[right-left];
        int outputIndex=0;

        while (cur1<mid && cur2<right){
            if (arr[cur1]<=arr[cur2]) {
                output[outputIndex++] = arr[cur1++];
            }else {
                output[outputIndex++] = arr[cur2++];
            }
        }
        while (cur1<mid){
            output[outputIndex++] = arr[cur1++];
        }
        while (cur2<right){
            output[outputIndex++] = arr[cur2++];
        }

        for (int i = 0; i < right-left ; i++) {
            arr[left+i] = output[i];
        }
    }

非遞歸

public static void mergeSortByLoop(int[] arr){
        // gap 當(dāng)前每個(gè)組中的元素個(gè)數(shù).
        for (int gap =1;gap<arr.length;gap*=2){
            for (int i = 0; i <arr.length ; i+=2*gap) {
                //相當(dāng)于把兩個(gè)長(zhǎng)度為 gap 的相鄰組進(jìn)行了合并
                int left =i;
                int mid =i+gap;
                int right=i+2*gap;
                if (mid > arr.length){
                    mid =arr.length;
                }
                if (right>arr.length){
                    right=arr.length;
                }
                merge(arr,left,mid,right);
            }
        }
        System.out.println(Arrays.toString(arr));
    }

到此這篇關(guān)于Java綜合整理堆排序快速排序歸并排序的文章就介紹到這了,更多相關(guān)Java 排序算法內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: