穩定度（穩定性）
一個排序演算法是穩定的，就是當有兩個相等記錄的關鍵字R和S，且在原本的列表中R出現在S之前，在排序過的列表中R也將會是在S之前。
排序演算法分類
常見的有插入（插入排序/希爾排序）、交換（氣泡排序/快速排序）、選擇（選擇排序）、合併（歸併排序）等。
一.插入排序
插入排序（Insertion Sort），它的工作原理是通過構建有序序列，對於未排序資料，在已排序序列中從後向前掃描，找到相應位置並插入。插入排序在實現上，通常採用in-place排序（即只需用到O(1)的額外空間的排序），因而在從後向前掃描過程中，需要反覆把已排序元素逐步向後挪位，為最新元素提供插入空間。
一般來說，插入排序都採用in-place在陣列上實現。具體演算法描述如下：從第一個元素開始，該元素可以認為已經被排序。取出下一個元素，在已經排序的元素序列中從後向前掃描。如果該元素（已排序）大於新元素，將該元素移到下一位置。重複步驟3，直到找到已排序的元素小於或者等於新元素的位置。將新元素插入到該位置後。重複步驟2~5。
複製程式碼 程式碼如下:
public static void ionSort(int[] data) {
for (int index = 1; index < th; index++) {
int key = data[index];
int position = index;
// shift larger values to the right
while (position > 0 && data[position - 1] > key) {
data[position] = data[position - 1];
position--;
}
data[position] = key;
}
}
二.希爾排序
希爾排序(Shell Sort)是插入排序的一種。是針對直接插入排序演算法的改進。該方法又稱縮小增量排序，因DL．Shell於1959年提出而得名。
希爾排序是基於插入排序的以下兩點性質而提出改進方法的：插入排序在對幾乎已經排好序的資料操作時， 效率高， 即可以達到線性排序的效率。但插入排序一般來說是低效的， 因為插入排序每次只能將資料移動一位。
複製程式碼 程式碼如下:
staticvoid shellSort(Lista) {
int h = 1;
while (h < ()/3) h = h*3 + 1; //: 1, 4, 13, 40, 121, ...
for (; h >= 1; h /= 3)
for (int i = h; i < (); i++)
for (int j = i; j >= h && (j)areTo((j-h)) < 0; j-=h)
(a, j, j-h);
}
三.氣泡排序
氣泡排序（Bubble Sort，臺灣譯為：泡沫排序或氣泡排序）是一種簡單的排序演算法。它重複地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重複地進行直到沒有再需要交換，也就是說該數列已經排序完成。這個演算法的名字由來是因為越小的元素會經由交換慢慢“浮”到數列的頂端。
氣泡排序演算法的運作如下：
比較相鄰的元素，如果第一個比第二個大，就交換他們兩個。
對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對，在這一點，最後的元素應該會是最大的數。
針對所有的元素重複以上的步驟，除了最後一個。
持續每次對越來越少的元素重複上面的步驟，直到沒有任何一對數字需要比較。
複製程式碼 程式碼如下:
public static void bubbleSort(int[] data) {
int temp = 0;
for (int i = th - 1; i > 0; --i) {
boolean isSort = false;
for (int j = 0; j < i; ++j) {
if (data[j + 1] < data[j]) {
temp = data[j];
data[j] = data[j + 1];
data[j + 1] = temp;
isSort = true;
}
}
// 如果一次內迴圈中發生了交換，那麼繼續比較；如果一次內迴圈中沒發生任何交換，則認為已經排序好了。
if (!isSort)
break;
}
}
四.快速排序
快速排序（Quicksort）是對氣泡排序的一種改進。由C. A. R. Hoare在1962年提出。它的基本思想是：通過一趟排序將要排序的資料分割成獨立的兩部分，其中一部分的所有資料都比另外一部分的所有資料都要小，然後再按此方法對這兩部分資料分別進行快速排序，整個排序過程可以遞迴進行，以此達到整個資料變成有序序列。
快速排序使用分治法（Divide and conquer）策略來把一個序列（list）分為兩個子序列（sub-lists）。
步驟為：
從數列中挑出一個元素，稱為 "基準"（pivot）。重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的後面（相同的數可以到任一邊）。在這個分割槽退出之後，該基準就處於數列的中間位置。這個稱為分割槽（partition）操作。遞迴地（recursive）把小於基準值元素的子數列和大於基準值元素的子數列排序。
複製程式碼 程式碼如下:
/*
* more efficient implements for quicksort.
* use left, center and right median value (@see #median()) for the pivot, and
* the more efficient inner loop for the core of the algorithm.
*/
public class Quicksort {
public static final int CUTOFF = 11;
/**
* quick sort algorithm.
*
* @param arr an array of Comparable items.
*/
public staticvoid quicksort(T[] arr) {
quickSort(arr, 0, th - 1);
}
/**
* get the median of the left, center and right.
* order these and hide the pivot by put it the end of of the array.
*
* @param arr an array of Comparable items.
* @param left the most-left index of the subarray.
* @param right the most-right index of the subarray.
* @return T
*/
public staticT median(T[] arr, int left, int right) {
int center = (left + right) / 2;
if (arr[left]areTo(arr[center]) > 0)
swapRef(arr, left, center);
if (arr[left]areTo(arr[right]) > 0)
swapRef(arr, left, right);
if (arr[center]areTo(arr[right]) > 0)
swapRef(arr, center, right);
swapRef(arr, center, right - 1);
return arr[right - 1];
}
/**
* internal method to sort the array with quick sort algorithm.
*
* @param arr an array of Comparable Items.
* @param left the left-most index of the subarray.
* @param right the right-most index of the subarray.
*/
private staticvoid quickSort(T[] arr, int left, int right) {
if (left + CUTOFF <= right) {
// find the pivot
T pivot = median(arr, left, right);
// start partitioning
int i = left, j = right - 1;
for (;;) {
while (arr[++i]areTo(pivot) < 0);
while (arr[--j]areTo(pivot) > 0);
if (i < j)
swapRef(arr, i, j);
else
break;
}
// swap the pivot reference back to the small collection.
swapRef(arr, i, right - 1);
quickSort(arr, left, i - 1); // sort the small collection.
quickSort(arr, i + 1, right); // sort the large collection.
} else {
// if the total number is less than CUTOFF we use ion sort
// instead (cause it much more efficient).
ionSort(arr, left, right);
}
}
/**
* method to swap references in an array.
*
* @param arr an array of Objects.
* @param idx1 the index of the first element.
* @param idx2 the index of the second element.
*/
public staticvoid swapRef(T[] arr, int idx1, int idx2) {
T tmp = arr[idx1];
arr[idx1] = arr[idx2];
arr[idx2] = tmp;
}
/**
* method to sort an subarray from start to end with ion sort
* algorithm.
*
* @param arr an array of Comparable items.
* @param start the begining position.
* @param end the end position.
*/
public staticvoid ionSort(T[] arr, int start, int end) {
int i;
for (int j = start + 1; j <= end; j++) {
T tmp = arr[j];
for (i = j; i > start && areTo(arr[i - 1]) < 0; i--) {
arr[i] = arr[i - 1];
}
arr[i] = tmp;
}
}
private static void printArray(Integer[] c) {
for (int i = 0; i < th; i++)
t(c[i] + ",");
tln();
}
public static void main(String[] args) {
Integer[] data = {10, 4, 9, 23, 1, 45, 27, 5, 2};
tln("bubbleSort...");
printArray(data);
quicksort(data);
printArray(data);
}
}
五.選擇排序
選擇排序(Selection sort)是一種簡單直觀的排序演算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然後，再從剩餘未排序元素中繼續尋找最小（大）元素，然後放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。
因為每一趟確定元素的過程中都會有一個選擇最小值的子流程，所以人們形象地稱之為選擇排序。
舉個例子，序列5 8 5 2 9，我們知道第一遍選擇第1個元素5會和2交換，那麼原序列中2個5的相對前後順序就被破壞了，所以選擇排序不是一個穩定的排序演算法。
複製程式碼 程式碼如下:
public static void selectSort(int[] data) {
int minIndex = 0;
int temp = 0;
for (int i = 0; i < th; i++) {
minIndex = i; // 無序區的.最小資料陣列下標
for (int j = i + 1; j < th; j++) { // 在無序區中找到最小資料並儲存其陣列下標
if (data[j] < data[minIndex]) {
minIndex = j;
}
}
if (minIndex != i) { // 如果不是無序區的最小值位置不是預設的第一個資料，則交換之。
temp = data[i];
data[i] = data[minIndex];
data[minIndex] = temp;
}
}
}
六.歸併排序
歸併排序（Merge sort）是建立在歸併操作上的一種有效的排序演算法。該演算法是採用分治法（Divide and Conquer）的一個非常典型的應用。
歸併操作的過程如下：
申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合併後的序列。
設定兩個指標，最初位置分別為兩個已經排序序列的起始位置。
比較兩個指標所指向的元素，選擇相對小的元素放入到合併空間，並移動指標到下一位置。
重複步驟3直到某一指標達到序列尾。
將另一序列剩下的所有元素直接複製到合併序列尾。
複製程式碼 程式碼如下:
public static int[] mergeSort(int[] arr) {// 歸併排序 --遞迴
if (th == 1) {
return arr;
}
int half = th / 2;
int[] arr1 = new int[half];
int[] arr2 = new int[th - half];
ycopy(arr, 0, arr1, 0, th);
ycopy(arr, half, arr2, 0, th);
arr1 = mergeSort(arr1);
arr2 = mergeSort(arr2);
return mergeSortSub(arr1, arr2);
}
private static int[] mergeSortSub(int[] arr1, int[] arr2) {// 歸併排序子程式
int[] result = new int[th + th];
int i = 0;
int j = 0;
int k = 0;
while (true) {
if (arr1[i] < arr2[j]) {
result[k] = arr1[i];
if (++i > th - 1) {
break;
}
} else {
result[k] = arr2[j];
if (++j > th - 1) {
break;
}
}
k++;
}
for (; i < th; i++) {
result[++k] = arr1[i];
}
for (; j < th; j++) {
result[++k] = arr2[j];
}
return result;
}
完整程式碼（除QuickSort）
複製程式碼 程式碼如下:
package king;
import .*;
/**
* 幾路常見的排序演算法Java實現
* @author acer
*
*/
public class CommonSort {
/**
* 插入排序具體演算法描述如下：
* 1.從第一個元素開始，該元素可以認為已經被排序
* 2.取出下一個元素，在已經排序的元素序列中從後向前掃描
* 3.如果該元素（已排序）大於新元素，將該元素移到下一位置
* 4.重複步驟3，直到找到已排序的元素小於或者等於新元素的位置
* 5.將新元素插入到該位置後
* 6.重複步驟2~5
*/
public static void ionSort(int[] data) {
for (int index = 1; index < th; index++) {
int key = data[index];
int position = index;
// shift larger values to the right
while (position > 0 && data[position - 1] > key) {
data[position] = data[position - 1];
position--;
}
data[position] = key;
}
}
/**
* 希爾排序，演算法實現思想參考維基百科；適合大數量排序操作。
*/
staticvoid shellSort(Lista) {
int h = 1;
while (h < ()/3) h = h*3 + 1; //: 1, 4, 13, 40, 121, ...
for (; h >= 1; h /= 3)
for (int i = h; i < (); i++)
for (int j = i; j >= h && (j)areTo((j-h)) < 0; j-=h)
(a, j, j-h);
}
/**
* 氣泡排序演算法的運作如下：
* 1.比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
* 2.對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對。在這一點，最後的元素應該會是最大的數。
* 3.針對所有的元素重複以上的步驟，除了最後一個。
* 4.持續每次對越來越少的元素重複上面的步驟，直到沒有任何一對數字需要比較。[1]
*/
public static void bubbleSort(int[] data) {
int temp = 0;
for (int i = th - 1; i > 0; --i) {
boolean isSort = false;
for (int j = 0; j < i; ++j) {
if (data[j + 1] < data[j]) {
temp = data[j];
data[j] = data[j + 1];
data[j + 1] = temp;
isSort = true;
}
}
// 如果一次內迴圈中發生了交換，那麼繼續比較；如果一次內迴圈中沒發生任何交換，則認為已經排序好了。
if (!isSort)
break;
}
}
/**
* 選擇排序的基本思想是：
* 1.遍歷陣列的過程中，以 i 代表當前需要排序的序號，則需要在剩餘的 [i+1…n-1] 中找出其中的最小值，
* 2.然後將找到的最小值與 i 指向的值進行交換。
* 因為每一趟確定元素的過程中都會有一個選擇最小值的子流程，所以人們形象地稱之為選擇排序。
* @param data
*/
public static void selectSort(int[] data) {
int minIndex = 0;
int temp = 0;
for (int i = 0; i < th; i++) {
minIndex = i; // 無序區的最小資料陣列下標
for (int j = i + 1; j < th; j++) { // 在無序區中找到最小資料並儲存其陣列下標
if (data[j] < data[minIndex]) {
minIndex = j;
}
}
if (minIndex != i) { // 如果不是無序區的最小值位置不是預設的第一個資料，則交換之。
temp = data[i];
data[i] = data[minIndex];
data[minIndex] = temp;
}
}
}
/**
* 歸併操作的過程如下：
* 1.申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合併後的序列
* 2.設定兩個指標，最初位置分別為兩個已經排序序列的起始位置
* 3.比較兩個指標所指向的元素，選擇相對小的元素放入到合併空間，並移動指標到下一位置
* 4.重複步驟3直到某一指標達到序列尾
* 5.將另一序列剩下的所有元素直接複製到合併序列尾
*/
public static int[] mergeSort(int[] arr) {// 歸併排序 --遞迴
if (th == 1) {
return arr;
}
int half = th / 2;
int[] arr1 = new int[half];
int[] arr2 = new int[th - half];
ycopy(arr, 0, arr1, 0, th);
ycopy(arr, half, arr2, 0, th);
arr1 = mergeSort(arr1);
arr2 = mergeSort(arr2);
return mergeSortSub(arr1, arr2);
}
private static int[] mergeSortSub(int[] arr1, int[] arr2) {// 歸併排序子程式
int[] result = new int[th + th];
int i = 0;
int j = 0;
int k = 0;
while (true) {
if (arr1[i] < arr2[j]) {
result[k] = arr1[i];
if (++i > th - 1) {
break;
}
} else {
result[k] = arr2[j];
if (++j > th - 1) {
break;
}
}
k++;
}
for (; i < th; i++) {
result[++k] = arr1[i];
}
for (; j < th; j++) {
result[++k] = arr2[j];
}
return result;
}
private static void printArray(int[] c) {
for (int i = 0; i < th; i++)
t(c[i] + ",");
tln();
}
public static void main(String []args){
int[] data = {10,4,9,23,1,45,27,5,2};
tln("bubbleSort...");
int[] a = e();
printArray(a);
bubbleSort(a);
printArray(a);
tln("selectSort...");
int[] b = e();
printArray(b);
selectSort(b);
printArray(b);
tln("ionSort...");
int[] c = e();
printArray(c);
ionSort(c);
printArray(c);
tln("shellSort...");
Listlist = new ArrayList();
for(int i=0;i<th;i++)
(data[i]);
tln(list);
shellSort(list);
tln(list);
tln("mergeSort...");
int[] d = e();
printArray(d);
printArray(mergeSort(d));
}
}
