算法和資料結構是每個進階程式員必須掌握的。常用的内部排序包括選擇排序、交換排序、插入排序、歸并排序、桶式排序和基數排序。本篇将詳細講述常用的内部排序中的交換排序。之是以稱為交換排序，是因為這些算法的主體是資料組中的資料不斷交換。交換排序包括冒泡排序和快速排序。
轉載請注明出處——http://www.cnblogs.com/zrtqsk/p/3802583.html，謝謝！
一、工具類
為了友善研究排序，這裡，我建立了一個簡單的工具類，用于生成排序資料，以及輸出排序内容。研究排序，當然，所有資料設定為int類型就可以了。如下：
package sort;
import java.util.Arrays;
import java.util.Random;
/**
@ClassName: SortUtil
* @Description: 排序工具類
* @author qsk
* @date 2014年6月21日 下午8:14:55
*/
public class SortUtil {
/**
* @Title: outputArray
* @Description: 輸出int類型數組
* @param @param array
* @return void
* @throws
*/
public static void outputArray(int[] array) {
System.out.println(Arrays.toString(array));
}
/**
* @Title: getRandomArray
* @Description: 得到100範圍内的随機數組
* @param @param size
* @param @return
* @return int[]
* @throws
*/
public static int[] getRandomArray(int size) {
Random rd = new Random(System.currentTimeMillis());
int[] array = new int[size];
for (int i = 0; i < array.length; i++) {
array[i] = rd.nextInt(100);
}
return array;
}
/**
* @Title: getRandomArray
* @Description: 得到100範圍内的長度為10的随即數組
* @param @return
* @return int[]
* @throws
*/
public static int[] getRandomArray() {
return getRandomArray(10);
}
} 二、冒泡排序
冒泡排序的大名，可謂無人不知。它的原理也是非常簡單。
1、原理
對于n個資料的記錄。
第1趟 ： 依次比較0和1、1和2、2和3...n-2和n-1索引處的元素，發現前面的大于後面的，就交換它們，這樣一趟下來，最大的元素排到了最後面。
第2趟 ： 繼續按照第1趟的做法再做一遍，一趟下來，第二大的元素排到了最後面。
......
這樣經過n-1趟比較、交換，n個資料排序完畢。如果某一趟沒有交換，表明已經排序完畢，可提前結束排序。
2、Java實作
package sort;
/**
*
@ClassName: BubbleSort
* @Description: 冒泡排序
* @author qsk
* @date 2014年6月21日 下午4:45:57
*/
public class BubbleSort {
public static void sort(int[] source) {
// 排序前先輸出
SortUtil.outputArray(source);
int size = source.length;
for (int i = 0; i < size - 1; i++) {
boolean isSwap = false;
// 每次排序都從0開始，size-i-1結束,因為每一趟排序結束，都将排序隊列中最大的那個移到最右邊
for (int j = 0; j < size - i - 1; j++) {
//
if (source[j] > source[j + 1]) {
int temp = source[j];
source[j] = source[j + 1];
source[j + 1] = temp;
isSwap = true;
}
}
// 如果沒有換，代表排序已經結束
if (!isSwap) {
break;
}
// 每一次交換結束時輸出
SortUtil.outputArray(source);
}
}
public static void main(String[] args) {
sort(SortUtil.getRandomArray());
}
} 如上，注釋已經非常清楚了，結果如下：
[35, 63, 63, 24, 21, 40, 26, 22, 2, 41]
[35, 63, 24, 21, 40, 26, 22, 2, 41, 63]
[35, 24, 21, 40, 26, 22, 2, 41, 63, 63]
[24, 21, 35, 26, 22, 2, 40, 41, 63, 63]
[21, 24, 26, 22, 2, 35, 40, 41, 63, 63]
[21, 24, 22, 2, 26, 35, 40, 41, 63, 63]
[21, 22, 2, 24, 26, 35, 40, 41, 63, 63]
[21, 2, 22, 24, 26, 35, 40, 41, 63, 63]
[2, 21, 22, 24, 26, 35, 40, 41, 63, 63] 3、時間複雜度和穩定性
冒泡排序的時間複雜度是O(N2)。
假設被排序的數列中有N個數。周遊一趟的時間複雜度是O(N)，需要周遊多少次呢？N-1次！是以，冒泡排序的時間複雜度是O(N2)。
冒泡排序是穩定的算法，它滿足穩定算法的定義。
算法穩定性 -- 假設在數列中存在a[i]=a[j]，若在排序之前，a[i]在a[j]前面；并且排序之後，a[i]仍然在a[j]前面。則這個排序算法是穩定的！
三、快速排序
快速排序是一種速度非常快的交換排序方法，不過實作起來比較複雜。
從資料中取出第一個元素作為分界值、放在中間，所有比分界值小的元素放在左邊，所有比分界值大的元素放在右邊。然後對左右兩個序列進行遞歸，重新選擇分界值并進行移動。這樣層層遞歸下去，直到每個子序列的元素隻剩下一個。
這幾天看到一副完全描述了快速排序的圖檔：
（圖檔出處：http://cricode.com/2001.html）
package sort;
/**
* @ClassName: QuickSort
* @Description: 快速排序
* @author qsk
* @date 2014年6月21日 下午8:15:27
*/
public class QuickSort {
/**
* @Title: sort
* @Description: 用來調用疊代的子排序算法
* @param @param source
* @return void
* @throws
*/
public static void sort(int[] source) {
SortUtil.outputArray(source);
subSort(source, 0, source.length - 1);
}
/**
* @Title: subSort
* @Description: 子排序算法，可以繼續疊代
* @param @param source
* @param @param begin
* @param @param end
* @return void
* @throws
*/
public static void subSort(int[] source, int begin, int end) {
if (begin < end) {
// 标記1從開始起,因為不包括base，而且使用前要++,是以為這個數
int sign1 = begin;
// 标記2從結束起，使用前要--,是以為這個數
int sign2 = end + 1;
// 假設第一個為base
int base = source[begin];
while (true) {
// 從左向右找第一個比base大的數，用sign1标記索引
while (source[++sign1] < base && sign1 < end) {
;
}
// 從右到左找第一個比base小的數，用sign2标記索引
while (source[--sign2] > base && sign2 > begin) {
;
}
// 若此時sign1和sign2沒有碰頭，就交換它們
if (sign1 < sign2) {
swap(source, sign1, sign2);
SortUtil.outputArray(source);
// 若已經碰頭，就結束循環
} else {
break;
}
}
//将base和sign2換一下，這樣，已經将原數組分成2部分，中間的那個為base
swap(source, begin, sign2);
SortUtil.outputArray(source);
subSort(source, begin, sign2 - 1);
subSort(source, sign2 + 1, end);
}
}
/**
* @Title: swap
* @Description: 交換數組中索引i和j處的值
* @param @param source
* @param @param i
* @param @param j
* @return void
* @throws
*/
public static void swap(int[] source, int i, int j) {
int temp = source[i];
source[i] = source[j];
source[j] = temp;
}
public static void main(String[] args) {
sort(SortUtil.getRandomArray());
}
} [83, 7, 11, 47, 66, 26, 85, 79, 44, 14]
[83, 7, 11, 47, 66, 26, 14, 79, 44, 85]
[44, 7, 11, 47, 66, 26, 14, 79, 83, 85]
[44, 7, 11, 14, 66, 26, 47, 79, 83, 85]
[44, 7, 11, 14, 26, 66, 47, 79, 83, 85]
[26, 7, 11, 14, 44, 66, 47, 79, 83, 85]
[14, 7, 11, 26, 44, 66, 47, 79, 83, 85]
[11, 7, 14, 26, 44, 66, 47, 79, 83, 85]
[7, 11, 14, 26, 44, 66, 47, 79, 83, 85]
[7, 11, 14, 26, 44, 47, 66, 79, 83, 85] 3、時間複雜度和穩定性
快速排序的時間複雜度在最壞情況下是O(N2)，平均的時間複雜度是O(N*lgN)。
這句話很好了解：假設被排序的數列中有N個數。周遊一次的時間複雜度是O(N)，需要周遊多少次呢？至少lg(N+1)次，最多N次。
(01) 為什麼最少是lg(N+1)次？快速排序是采用的分治法進行周遊的，我們将它看作一棵二叉樹，它需要周遊的次數就是二叉樹的深度，而根據完全二叉樹的定義，它的深度至少是lg(N+1)。因 此，快速排序的周遊次數最少是lg(N+1)次。
(02) 為什麼最多是N次？這個應該非常簡單，還是将快速排序看作一棵二叉樹，它的深度最大是N。是以，快讀排序的周遊次數最多是N次。
快速排序是不穩定的算法，它不滿足穩定算法的定義。
算法穩定性 -- 假設在數列中存在a[i]=a[j]，若在排序之前，a[i]在a[j]前面；并且排序之後，a[i]仍然在a[j]前面。則這個排序算法是穩定的！
參考：《Java程式員的基本修養》
http://www.cnblogs.com/skywang12345/p/3596746.html
http://www.cnblogs.com/skywang12345/p/3596232.html
/**
* ————————如果覺得本博文還行，别忘了推薦一下哦，謝謝！
* 作者：錢書康
* 歡迎轉載，請保留此段聲明。
* 出處：http://www.cnblogs.com/zrtqsk/
*/