數組常用排序算法

排序算法總結

常用排序算法

冒泡排序BubbleSort

直接選擇排序SelectSort

快速排序QuickSort

今天複習到數組部分，發現數組部分中比較重要的可能就是排序這個問題了。其他像周遊、填充替換數組元素、複制數組、查詢數組等都相對簡單，就把排序部分稍作整理。沒什麼高深知識，随便看看就好。

首先貼出冒泡排序和直接選擇排序的代碼，兩者相近且比較簡單，本來打算分着寫更明顯，不過看着實在太短了，就在一個類中寫出了，類名也沒改，大家将就看吧=。=

public class BubbleSort {//冒泡排序和直接選擇排序

    public static void main(String[] args) {
        int a[]=new int[]{,,,,};
        bubble(a);
        select(a);
    }
    public static void bubble(int arr[]){
        int temp;
        for(int i=;i<arr.length;i++){
            for(int j=;j<arr.length--i;j++){
                if(arr[j]>arr[j+]){
                    temp=arr[j+];
                    arr[j+]=arr[j];
                    arr[j]=temp;
                }
            }
        }
        for(int x:arr){
            System.out.print(x+" ");
        }
        System.out.println();
    }
    public static void select(int arr[]){

        for(int i=;i<arr.length;i++){
            int index = ;
            for(int j=;j<arr.length--i;j++){
                if(arr[index]<arr[j+]){
                    index=j+;
                }
            }
            int temp;
            temp=arr[arr.length--i];
            arr[arr.length--i]=arr[index];
            arr[index]=temp;
        }
        for(int x:arr){
            System.out.print(x+" ");
        }
    }
}
           

在我看來，冒泡排序和直接選擇排序相近。兩者的比較次數相同，交換次數：冒泡排序>直接選擇排序，代碼有一定的相似性。

兩者代碼都是有嵌套的兩層for循環作為主體，冒泡排序是相鄰兩數比較，若前者大于後者，則交換位置，直接選擇排序則是一輪循環下來用一個index标記此輪循環的最大值，然後在内層for循環結束後進行本輪最後一個位置和最大值的交換。

而快速排序和他們則有所差別。

public class QuickSort {
    public static void main(String[] args) {
        int arr[] = { , , , ,  };
        quickSort(arr, , arr.length - );
        //quick(arr,0,arr.length-1);
        for (int x : arr) {
            System.out.println(x);
        }
    }

    public static void quickSort(int arr[], int top, int end) {
        if (top < end) {
            int p = partition(arr, top, end);
            quickSort(arr, top, p);
            quickSort(arr, p + , end);
        }

    }

    public static int partition(int arr[], int top, int end) {//每次調用就完成一輪快排
        int x = arr[top];
        int i = top, j = end + ;
        while (true) {
            while (arr[++i] < x && i < end)//從左開始找到比top值大得數
                ;
            while (arr[--j] > x)//從右開始找到比top值小得數
                ;
            if (i >= j)//判斷兩個數是否相遇
                break;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;//不相遇就交換兩個數
        }
        arr[top] = arr[j];
        arr[j] = x;
        return j;

    }
    public static void quick(int[] a, int left, int right){//sort函數源碼,
        for (int i = left, j = i; i < right; j = ++i) {//第一次進去時，i和j總相等
            int ai = a[i + ];//令ai=目前位置的下一個，記錄下新的要排序的數的值
            while (ai < a[j]) {//通過交換找到ai值在0-i+1範圍内應當在的位置，這不是快速排序，
                a[j + ] = a[j];
                if (j-- == left) {
                    break;
                }
            }
            a[j + ] = ai;//到此會發現i+1位之前都是從小到大排序，即每完成一輪循環，數組前面的數就多一個有序的。
        }
    }

}
           

快速排序則和他們完全不同。快速排序用到了分治思想，用遞歸算法達到将數組分割，簡化排序過程。

每一次調用quickSort()方法都會将目前數組分成三部分：首項、>首項、<首項。

分别在後兩個數組中再調用quickSort()方法，分割的下标則是由partition()方法決定的partition為“劃分”意，在這裡用來找到首項應該在的下标位置。

上述代碼中還出現了一個方法quick()，這個方法是從Arrays.sort()方法的源碼中找到的，一開始我認為是快速排序的一個非遞歸化變形，後來發現似乎不是如此，這個方法是從第一個數開始，不斷的往後擴充，沒添加一個數就找到這個數應當在的前面的位置，感覺類似直接選擇排序的倒叙版，但是他每一次又不會周遊整個數組，是以說我也拿不準究竟如何形容他，不過他玲珑的代碼段還是驚豔到我了，果然程式設計是一門藝術活，總有一些神奇的代碼片有着匪夷所思的用處。

如有不妥，敬請交流指教。