一肾档、綜述
二咨跌、選擇排序
思想：
首先找到數(shù)組中最小的元素沪么，其次將它和數(shù)組的第一個元素交換位置（如果第一個元素是最小元素就和自己交換位置）。再次锌半，在剩余的元素中找到最小元素禽车，將它和數(shù)組的第二個元素交換位置。如此往復直到整個數(shù)組排序刊殉。
時間復雜度：
- 對于長度為N的數(shù)組哭当，選擇排序需要大約N2/2次比較以及N次交換
- 運行時間和數(shù)組無關(guān)。無論數(shù)組是亂序冗澈、部分有序或者全部有序钦勘，該方法都會進行大約N2/2次比較以及N次交換
- 數(shù)據(jù)移動是最少的。這是其他算法所不能達到的亚亲。
實現(xiàn)
public static void selectSort(int[] array, int start) {
for (int i = start; i < array.length; i++) {
int minIndex = min(array, i);
if (i != minIndex) {
swap(array, i, minIndex);
}
}
}
三彻采、插入排序
思想：
和選擇排序一樣，當前索引左邊的所有元素都是有序的捌归，但是她們的最終位置并不確定肛响，為了給更小的元素騰出位置，他們可能會被移動惜索。和選擇排序不同的是特笋，插入排序的時間復雜度取決于數(shù)組的初始順序。對一個很大但其中的元素已經(jīng)有序（或接近有序）的數(shù)組進行排序會比對隨機順序的數(shù)組或者逆序數(shù)組進行排序要快得多巾兆。
時間復雜度
- 對于隨機無重復長度為N的數(shù)組猎物，平均情況下需要N2/4次比較以及N2/4次交換。最壞情況下需要N2/2 次比較以及N2/2次交換角塑。最好情況下需要N-1次比較以及0次交換蔫磨。
- 插入排序需要交換元素的次數(shù)和原始數(shù)組中逆序?qū)Φ臄?shù)目相同。
適用情況
插入排序?qū)Σ糠钟行虻臄?shù)組十分高效圃伶，也很適合小規(guī)模數(shù)組堤如。
實現(xiàn)
public static void insert(int[] array) {
for (int i = 1; i < array.length; i++) {
if (array[i] < array[i - 1]) {
int temp = array[i];
int j = 0;
for (j = i - 1; j >= 0 && array[j] > temp; j--) {
array[j + 1] = array[j];
}
array[j + 1] = temp;
}
}
}
四蒲列、希爾排序
思想：
基于插入排序進行改進，對于大規(guī)模亂序數(shù)組插入排序很慢搀罢，因為它只會交換相鄰的元素蝗岖，因此元素只能一點一點從數(shù)組的一端移動到另一端。希爾排序為了加快速度改進了插入排序榔至，交換不相鄰元素以對數(shù)組局部進行排序剪侮，最終用插入排序?qū)植坑行虻臄?shù)組進行排序。希爾排序的思想是使數(shù)組中任意間隔為h的元素都是有序的洛退。這樣的數(shù)組成為h有序數(shù)組瓣俯。換句話說一個h有序數(shù)組是h個相互獨立的有序數(shù)組編織在一起形成的數(shù)組。
時間復雜度
- 希爾排序的時間復雜度達不到平方級別兵怯。
- 使用遞增序列1,4,13,40,121（3h+1）的希爾排序所需比較次數(shù)不會超過N的若干倍乘以遞增序列長度
適用情況
適用于大型數(shù)組彩匕，并且數(shù)組越大，優(yōu)勢越大媒区。
實現(xiàn)
public static void shellSort(int[] array, int d) {
for (int i = 0; i + d < array.length; i++) {
if (array[i] > array[i + d]) {
int temp = array[i + d];
int j;
for (j = i; j >= 0 && array[j] > temp; j -= d) {
array[j + d] = array[j];
}
array[j + d] = temp;
}
}
if (d != 1) {
shellSort(array, d / 2);
}
}
五驼仪、冒泡排序
思想
- 比較相鄰的元素。如果第一個比第二個大袜漩，就交換他們兩個绪爸。
- 對每一對相鄰元素作同樣的工作，從開始第一對到結(jié)尾的最后一對宙攻。在這一點奠货，最后的元素應(yīng)該會是最大的數(shù)。
- 針對所有的元素重復以上的步驟座掘，除了最后一個递惋。
- 持續(xù)每次對越來越少的元素重復上面的步驟，直到?jīng)]有任何一對數(shù)字需要比較溢陪。
時間復雜度
實現(xiàn)
public class BubbleSort
{
public void sort(int[] a)
{
int temp = 0;
for (int i = a.length - 1; i > 0; --i)
{
for (int j = 0; j < i; ++j)
{
if (a[j + 1] < a[j])
{
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
}
}
六萍虽、歸并排序
思想
將兩個有序的數(shù)組歸并成一個更大的數(shù)組。首先將數(shù)組分為兩半分別進行排序形真，然后將結(jié)果歸并起來杉编。歸并排序保證任意長度為N的數(shù)組排序所需時間復雜度和NlogN成正比，主要缺點是空間復雜度和長度N成正比咆霜。
時間復雜度
- 歸并排序是一種漸進最優(yōu)的基于比較的排序算法邓馒，時間復雜度和原始數(shù)組初始順序無關(guān)，都為O(NlogN)裕便，空間復雜度為O(N)绒净。
實現(xiàn)
public static void merge(int[] array, int lo, int middle, int hi) {
int i = lo;
int j = middle + 1;
int[] temp = new int[hi - lo + 1];
for (int k = lo; k <= hi; k++) {
temp[k - lo] = array[k];
}
int index = lo;
while (i <= middle && j <= hi) {
if (temp[i - lo] > temp[j - lo]) {
array[index++] = temp[j - lo];
j++;
} else {
array[index++] = temp[i - lo];
i++;
}
}
while (i <= middle) {
array[index++] = temp[i - lo];
i++;
}
while (j <= hi) {
array[index++] = temp[j - lo];
j++;
}
}
public static void mergeSort(int[] array, int lo, int hi) {
if (lo >= hi) {
return;
}
int mid = lo + (hi - lo) / 2;
mergeSort(array, 0, mid);
mergeSort(array, mid + 1, hi);
merge(array, lo, mid, hi);
}
七见咒、快速排序
思想
快速排序是一種分治的排序算法偿衰。它將一個數(shù)組分成兩個子數(shù)組，將兩部分獨立的排序∠卖幔快速排序關(guān)鍵點在于實現(xiàn)切分方法缤言，一般取a[low]為切分元素，然后我們先從右往左掃描數(shù)組视事，找到小于切分元素的元素胆萧，并和切分元素交換位置；之后在從左向右掃描元素俐东，找到大于切分元素的元素跌穗，并和切分元素交換位置。如此繼續(xù)我們便可以保證切分元素左邊的元素都小于切分元素虏辫，切分元素右邊的元素都大于切分元素蚌吸。
時間復雜度
- 時間復雜度和數(shù)組初始順序有關(guān)，對于隨機順序的數(shù)組來說砌庄，快速排序可以實現(xiàn)O(NlogN)羹唠，但對于有序數(shù)組而言，快速排序的時間復雜度為O(N^2)娄昆。
- 快速排序比較次數(shù)很少佩微。
實現(xiàn)
public static void qSort(int[] array, int low, int hi) {
if (low > hi) {
return;
}
int key = array[low];
int i = low;
int j = hi;
while (i < j) {
while (i < j && array[j] >= key) {
j--;
}
if (i < j) {
swap(array, i, j);
}
while (i < j && array[i] <= key) {
i++;
}
if (i < j) {
swap(array, i, j);
}
}
qSort(array, low, i - 1);
qSort(array, i + 1, hi);
}
