- 冒泡排序 時間復(fù)雜度 O(n2)，空間復(fù)雜度 O(1)
- 選擇排序 時間復(fù)雜度 O(n2)癌压，空間復(fù)雜度 O(1)
- 插入排序 時間復(fù)雜度 O(n2)仰泻，空間復(fù)雜度 O(1)
- 希爾排序 時間復(fù)雜度 O(nlogn)，空間復(fù)雜度 O(1)
- 歸并排序 時間復(fù)雜度 O(nlogn)措拇，空間復(fù)雜度 O(n)
- 快速排序 時間復(fù)雜度 O(nlogn)我纪，空間復(fù)雜度 O(logn)
- 堆排序
- 計數(shù)排序
- 桶排序
- 基數(shù)排序
冒泡排序
兩兩比較元素，使值較小的元素不斷前移丐吓，值較大的元素不斷后移浅悉，每次循環(huán)都能找出當(dāng)前區(qū)間中值最大的元素，且循環(huán)結(jié)束時值最大的元素位于當(dāng)前區(qū)間的最右端券犁。
public static void bubbleSort(int[] array) {
for (int i = 0; i < array.length; i++) {
/*循環(huán)區(qū)間[0, len-i)*/
for (int j = 0; j < array.length - 1 - i; j++) {
if (array[j] > array[j+1]) {
int temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
}
}
選擇排序
兩兩比較元素术健，找出當(dāng)前區(qū)間中值最小的元素，將該元素和當(dāng)前區(qū)間頭部元素互換粘衬，以此類推荞估，直到所有元素均排序完畢。
public static void selectionSort(int[] array) {
for (int i = 0; i < array.length; i++) {
int index = i;
/*當(dāng)前區(qū)間[i, len)*/
for (int j = i; j < array.length; j++) {
if (array[j] < array[index]) {
index = j;
}
}
/*將當(dāng)前區(qū)間中最小元素和區(qū)間頭部元素互換*/
int temp = array[i];
array[i] = array[index];
array[index] = temp;
}
}
插入排序
在原數(shù)組上構(gòu)建一個有序序列稚新，初始時將a[0]視為有序序列勘伺，對于a[i]，從右到左掃描區(qū)間[o, i)褂删，找到a[i]合適的插入位置飞醉，然后將區(qū)間[o, i)中大于a[i]的元素都后移一位，最后將a[i]插入到區(qū)間中屯阀，以此類推缅帘，直到所有元素均排序完畢。
public static void insertionSort(int[] array) {
for (int i = 1; i < array.length; i++) {
int current = array[i], j;
/*若current<array[j], 則array[j]后移一位*/
for (j = i-1; j >= 0; j--) {
if (current < array[j]) {
array[j+1] = array[j];
} else {
break;
}
}
array[j+1] = current;
}
}
希爾排序
希爾排序是插入排序的改進(jìn)算法难衰，不同點(diǎn)在于希爾排序會優(yōu)先比較距離較遠(yuǎn)的元素钦无。希爾排序也叫縮小增量排序，首先需要確定增量和縮小增量的模式盖袭，一般采用增量gap = length / 2失暂，縮小增量gap = gap / 2彼宠，從而得到增量序列{n/2, (n/2)/2 … 1}。增量序列的長度k表示算法需要對數(shù)組進(jìn)行排序的次數(shù)趣席，增量值gap表示每次排序需將數(shù)組劃分成gap組兵志，分組提取元素時的步長為gap，對于每個分組宣肚，按照插入排序的方式進(jìn)行處理想罕。
public static void ShellSort(int[] array) {
/*確定增量*/
int gap = array.length / 2;
while (gap > 0) {
/*分成gap組, 當(dāng)前指向分組中第二個元素*/
for (int i = gap; i < array.length; i++) {
int current = array[i], j;
/*若current<array[j], 則array[j]后移一位*/
for (j = i-gap; j >= 0; j = j-gap) {
if (current < array[j]) {
array[j+gap] = array[j];
} else {
break;
}
}
array[j+gap] = current;
}
/*確定縮小增量*/
gap /= 2;
}
}
歸并排序
（分治法）以二路歸并排序?yàn)槔紫葘?dāng)前數(shù)組分成兩個子串，遞歸分割子串，直到每個子串中只包含一個元素娶聘，這時可以認(rèn)為子串內(nèi)部是有序的众弓，然后將子串兩兩合并客税，使子串間有序，不斷合并有序的子串，最終得到一個有序的數(shù)組。
public static int[] MergeSort(int[] array) {
/*遞歸終止條件*/
if (array.length < 2) {
return array;
}
int mid = array.length / 2;
/*2-路歸并, 將array分成兩段*/
int[] left = Arrays.copyOfRange(array, 0, mid);
int[] right = Arrays.copyOfRange(array, mid, array.length);
/*使兩個子段內(nèi)部有序*/
/*合并內(nèi)部有序的子串, 使整體有序*/
return merge(MergeSort(left), MergeSort(right));
}
/**
* 將兩段排序好的數(shù)組結(jié)合成一個排序數(shù)組
* @param left
* @param right
*/
public static int[] merge(int[] left, int[] right) {
int[] res = new int[left.length + right.length];
for (int index = 0,i = 0,j = 0; index < res.length; index++) {
/*left遍歷完*/
if (i >= left.length) {
res[index] = right[j++];
} else if (j >= right.length) {
res[index] = left[i++];
} else if (left[i] < right[j]) {
res[index] = left[i++];
} else {
res[index] = right[j++];
}
}
return res;
}
快速排序
（分治法）從當(dāng)前數(shù)組中挑出一個元素作為基準(zhǔn)框产，將小于基準(zhǔn)的元素放在基準(zhǔn)的左邊，大于基準(zhǔn)的元素放在基準(zhǔn)右邊错洁，從而得到基準(zhǔn)的左子串和右子串秉宿，然后按照上述規(guī)則遞歸處理左子串和右子串，最終得到一個有序的數(shù)組屯碴。
public static void QuickSort(int[] array, int low, int high) {
/*遞歸終止條件, 如果子串中只有一個元素則不處理*/
if (low >= high) {
return;
}
int i = low, j = high, pivot = array[low], temp;
while (i < j) {
/*必須先處理j, 保證該輪結(jié)束后是較小數(shù)和基準(zhǔn)數(shù)互換*/
while (pivot <= array[j] && i < j) {
j--;
}
while (pivot >= array[i] && i < j) {
i++;
}
/*互換array[i]和array[j], 使數(shù)列相對有序*/
if (i < j) {
temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
/*基準(zhǔn)數(shù)和ij互換*/
array[low] = array[i];
array[i] = pivot;
/*遞歸調(diào)用左半數(shù)組*/
QuickSort(array, low, j-1);
//遞歸調(diào)用右半數(shù)組
QuickSort(array, j+1, high);
}
堆排序
堆積是一個近似完全二叉樹的結(jié)構(gòu)描睦，并同時滿足堆積的性質(zhì)：即子結(jié)點(diǎn)的鍵值或索引總是小于（或者大于）它的父節(jié)點(diǎn)。
首先根據(jù)數(shù)組構(gòu)建一個無序的完全二叉樹导而，根據(jù)堆積的性質(zhì)將二叉樹轉(zhuǎn)換成堆積忱叭，轉(zhuǎn)換完成后根節(jié)點(diǎn)即為當(dāng)前數(shù)組中的最大值，將根節(jié)點(diǎn)與樹中最后一個葉子節(jié)點(diǎn)互換今艺，并刪除該葉子節(jié)點(diǎn)韵丑，此時完全二叉樹又變成了無序狀態(tài)，按照上述規(guī)則類推虚缎，直到樹為空埂息。
(10條消息) 超詳細(xì)十大經(jīng)典排序算法總結(jié)（java代碼）c或者cpp的也可以明白Top_Spirit的博客-CSDN博客排序算法
