天天看點

數組排序的四種方法

在程式設計中,經常需要将一組數列進行排序,這樣更加友善與統計與查詢。這篇部落格,我就來介紹幾種關于數組排序的方法。

一)通過Arrays類的靜态sort()方法,實作對數組進行排序,sort()方法提供了多種重載形式,可對任意類型的數組進行升序排序。

文法如下:

Arrays.sort(object)     //其中,object是指進行排序的數組名稱。
           

算法執行個體:

import java.util.Arrays;        //導入java.util.Arrays類

public class Demo1 {
    public static void main(String[] args) {
        int arr[]=new int[]{5,25,1,77};
        Arrays.sort(arr);       //運用sort()方法進行排序
        for(int i=0 ; i<4 ; i++){ //循環周遊排序後的數組
            System.out.print(arr[i]+" "); //将排序後的數組的各個元素進行輸出
        }
    }
}
           

運作結果:

數組排序的四種方法

上述執行個體是對整形資料進行排序,Java中的String類型數組的排序算法,是根據字典編排順序排序的,是以數字排在字母前邊,大寫字母排在小寫字母前面。

 二)冒泡排序:這是廣大學習者最先接觸的一種排序算法,它排序數組元素的過程總是将小數往前放、大數往後放,類似于水中氣泡往上升的動作,是以稱冒泡排序。

基本思想:冒泡排序的基本思想是對比相鄰的元素值,如果滿足條件就交換元素值,把較小的元素移動到數組前面,把大的元素移動到數組後面(也就是交換兩個元素的位置),這樣較小的元素就像氣泡一樣從底部上升到頂部。

算法執行個體:

public class Demo2 {
    public static void main(String[] args) {
        int array[]={55,88,78,12,3,1};
        Demo2 demo2=new Demo2();
        demo2.sort(array);   //調用後面的排序方法将數組進行排序
    }
    /**
     * 冒泡排序
     * 
     * @param array
     *          要排序的數組
     */
    public void sort(int[] array){
        for(int i=1 ; i<array.length;i++){
            //比較兩個相鄰的元素,較大的數往冒泡
            for(int j=0;j<array.length-i;j++){
                if(array[j]>array[j+1]){
                    int temp=array[j];   //第一個元素存于臨時變量temp中
                    array[j]=array[j+1]; //第二個元素儲存在第一個元素單元中
                    array[j+1]=temp;  //把臨時變量(也就是第一個元素原值)儲存在第二個元素單元
                }
            }
        }
        showArray(array);    //輸出冒泡排序後的數組
    }
    /**
     * 顯示數組胡所有元素
     * 
     * @param  array
     *          要顯示的數組
     */
    public void showArray(int[] array){
        for(int i:array){                    //周遊數組
            System.out.print(">"+i);         //輸出每個數組的元素值
        }
        System.out.println();
    }
}
           

運作結果:

數組排序的四種方法

冒泡排序的主要思想就是:把相鄰兩個元素進行比較,如滿足一定條件則進行交換(如判斷大小或日期前後等),每次循環都将最大(或最小)的元素排在最後,下一次循環是對數組中其他元素進行類似操作。

三)直接選擇排序:直接選擇排序屬于選擇排序的一種,它的排序速度要比冒泡排序快一些,也是常用的排序算法。

基本思想:将指定排序位置與其他數組元素分别對比,如果滿足條件就交換元素值,注意這裡差別冒泡排序,不是交換相鄰元素,而是把滿足條件的元素與指定的排序位置交換。

算法執行個體:

/**
 * 直接選擇排序算法執行個體
 */

public class Demo2 {
    public static void main(String[] args) {
        int array[]={22,45,85,1,2,0,32};
        Demo2 demo2=new Demo2();
        demo2.sort(array);  //調用後面的排序方法
    }
    /**
     * 直接選擇排序
     * 
     * @param array
     *          要排序的數組
     */
    public void sort(int[] array){
        int index;
        for(int i=1 ; i<array.length;i++){
            index=0;
            for(int j=0;j<array.length-i;j++){
                if(array[j]>array[index]){
                    index=j;  //找出本次循環數組中最大的元素的位置
                }
            }
            //交換在位置array.length-i和index(最大值)上的兩個元素
            int temp=array[array.length-i];
            array[array.length-i]=array[index];
            array[index]=temp;
        }
        showArray(array);
    }
    /**
     * 顯示數組胡所有元素
     * 
     * @param  array
     *          要顯示的數組
     */
    public void showArray(int[] array){
        for(int i:array){
            System.out.print(">"+i);
        }
        System.out.println();
    }
}
           

運作結果:

數組排序的四種方法

将直接選擇排序算法與冒泡排序算法相比較,我們可以看出,冒泡排序是交換滿足條件的相鄰元素值,而直接選擇排序則是先找大最大(或最小)元素值的位置,然後與相應位置的元素進行交換。

四)反轉排序:顧名思義,反轉排序就是以相反的順序把原數組的内容進行重新排序。

基本思想:把數組最後一個元素與第一個元素進行替換,倒數第二個與第二個元素進行替換,以此類推,直到把所有元素反轉替換。

算法執行個體:

/**
 * 反轉排序算法執行個體
 */

public class Demo2 {
    public static void main(String[] args) {
        int array[]={1,2,3,4,5,6,7,8,9,10};
        Demo2 demo2=new Demo2();
        demo2.sort(array);
    }
    /**
     * 反轉排序
     * 
     * @param array
     *          要排序的數組
     */
    public void sort(int[] array){
        System.out.println("數組原有内容:" );
        showArray(array);
        int temp;
        int len=array.length;
        for(int i=0; i<len/2;i++){
           temp=array[i];
           array[i]=array[len-1-i];
           array[len-1-i]=temp;
        }
        System.out.println("數組反轉後内容:");
        showArray(array);
    }
    /**
     * 顯示數組胡所有元素
     * 
     * @param  array
     *          要顯示的數組
     */
    public void showArray(int[] array){
        for(int i:array){
            System.out.print("\t"+i);
        }
        System.out.println();
    }
}
           

運作結果:

數組排序的四種方法

最後,需要注意的是,數組的下标都是從0開始的,最後一個元素的表示總是“數組名.length-1”。