一、冒泡排序

1.1冒泡排序算法的原理如下：

1. 比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
2. 對每一對相鄰元素做同樣的工作，從開始第一對到結(jié)尾的最后一對。在這一點，最后的元素應(yīng)該會是最大的數(shù)。
3. 針對所有的元素重復(fù)以上的步驟，除了最后一個。
4. 持續(xù)每次對越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對數(shù)字需要比較。

1.2算法穩(wěn)定性

冒泡排序就是把小的元素往前調(diào)或者把大的元素往后調(diào)。比較是相鄰的兩個元素比較，交換也發(fā)生在這兩個元素之間。所以，如果兩個元素相等，是不會再交換的；如果兩個相等的元素沒有相鄰，那么即使通過前面的兩兩交換把兩個相鄰起來，這時候也不會交換，所以相同元素的前后順序并沒有改變，所以冒泡排序是一種穩(wěn)定排序算法。

1.3算法描述(優(yōu)化)

• 針對問題：
  數(shù)據(jù)的順序排好之后，冒泡算法仍然會繼續(xù)進行下一輪的比較，直到arr.length-1次，后面的比較沒有意義的。
• 方案：
  設(shè)置標志位flag，如果發(fā)生了交換flag設(shè)置為true；如果沒有交換就設(shè)置為false。
  這樣當一輪比較結(jié)束后如果flag仍為false，即：這一輪沒有發(fā)生交換，說明數(shù)據(jù)的順序已經(jīng)排好，沒有必要繼續(xù)進行下去。
• 以java代碼為例

public static void BubbleSort1(int [] arr){
　   int temp;//臨時變量
　   boolean flag;//是否交換的標志
　   for(int i=0; i<arr.length-1; i++){   //表示趟數(shù)，一共 arr.length-1 次
　       // 每次遍歷標志位都要先置為false，才能判斷后面的元素是否發(fā)生了交換
　       flag = false;
　       for(int j=arr.length-1; j>i; j--){ //選出該趟排序的最小值往前移動，所以最前面的不參與循環(huán)j>i
　           if(arr[j] < arr[j-1]){
　               temp = arr[j];
　               arr[j] = arr[j-1];
　               arr[j-1] = temp;
　               flag = true;    //只要有發(fā)生了交換，flag就置為true
　           }
　       }
　       // 判斷標志位是否為false，如果為false，說明后面的元素已經(jīng)有序，就直接return
　       if(!flag) break;
　   }
}

二、選擇排序

2.1選擇排序思路

首先在未排序序列中找到最?。ù螅┰?，存放到排序序列的起始位置，然后，再從剩余未排序元素中繼續(xù)尋找最小（大）元素，然后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。

2.2算法穩(wěn)定性

選擇排序是給每個位置選擇當前元素最小的，比如給第一個位置選擇最小的，在剩余元素里面給第二個元素選擇第二小的，依次類推，直到第n-1個元素，第n個元素不用選擇了，因為只剩下它一個最大的元素了。那么，在一趟選擇，如果一個元素比當前元素小，而該小的元素又出現(xiàn)在一個和當前元素相等的元素后面，那么交換后穩(wěn)定性就被破壞了。舉個例子，序列5 8 5 2 9，我們知道第一遍選擇第1個元素5會和2交換，那么原序列中兩個5的相對前后順序就被破壞了，所以選擇排序是一個不穩(wěn)定的排序算法。

2.3算法描述（java）

public static void selectionSort(int[] arr){                
    for(int i = 0; i < arr.length - 1; i++){
        // 交換次數(shù)         
        // 先假設(shè)每次循環(huán)時，最小數(shù)的索引為i            
        int minIndex = i;// 每一個元素都和剩下的未排序的元素比較          
        for(int j = i + 1; j < arr.length; j++){             
            if(arr[j] < arr[minIndex]){//尋找最小數(shù)                   
                minIndex = j;//將最小數(shù)的索引保存                
            }           
        }//經(jīng)過一輪循環(huán)，就可以找出第一個最小值的索引，然后把最小值放到i的位置           
        swap(arr, i, minIndex);         
    }   
}
 
private static void swap(int[] arr, int i, int j) {     
    int temp = arr[i];      
    arr[i] = arr[j];        
    arr[j] = temp;          
}

三、快速排序

3.1快速排序流程

1. 首先設(shè)定一個分界值，通過該分界值將數(shù)組分成左右兩部分。
2. 將大于或等于分界值的數(shù)據(jù)集中到數(shù)組右邊，小于分界值的數(shù)據(jù)集中到數(shù)組的左邊。此時，左邊部分中各元素都小于或等于分界值，而右邊部分中各元素都大于或等于分界值。
3. 然后，左邊和右邊的數(shù)據(jù)可以獨立排序。對于左側(cè)的數(shù)組數(shù)據(jù)，又可以取一個分界值，將該部分數(shù)據(jù)分成左右兩部分，同樣在左邊放置較小值，右邊放置較大值。右側(cè)的數(shù)組數(shù)據(jù)也可以做類似處理。
4. 重復(fù)上述過程，可以看出，這是一個遞歸定義。通過遞歸將左側(cè)部分排好序后，再遞歸排好右側(cè)部分的順序。當左、右兩個部分各數(shù)據(jù)排序完成后，整個數(shù)組的排序也就完成了。

3.2排序原理

設(shè)要排序的數(shù)組是A[0]……A[N-1]，首先任意選取一個數(shù)據(jù)（通常選用數(shù)組的第一個數(shù)）作為關(guān)鍵數(shù)據(jù)，然后將所有比它小的數(shù)都放到它左邊，所有比它大的數(shù)都放到它右邊，這個過程稱為一趟快速排序。值得注意的是，快速排序不是一種穩(wěn)定的排序算法，也就是說，多個相同的值的相對位置也許會在算法結(jié)束時產(chǎn)生變動。

一趟快速排序的算法是：

1. 設(shè)置兩個變量i、j，排序開始的時候：i=0，j=N-1；
2. 以第一個數(shù)組元素作為關(guān)鍵數(shù)據(jù)，賦值給key，即key=A[0]；
3. 從j開始向前搜索，即由后開始向前搜索(j--)，找到第一個小于key的值A(chǔ)[j]，將A[j]和A[i]的值交換；
4. 從i開始向后搜索，即由前開始向后搜索(i++)，找到第一個大于key的A[i]，將A[i]和A[j]的值交換；
5. 重復(fù)第3、4步，直到i==j； (3,4步中，沒找到符合條件的值，即3中A[j]不小于key,4中A[i]不大于key的時候改變j、i的值，使得j=j-1，i=i+1，直至找到為止。找到符合條件的值，進行交換的時候i， j指針位置不變。另外，i==j這一過程一定正好是i+或j-完成的時候，此時令循環(huán)結(jié)束）。

3.3排序演示

假設(shè)一開始序列{xi}是：5，3，7，6，4，1，0，2，9，10，8。
此時，key=5，i=1，j=10，從后往前找，第一個比5小的數(shù)是x8=2，因此序列為：2，3，7，6，4，1，0，5，9，10，8。
此時i=1，j=8，從前往后找，第一個比5大的數(shù)是x3=7，因此序列為：2，3，5，6，4，1，0，7，9，10，8。
此時，i=3，j=8，從第8位往前找，第一個比5小的數(shù)是x7=0，因此：2，3，0，6，4，1，5，7，9，10，8。
此時，i=3，j=7，從第3位往后找，第一個比5大的數(shù)是x4=6，因此：2，3，0，5，4，1，6，7，9，10，8。
此時，i=4，j=7，從第7位往前找，第一個比5小的數(shù)是x6=1，因此：2，3，0，1，4，5，6，7，9，10，8。
此時，i=4，j=6，從第4位往后找，直到第6位才有比5大的數(shù)，這時，i=j=6，key成為一條分界線，它之前的數(shù)都比它小，之后的數(shù)都比它大，對于前后兩部分數(shù)，可以采用同樣的方法來排序。

3.4代碼展示（java）

public static int[] qsort(int arr[],int start,int end) {        
    int pivot = arr[start];        
    int i = start;        
    int j = end;        
    while (i<j) {            
        while ((i<j)&&(arr[j]>pivot)) {                
            j--;            
        }            
        while ((i<j)&&(arr[i]<pivot)) {                
            i++;            
        }            
        if ((arr[i]==arr[j])&&(i<j)) {                
            i++;            
        } else {                
            int temp = arr[i];                
            arr[i] = arr[j];                
            arr[j] = temp;            
        }        
    }        
    if (i-1>start) arr=qsort(arr,start,i-1);        
    if (j+1<end) arr=qsort(arr,j+1,end);        
    return (arr);    
}    
 
public static void main(String[] args) {        
    int arr[] = new int[]{3,3,3,7,9,122344,4656,34,34,4656,5,6,7,8,9,343,57765,23,12321};        
    int len = arr.length-1;        
    arr=qsort(arr,0,len);        
    for (int i:arr) {            
        System.out.print(i+"\t");        
    }    
}