Java數(shù)據(jù)結(jié)構(gòu)七大排序怎么使用

這篇“Java數(shù)據(jù)結(jié)構(gòu)七大排序怎么使用”文章的知識點大部分人都不太理解，所以小編給大家總結(jié)了以下內(nèi)容，內(nèi)容詳細，步驟清晰，具有一定的借鑒價值，希望大家閱讀完這篇文章能有所收獲，下面我們一起來看看這篇“Java數(shù)據(jù)結(jié)構(gòu)七大排序怎么使用”文章吧。

一、插入排序

1、直接插入排序

當插入第i(i>=1)個元素時，前面的array[0],array[1],…,array[i-1]已經(jīng)排好序，此時用array[i]與array[i-1],array[i-2],…進行比較，找到插入位置即將array[i]插入，原來位置上的元素順序后移。

數(shù)據(jù)越接近有序，直接插入排序的時間消耗越少。

時間復(fù)雜度：O(N^2)

空間復(fù)雜度O(1)，是一種穩(wěn)定的算法

直接插入排序：

    public static void insertSort(int[] array){
        for (int i = 1; i < array.length; i++) {
            int tmp=array[i];
            int j=i-1;
            for(;j>=0;--j){
                if(array[j]>tmp){
                    array[j+1]=array[j];
                }else{
                    break;
                }
            }
            array[j+1]=tmp;
        }
    }

2、希爾排序

希爾排序法的基本思想是：先選定一個整數(shù)gap，把待排序文件中所有記錄分成gap個組，所有距離為gap的數(shù)分在同一組內(nèi)，并對每一組內(nèi)的數(shù)進行直接插入排序。然后取gap=gap/2，重復(fù)上述分組和排序的工作。當gap=1時，所有數(shù)在一組內(nèi)進行直接插入排序。

• 希爾排序是對直接插入排序的優(yōu)化。 

• 當gap > 1時都是預(yù)排序，目的是讓數(shù)組更接近于有序。當gap == 1時，數(shù)組已經(jīng)接近有序的了，直接插入排序會很快。

• 希爾排序的時間復(fù)雜度不好計算，因為gap的取值方法很多，導(dǎo)致很難去計算。

 希爾排序 ：

public static void shellSort(int[] array){
        int size=array.length;
        //這里定義gap的初始值為數(shù)組長度的一半
        int gap=size/2;
        while(gap>0){
            //間隔為gap的直接插入排序
            for (int i = gap; i < size; i++) {
                int tmp=array[i];
                int j=i-gap;
                for(;j>=0;j-=gap){
                    if(array[j]>tmp){
                        array[j+gap]=array[j];
                    }else{
                        break;
                    }
                }
                array[j+gap]=tmp;
            }
            gap/=2;
        }
    }

二、選擇排序

1、選擇排序

• 在元素集合array[i]--array[n-1]中選擇最小的數(shù)據(jù)元素

• 若它不是這組元素中的第一個，則將它與這組元素中的第一個元素交換

• 在剩余的集合中，重復(fù)上述步驟，直到集合剩余1個元素

時間復(fù)雜度：O(N^2)

空間復(fù)雜度為O(1)，不穩(wěn)定

選擇排序 ：

    //交換
    private static void swap(int[] array,int i,int j){
        int tmp=array[i];
        array[i]=array[j];
        array[j]=tmp;
    }
    //選擇排序
    public static void chooseSort(int[] array){
        for (int i = 0; i < array.length; i++) {
            int minIndex=i;//記錄最小值的下標
            for (int j = i+1; j < array.length; j++) {
                if (array[j]<array[minIndex]) {
                    minIndex=j;
                }
            }
            swap(array,i,minIndex);
        }
    }

2、堆排序

堆排序的兩種思路（以升序為例）：

• 創(chuàng)建小根堆，依次取出堆頂元素放入數(shù)組中，直到堆為空

• 創(chuàng)建大根堆，定義堆的尾元素位置key，每次交換堆頂元素和key位置的元素（key--），直到key到堆頂，此時將堆中元素層序遍歷即為升序（如下）

時間復(fù)雜度：O(N^2)

空間復(fù)雜度：O(N)，不穩(wěn)定

堆排序：

    //向下調(diào)整
    public static void shiftDown(int[] array,int parent,int len){
        int child=parent*2+1;
        while(child<len){
            if(child+1<len){
                if(array[child+1]>array[child]){
                    child++;
                }
            }
            if(array[child]>array[parent]){
                swap(array,child,parent);
                parent=child;
                child=parent*2+1;
            }else{
                break;
            }
 
        }
    }
    //創(chuàng)建大根堆
    private static void createHeap(int[] array){
        for (int parent = (array.length-1-1)/2; parent >=0; parent--) {
            shiftDown(array,parent,array.length);
        }
    }
    //堆排序
    public static void heapSort(int[] array){
        //創(chuàng)建大根堆
        createHeap(array);
        //排序
        for (int i = array.length-1; i >0; i--) {
            swap(array,0,i);
            shiftDown(array,0,i);
        }
    }

三、交換排序

1、冒泡排序

兩層循環(huán)，第一層循環(huán)表示要排序的趟數(shù)，第二層循環(huán)表示每趟要比較的次數(shù)；這里的冒泡排序做了優(yōu)化，在每一趟比較時，我們可以定義一個計數(shù)器來記錄數(shù)據(jù)交換的次數(shù)，如果沒有交換，則表示數(shù)據(jù)已經(jīng)有序，不需要再進行排序了。

時間復(fù)雜度：O(N^2)

空間復(fù)雜度為O(1),是一個穩(wěn)定的排序

冒泡排序：

   public static void bubbleSort(int[] array){
        for(int i=0;i<array.length-1;++i){
            int count=0;
            for (int j = 0; j < array.length-1-i; j++) {
                if(array[j]>array[j+1]){
                    swap(array,j,j+1);
                    count++;
                }
            }
            if(count==0){
                break;
            }
        }
    }

2、快速排序

任取待排序元素序列中的某元素作為基準值，按照該排序碼將待排序集合分割成兩子序列，左子序列中所有元素均小于基準值，右子序列中所有元素均大于基準值，然后最左右子序列重復(fù)該過程，直到所有元素都排列在相應(yīng)位置上為止。

時間復(fù)雜度：最好O(n*logn):每次可以盡量將待排序的序列均勻分割

                     最壞O(N^2)：待排序序列本身是有序的

空間復(fù)雜度：最好O(logn)、  最壞O(N)。不穩(wěn)定的排序

（1）挖坑法

當數(shù)據(jù)有序時，快速排序就相當于二叉樹沒有左子樹或右子樹，此時空間復(fù)雜度會達到O(N)，如果大量數(shù)據(jù)進行排序，可能會導(dǎo)致棧溢出。

public static void quickSort(int[] array,int left,int right){
        if(left>=right){
            return;
        }
        int l=left;
        int r=right;
        int tmp=array[l];
        while(l<r){
            while(array[r]>=tmp&&l<r){
            //等號不能省略，如果省略，當序列中存在相同的值時，程序會死循環(huán)
                r--;
            }
            array[l]=array[r];
            while(array[l]<=tmp&&l<r){
                l++;
            }
            array[r]=array[l];
        }
        array[l]=tmp;
        quickSort(array,0,l-1);
        quickSort(array,l+1,right);
    }

（2）快速排序的優(yōu)化

三數(shù)取中法選key

關(guān)于key值的選取，如果待排序序列是有序的，那么我們選取第一個或最后一個作為key可能導(dǎo)致分割的左邊或右邊為空，這時快速排序的空間復(fù)雜度會比較大，容易造成棧溢出。那么我們可以采用三數(shù)取中法來取消這種情況。找到序列的第一個，最后一個，以及中間的一個元素，以他們的中間值作為key值。

 //key值的優(yōu)化，只在快速排序中使用，則可以為private
    private int threeMid(int[] array,int left,int right){
        int mid=(left+right)/2;
        if(array[left]>array[right]){
            if(array[mid]>array[left]){
                return left;
            }
            return array[mid]<array[right]?right:mid;
        }else{
            if(array[mid]<array[left]){
                return left;
            }
            return array[mid]>array[right]?right:mid;
        }
    }

遞歸到小的子區(qū)間時，可以考慮用插入排序

隨著我們遞歸的進行，區(qū)間會變的越來越小，我們可以在區(qū)間小到一個值的時候，對其進行插入排序，這樣代碼的效率會提高很多。

（3）快速排序的非遞歸實現(xiàn)

 //找到一次劃分的下標
    public static int patition(int[] array,int left,int right){
        int tmp=array[left];
        while(left<right){
            while(left<right&&array[right]>=tmp){
                right--;
            }
            array[left]=array[right];
            while(left<right&&array[left]<=tmp){
                left++;
            }
            array[right]=array[left];
        }
        array[left]=tmp;
        return left;
    }
    //快速排序的非遞歸
    public static void quickSort2(int[] array){
        Stack<Integer> stack=new Stack<>();
        int left=0;
        int right=array.length-1;
        stack.push(left);
        stack.push(right);
        while(!stack.isEmpty()){
            int r=stack.pop();
            int l=stack.pop();
            int p=patition(array,l,r);
            if(p-1>l){
                stack.push(l);
                stack.push(p-1);
            }
            if(p+1<r){
                stack.push(p+1);
                stack.push(r);
            }
        }
    }

四、歸并排序

歸并排序（MERGE-SORT）：該算法是采用分治法（Divide and Conquer）的一個非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為二路歸并。

時間復(fù)雜度：O(n*logN)（無論有序還是無序）

空間復(fù)雜度：O（N）。是穩(wěn)定的排序。

    //歸并排序：遞歸
    public static void mergeSort(int[] array,int left,int right){
        if(left>=right){
            return;
        }
        int mid=(left+right)/2;
        //遞歸分割
        mergeSort(array,left,mid);
        mergeSort(array,mid+1,right);
        //合并
        merge(array,left,right，mid);
    }
    //非遞歸
    public static void mergeSort1(int[] array){
        int gap=1;
        while(gap<array.length){
            for (int i = 0; i < array.length; i+=2*gap) {
                int left=i;
                int mid=left+gap-1;
                if(mid>=array.length){
                    mid=array.length-1;
                }
                int right=left+2*gap-1;
                if(right>=array.length){
                    right=array.length-1;
                }
                merge(array,left,right,mid);
            }
            gap=gap*2;
        }
    } 
    //合并：合并兩個有序數(shù)組
    public static void merge(int[] array,int left,int right，int mid){
        int[] tmp=new int[right-left+1];
        int k=0;
        int s1=left;
        int e1=mid;
        int s2=mid+1;
        int e2=right;
        while(s1<=e1&&s2<=e2){
            if(array[s1]<=array[s2]){
                tmp[k++]=array[s1++];
            }else{
                tmp[k++]=array[s2++];
            }
        }
        while(s1<=e1){
            tmp[k++]=array[s1++];
        }
        while(s2<=e2){
            tmp[k++]=array[s2++];
        }
        for (int i = left; i <= right; i++) {
            array[i]=tmp[i-left];
        }
    }

五、排序算法的分析

以上就是關(guān)于“Java數(shù)據(jù)結(jié)構(gòu)七大排序怎么使用”這篇文章的內(nèi)容，相信大家都有了一定的了解，希望小編分享的內(nèi)容對大家有幫助，若想了解更多相關(guān)的知識內(nèi)容，請關(guān)注億速云行業(yè)資訊頻道。