Java排序算法實現的方法是什么

這篇文章主要介紹“Java排序算法實現的方法是什么”，在日常操作中，相信很多人在Java排序算法實現的方法是什么問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”Java排序算法實現的方法是什么”的疑惑有所幫助！接下來，請跟著小編一起來學習吧！

冒泡排序：

（1）原理：

• 從第一個數據開始，與第二個數據相比較，如果第二個數據小于第一個數據，則交換兩個數據的位置。

• 指針由第一個數據移向第二個數據，第二個數據與第三個數據相比較，如果第三個數據小于第二個數據，則交換兩個數據的位置。

• 依此類推，完成第一輪排序。第一輪排序結束后，最大的元素被移到了最右面。

• 依照上面的過程進行第二輪排序，將第二大的排在倒數第二的位置。

• 重復上述過程，沒排完一輪，比較次數就減少一次。

（2）例子：

待排序數據：7, 6, 9, 8, 5,1

第一輪排序過程：

指針先指向7，7和6比較，6<7，交換6和7的位置，結果為：6,7,9,8,5,1
指針指向第二個元素7，7和9比較，9>7，不用交換位置，結果仍為：6,7,9,8,5,1
指針指向第三個元素9，比較9和8，8<9，交換8和9的位置，結果為：6,7,8,9,5,1
指針指向第四個元素9，比較9和5，5<9，交換5和9，結果為：6,7,8,5,9,1
指針指向第五個元素9，比較9和1，1<9，交換1和9的位置，結果為6,7,8,5,1,9

第一輪排序結束后，最大的數字9被移到了最右邊。

進行第二輪排序，過程同上，只是由于最大的9已經放在最右邊了，因此不用在比較9了，少了一次比較，第二輪結束的結果為：6,7,5,1,8,9

第三輪結果：6,5,1,7,8,9

第四輪比較結果：5,1,6,7,8,9

第五輪比較結果：1,5,6,7,8,9

最終排序結果為：1,5,6,7,8,9，由上可知N個數據排序，需要進行N-1輪排序；第i輪排序需要的比較次數為N-i次。

（3）編碼思路：

需要兩層循環(huán)，第一層循環(huán)i表示排序的輪數，第二層循環(huán)j表示比較的次數。

（4）代碼實現：

實例

package com.test.insertsort;/**
 * 選擇排序
 * @author Administrator
 * */public class ChooseSort {
    private int[] array;    private int length;    
    public ChooseSort(int[] array){
        this.array = array;        this.length = array.length;    }
    
    /**
     * 打印數組中的所有元素     */
    public void display(){
        for(int i: array){
            System.out.print(i+" ");        }
        System.out.println(); 
    }
    
    /**
     * 選擇排序算法     */
    public void chooseSort(){
        for(int i=0; i<length-1; i++){
            int minIndex = i;            for(int j=minIndex+1;j<length;j++){
                if(array[j]<array[minIndex]){
                    minIndex = j;                }
            }
            int temp = array[i];            array[i] = array[minIndex];            array[minIndex] = temp; 
        }
    }
    
    public static void main(String[] args){
        int[] array={100,45,36,21,17,13,7};        ChooseSort cs = new ChooseSort(array);        System.out.println("排序前的數據為：");        cs.display();        cs.chooseSort();        System.out.println("排序后的數據為：");        cs.display();    }}

（5）選擇排序總結：

• N個元素需要排序N-1輪；

• 第i輪需要比較N-i次；

• N個元素排序，需要比較n（n-1）/2次；

• 選擇排序的算法復雜度仍為O（n*n）；

• 相比于冒泡排序，選擇排序的交換次數大大減少，因此速度要快于冒泡排序

插入排序

插入排序是簡單排序中最快的排序算法，雖然時間復雜度仍然為O(n*n)，但是卻比冒泡排序和選擇排序快很多。

（1）原理：

• 將指針指向某個元素，假設該元素左側的元素全部有序，將該元素抽取出來，然后按照從右往左的順序分別與其左邊的元素比較，遇到比其大的元素便將元素右移，直到找到比該元素小的元素或者找到最左面發(fā)現其左側的元素都比它大，停止；

• 此時會出現一個空位，將該元素放入到空位中，此時該元素左側的元素都比它小，右側的元素都比它大；

• 指針向后移動一位，重復上述過程。每操作一輪，左側有序元素都增加一個，右側無序元素都減少一個。

（2）例子：

待比較數據：7, 6, 9, 8, 5,1

• 第一輪：指針指向第二個元素6，假設6左面的元素為有序的，將6抽離出來，形成7,_,9,8,5,1，從7開始，6和7比較，發(fā)現7>6。將7右移，形成_,7,9,8,5,1，6插入到7前面的空位，結果：6,7,9,8,5,1

• 第二輪：指針指向第三個元素9，此時其左面的元素6,7為有序的，將9抽離出來，形成6,7,_,8,5,1，從7開始，依次與9比較，發(fā)現9左側的元素都比9小，于是無需移動，把9放到空位中，結果仍為：6,7,9,8,5,1

• 第三輪：指針指向第四個元素8，此時其左面的元素6,7,9為有序的，將8抽離出來，形成6,7,9,_,5,1，從9開始，依次與8比較，發(fā)現8<9，將9向后移，形成6,7,_,9,5,1，8插入到空位中，結果為：6,7,8,9,5,1

• 第四輪：指針指向第五個元素5，此時其左面的元素6,7,8,9為有序的，將5抽離出來，形成6,7,8,9,_,1，從9開始依次與5比較，發(fā)現5比其左側所有元素都小，5左側元素全部向右移動，形成_,6,7,8,9,1，將5放入空位，結果5,6,7,8,9,1。

• 第五輪：同上，1被移到最左面，最后結果：1,5,6,7,8,9。

（3）編碼分析：

需要兩層循環(huán)，第一層循環(huán)index表示上述例子中的指針，即遍歷從坐標為1開始的每一個元素；第二層循環(huán)從leftindex=index-1開始，leftindex--向左遍歷，將每一個元素與i處的元素比較，直到j處的元素小于i出的元素或者leftindex<0；遍歷從i到j的每一個元素使其右移，最后將index處的元素放到leftindex處的空位處。

（4）代碼實現：

實例

package com.test.insertsort;/**
 * 插入排序算法：
 * 1、以數組的某一位作為分隔位，比如index=1，假設左面的都是有序的.
 * 
 * 2、將index位的數據拿出來，放到臨時變量里，這時index位置就空出來了.
 * 
 * 3、從leftindex=index-1開始將左面的數據與當前index位的數據（即temp）進行比較，如果array[leftindex]>temp,
 * 則將array[leftindex]后移一位，即array[leftindex+1]=array[leftindex],此時leftindex就空出來了.
 * 
 * 4、再用index-2(即leftindex=leftindex-1)位的數據和temp比，重復步驟3，
 * 直到找到<=temp的數據或者比到了最左面（說明temp最小），停止比較，將temp放在當前空的位置上.
 * 
 * 5、index向后挪1，即index=index+1，temp=array[index],重復步驟2-4，直到index=array.length,排序結束，
 * 此時數組中的數據即為從小到大的順序.
 * 
 * @author bjh
 * */public class InsertSort {
    private int[] array;    private int length;    
    public InsertSort(int[] array){
        this.array = array;        this.length = array.length;    }
    
    public void display(){        
        for(int a: array){
            System.out.print(a+" ");        }
        System.out.println();    }
    
    /**
     * 插入排序方法     */
    public void doInsertSort(){
        for(int index = 1; index<length; index++){//外層向右的index，即作為比較對象的數據的index
            int temp = array[index];//用作比較的數據
            int leftindex = index-1;            while(leftindex>=0 && array[leftindex]>temp){//當比到最左邊或者遇到比temp小的數據時，結束循環(huán)
                array[leftindex+1] = array[leftindex];                leftindex--;            }
            array[leftindex+1] = temp;//把temp放到空位上
        }
    }
    
    public static void main(String[] args){
        int[] array = {38,65,97,76,13,27,49};        InsertSort is = new InsertSort(array);        System.out.println("排序前的數據為：");        is.display();        is.doInsertSort();        System.out.println("排序后的數據為：");        is.display();    }}

（5）插入排序分析：

時間復雜度，由于仍然需要兩層循環(huán)，插入排序的時間復雜度仍然為O(n*n)。

　　比較次數：在第一輪排序中，插入排序最多比較一次；在第二輪排序中插入排序最多比較二次；以此類推，最后一輪排序時，最多比較N-1次，因此插入排序的最多比較次數為1+2+...+N-1=N*(N-1)/2。盡管如此，實際上插入排序很少會真的比較這么多次，因為一旦發(fā)現左側有比目標元素小的元素，比較就停止了，因此，插入排序平均比較次數為N*(N-1)/4。

移動次數：插入排序的移動次數與比較次數幾乎一致，但移動的速度要比交換的速度快得多。

綜上，插入排序的速度約比冒泡排序快一倍（比較次數少一倍），比選擇排序還要快一些，對于基本有序的數據，插入排序的速度會很快，是簡單排序中效率最高的排序算法。

快排、冒泡排序、選擇排序、插入排序、歸并排序

一、概述：

上文介紹了常見簡單算法：冒泡排序、選擇排序和插入排序。本文介紹高級排序算法：快速排序和歸并排序。在開始介紹算法之前，首先介紹高級算法所需要的基礎知識：劃分、遞歸，并順帶介紹二分查找算法。

二、劃分：

劃分是快速排序的前提，即把數據分為兩組，大于特定值的數據在一組，小于特定值的數據在另一組?？焖倥判蚣词怯蓜澐趾瓦f歸操作來完成的。

（1）原理：

定義一個閾值，分別從最左面和最右面向中間遍歷元素，左面找到一個大于閾值的數據便停止，右邊找到一個小于閾值的數據便停止，如果此時左右兩邊都還沒有走到中間，則交換左面大于閾值的數據和右面小于閾值的數據；重復上述過程，直到左面指針和右面指針相遇，此時左面數據均小于閾值，右面數據均大于閾值，劃分結束。劃分結束后，數據仍然是無序的，但更接近于有序。

（2）例子：

待劃分數據：7, 6, 9, 8, 5,1，假設閾值為5

第一輪：左指針指向7，右指針指向1，左指針向后移，右指針向左移，發(fā)現左面第一個大于5的元素7，右面第一個小于5的元素1，交換7和1的位置，結果：1,6,9,8,5,7；

第二輪：從6開始找大于5的數字，找到6，右邊從5起找小于5的數字，找到1，但此時由于6在1的右面，，即右指針<左指針，左右指針交叉，此時劃分結束。原數列被劃分為兩部分，左側子數列只有一個元素，即為1，其為小于閾值的子數列；右側子數列包括5個元素，均為大于閾值5的元素。 （3）代碼實現：

實例

package com.test.insertsort; 
/**
 * 劃分、遞歸、快排
 * @author bjh
 * */public class QuickSort {
    
    /**待排序、劃分數組*/
    private int[] array;    /**數組長度*/
    private int length;    
    public QuickSort(int[] array){
        this.array = array;        this.length = array.length;    }
    
    /**
     * 打印元素     */
    public void printArray(){
        for(int i=0; i<length; i++){
            System.out.print(array[i]+" ");        }
        System.out.println();    }
    
    
    /**
     * 劃分
     * @return 劃分的分界點     */
    public int partition(int left, int right, int pivot){
        //左指針的起點，left-1是由于在后面的循環(huán)中，每循環(huán)一次左指針都要右移，
        //這樣可以確保左指針從左邊第一個元素開始，不然是從第二個開始
        int leftpoint = left-1;        //右指針的起點，right+1是由于后面的循環(huán)中，每循環(huán)一次右指針都要左移，
        //這樣可以確保右指針從最右邊開始，不然是從倒數第二個開始
        int rightpoint = right+1;        while(true){
            //找到左邊大于pivot的數據，或者走到了最右邊仍然沒有找到比pivot大的數據
            while(leftpoint<right && array[++leftpoint]<pivot);            //找到右邊小于pivot的數據，或者走到了最左邊仍然沒有找到比pivot小的數據
            while(rightpoint>left && array[--rightpoint]>pivot);            //左指針和右指針重疊或相交
            if(leftpoint >= rightpoint){
                break;            }else{
                //交換左邊大的和右邊小的數據
                swap(leftpoint,rightpoint);            }
        }
        //返回分界點，即右邊子數組中最左邊的點
        return leftpoint;    }
    
    
    /**
     * 交換數據     */
    public void swap(int leftpoint,int rightpoint){
        int temp = array[leftpoint];        array[leftpoint] = array[rightpoint];        array[rightpoint] = temp;    }
    
    public static void main(String args[]){
        int[] array = {99,78,26,17,82,36,9,81,22,100,30,20,17,85};        QuickSort qs = new QuickSort(array);        System.out.println("劃分前的數據為：");        qs.printArray();        int bound = qs.partition(0, array.length-1, 50);        System.out.println("劃分后的數據為：");        qs.printArray();        System.out.println("劃分的分界點為：" + array[bound] + "，分界點的坐標為：" + bound);    }
 }

運行結果為：

到此，關于“Java排序算法實現的方法是什么”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續(xù)學習更多相關知識，請繼續(xù)關注億速云網站，小編會繼續(xù)努力為大家?guī)砀鄬嵱玫奈恼拢?/p>