對一序列對象根據某個關鍵字進行排序。

穩(wěn)定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；

不穩(wěn)定：如果a原本在b的前面，而a=b，排序之后a可能會出現在b的后面；

內排序：所有排序操作都在內存中完成；

外排序：由于數據太大，因此把數據放在磁盤中，而排序通過磁盤和內存的數據傳輸才能進行；

時間復雜度： 一個算法執(zhí)行所耗費的時間。

空間復雜度：運行完一個程序所需內存的大小。

（注意：n指數據規(guī)模；k指“桶”的個數；In-place指占用常數內存，不占用額外內存；Out-place指占用額外內存）

常見的快速排序、歸并排序、堆排序、冒泡排序等屬于比較排序。在排序的最終結果里，元素之間的次序依賴于它們之間的比較。每個數都必須和其他數進行比較，才能確定自己的位置。在冒泡排序之類的排序中，問題規(guī)模為n，又因為需要比較n次，所以平均時間復雜度為O(n2)。在歸并排序、快速排序之類的排序中，問題規(guī)模通過分治法消減為logN次，所以時間復雜度平均O(nlogn)。比較排序的優(yōu)勢是，適用于各種規(guī)模的數據，也不在乎數據的分布，都能進行排序。可以說，比較排序適用于一切需要排序的情況。計數排序、基數排序、桶排序則屬于非比較排序。非比較排序是通過確定每個元素之前，應該有多少個元素來排序。針對數組arr，計算arr[i]之前有多少個元素，則唯一確定了arr[i]在排序后數組中的位置。非比較排序只要確定每個元素之前的已有的元素個數即可，所有一次遍歷即可解決。算法時間復雜度O(n)。非比較排序時間復雜度底，但由于非比較排序需要占用空間來確定唯一位置。所以對數據規(guī)模和數據分布有一定的要求。

冒泡排序是一種簡單的排序算法。它重復地走訪過要排序的數列，一次比較兩個元素，如果它們的順序錯誤就把它們交換過來。走訪數列的工作是重復地進行直到沒有再需要交換，也就是說該數列已經排序完成。這個算法的名字由來是因為越小的元素會經由交換慢慢“浮”到數列的頂端。

比較相鄰的元素。如果第一個比第二個大，就交換它們兩個；

對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最后一對，這樣在最后的元素應該會是最大的數；

針對所有的元素重復以上的步驟，除了最后一個；

重復步驟1~3，直到排序完成。

/**
 * 選擇排序
 * @param array
 * @return
 */
public static int[] selectionSort(int[] array) {
if (array.length == 0)
return array;
for (int i = 0; i < array.length; i  ) {
int minIndex = i;
for (int j = i; j < array.length; j  ) {
if (array[j] < array[minIndex]) //找到最小的數
minIndex = j; //將最小數的索引保存
}
int temp = array[minIndex];
array[minIndex] = array[i];
array[i] = temp;
}
return array;
}

• 一般來說，插入排序都采用in-place在數組上實現。具體算法描述如下：
• 從第一個元素開始，該元素可以認為已經被排序；
• 取出下一個元素，在已經排序的元素序列中從后向前掃描；
• 如果該元素（已排序）大于新元素，將該元素移到下一位置；
• 重復步驟3，直到找到已排序的元素小于或者等于新元素的位置；
• 將新元素插入到該位置后；
• 重復步驟2~5。

/**
 * 希爾排序
 *
 * @param array
 * @return
 */
public static int[] ShellSort(int[] array) {
int len = array.length;
int temp, gap = len / 2;
while (gap > 0) {
for (int i = gap; i < len; i  ) {
temp = array[i];
int preIndex = i - gap;
while (preIndex >= 0 && array[preIndex] > temp) {
array[preIndex   gap] = array[preIndex];
preIndex -= gap;
}
array[preIndex   gap] = temp;
}
gap /= 2;
}
return array;
}