本文記錄幾個(gè)基礎(chǔ)的排序算法。排序算法分為插入排序悦冀、交換排序、選擇排序等幾大類睛琳。
插入排序
1. 直接插入排序 O(n2)
直接插入排序思路：將數(shù)組分為有序區(qū)和無序區(qū)盒蟆，每次插入都在無序區(qū)中取一個(gè)元素，插入到有序區(qū)合適的位置师骗。排序開始時(shí)历等，默認(rèn)第一個(gè)元素有序，隨后取第2 3 ... 個(gè)元素與有序區(qū)的元素進(jìn)行對(duì)比辟癌，插入寒屯。
原始數(shù)組：
5, 2, 6, 7, 1, 3,
排序過程：
當(dāng)前是第2個(gè)元素2插入：2, 5, 6, 7, 1, 3,
當(dāng)前是第3個(gè)元素6插入：2, 5, 6, 7, 1, 3,
當(dāng)前是第4個(gè)元素7插入：2, 5, 6, 7, 1, 3,
當(dāng)前是第5個(gè)元素1插入：1, 2, 5, 6, 7, 3,
當(dāng)前是第6個(gè)元素3插入：1, 2, 3, 5, 6, 7,
排序數(shù)組
1, 2, 3, 5, 6, 7,
算法如下：
public static void insertSort(int[] numbers){
int insert;
for (int i = 1; i < numbers.length; i++){
//System.out.print("當(dāng)前是第" + (i+1) + "個(gè)元素" + numbers[i] +"插入：");
insert = numbers[i];
int j = i-1; //有序部分的個(gè)數(shù)
while(j>= 0 && numbers[j] > insert){ //有序部分從右到左比較，若大于插入元素黍少，則后移
numbers[j+1] = numbers[j]; //元素后移
j--;
}
numbers[j+1] = insert; //在需要的位置插入
//fore(numbers);
}
}
2. 折半插入排序
折半插入排序的思路和直接插入排序類似：將數(shù)組分為有序區(qū)和無序區(qū)寡夹，每次插入都在無序區(qū)中取一個(gè)元素，然后通過折半查找的方式厂置，找出插入的位置是在左半?yún)^(qū)還是在右半?yún)^(qū)菩掏，找到插入的半?yún)^(qū)后，插入到有序區(qū)合適的位置昵济。排序開始時(shí)智绸，默認(rèn)第一個(gè)元素有序，隨后取第2 3 ... 個(gè)元素與有序區(qū)的元素進(jìn)行對(duì)比访忿，插入瞧栗。
public static void insertSort2(int[] numbers) {
int low, high, mid;
int insert;
for (int i = 1; i < numbers.length; i++) {
//System.out.print("當(dāng)前是第" + (i+1) + "個(gè)元素" + numbers[i] +"插入：");
insert = numbers[i];
low = 0;
high = i - 1;
while (low <= high) { //在有序區(qū)中，折半查找插入的位置
mid = (low + high) / 2;
if (insert < numbers[mid]) { //插入點(diǎn)在左半?yún)^(qū)醉顽，設(shè)置high為中點(diǎn)的左邊
high = mid - 1;
} else //插入點(diǎn)在右半?yún)^(qū)沼溜，設(shè)置high為中點(diǎn)的右邊
low = mid + 1;
}
for (int j = i-1; j>=high+1; j--){
numbers[j + 1] = numbers[j]; //元素后移
}
numbers[high + 1] = insert; //在需要的位置插入
// fore(numbers);
}
}
3. 希爾排序 O(n1.3)
希爾排序?qū)嶋H上是一種分組插入的方法，思想：選定一個(gè)小于n的整數(shù)d1游添，作為一個(gè)增量系草，將距離間隔為d的元素分組，然后在組內(nèi)進(jìn)行直接插入排序唆涝；然后取第二個(gè)增量d2<d1找都，分組，組內(nèi)插入排序廊酣；直到增量d=1能耻，分組，組內(nèi)直接插入排序，結(jié)束晓猛。
關(guān)于d的選取饿幅，這里建議d1 = n / 2, di+1=di / 2。
原始數(shù)組：
5, 2, 6, 7, 1, 3,
排序過程：
增量gap=3 結(jié)果：5, 1, 3, 7, 2, 6,
增量gap=1 結(jié)果：1, 2, 3, 5, 6, 7,
排序數(shù)組
1, 2, 3, 5, 6, 7,
算法：
public static void shellSort(int[] numbers) {
int gap;
gap = numbers.length / 2; //增量初始值
while (gap > 0) {
for (int i = gap; i < numbers.length; i++) { //相隔gap的元素組進(jìn)行直接插入排序
int temp = numbers[i];
int j = i - gap;
while (j >= 0 && temp < numbers[j]) { //組內(nèi)移動(dòng)
numbers[j + gap] = numbers[j];
j = j - gap;
}
numbers[j + gap] = temp;
}
// System.out.print("增量gap=" + gap + " 結(jié)果：");
// fore(numbers);
gap = gap / 2;
}
}
交換排序
1. 冒泡排序 O(n2)
冒泡排序戒职，也稱氣泡排序栗恩，對(duì)每兩兩相鄰的關(guān)鍵字進(jìn)行比較，使得關(guān)鍵字較大的排到數(shù)組的后邊洪燥。一次排序后磕秤，得到的結(jié)果就將目前最大的元素放置到數(shù)組的后部，不斷重復(fù)該過程捧韵，直到所有元素有序市咆。（也有部分冒泡排序每次將最小的部分排列到數(shù)組最前端，這兩者思想都是一致的）
原始數(shù)組：
5, 2, 6, 7, 1, 3,
第1趟排序：
2, 5, 6, 7, 1, 3,
2, 5, 6, 1, 7, 3,
2, 5, 6, 1, 3, 7,
第2趟排序：
2, 5, 1, 6, 3, 7,
2, 5, 1, 3, 6, 7,
第3趟排序：
2, 1, 5, 3, 6, 7,
2, 1, 3, 5, 6, 7,
第4趟排序：
1, 2, 3, 5, 6, 7,
第5趟排序：
第6趟排序：
排序數(shù)組
1, 2, 3, 5, 6, 7,
public static void bubbleSort(int[] a){
int temp;
for(int i=0;i<a.length;i++){
//System.out.println("第"+ (i+1) + "趟排序：" );
for(int j=0;j<a.length-i-1;j++){
if(a[j]>a[j+1]){
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
//fore(a); //輸出
}
}
}
}
可以發(fā)現(xiàn)再来，在第5趟排序中蒙兰，根本就沒有交換元素，那么就表明所有元素已經(jīng)按順序排列其弊，那么就沒比較進(jìn)行第六趟的比較癞己，因此做如下優(yōu)化：通過一個(gè)boolean判斷是否發(fā)生交換，如果沒有發(fā)生交換梭伐，則結(jié)束算法痹雅。
public static void bubbleSort2(int[] a){
int temp;
boolean exchange; //是否做交換
for(int i=0;i<a.length;i++){
exchange = false;
System.out.println("第"+ (i+1) + "趟排序：" );
for(int j=0;j<a.length-i-1;j++){
if(a[j]>a[j+1]){
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
exchange = true;
fore(a);
}
}
if (!exchange){ //本趟沒有發(fā)生交換，中途結(jié)束算法
return;
}
}
}
2. 快速排序 O(nlog2n)
快速排序的思想：
- 選擇一個(gè)基準(zhǔn)base糊识，把小于base的數(shù)值移到base左邊绩社，把大于base的數(shù)值移到右邊。（此時(shí)數(shù)組中會(huì)分為小于base的左部赂苗，和大于base的右部）
- 遞歸將小于base和大于base的兩部分重復(fù)第一步愉耙，直到遞歸完成。
代碼實(shí)現(xiàn)：
public static void quickSort2(int[] numbers, int start, int end) {
int base = numbers[start];
int i = start, j = end;
int temp; //臨時(shí)存儲(chǔ)拌滋，用作交換
do {
while (numbers[i] < base && i < end) { //i從左到右找到第一個(gè)大于等于基準(zhǔn)的值
i++;
}
while (numbers[j] > base && j > start) { //j從右到左找到第一個(gè)小于等于基準(zhǔn)的值
j--;
}
if (i <= j) { //左右兩側(cè)都找到后朴沿，交換其位置，并將i后移败砂，j左移
temp = numbers[i];
numbers[i] = numbers[j];
numbers[j] = temp;
i++;
j--;
}
} while (i <= j);
if (start < j) {
quickSort2(numbers, start, j); //遞歸小于base的左部
}
if (end > i) {
quickSort2(numbers, i, end); //遞歸大于base的右部
}
}
算法分析：
由于快速排序的思想分為左右兩部分遞歸赌渣，可以快速記憶時(shí)間復(fù)雜度為O(nlog2n)
選擇排序
1. 直接選擇排序 O(n2)
直接選擇排序思想：在當(dāng)前無序區(qū)中選擇最小的關(guān)鍵字與無序區(qū)的第一個(gè)元素進(jìn)行交換，直到n-1次排序后昌犹，整個(gè)數(shù)組遞增有序坚芜。
原始數(shù)組：
5, 2, 6, 7, 1, 3,
排序過程：
第1次排序：1, 2, 6, 7, 5, 3,
第2次排序：1, 2, 6, 7, 5, 3,
第3次排序：1, 2, 3, 7, 5, 6,
第4次排序：1, 2, 3, 5, 7, 6,
第5次排序：1, 2, 3, 5, 6, 7,
排序數(shù)組
1, 2, 3, 5, 6, 7,
算法：
public static void selectSort(int[] numbers) {
for (int i = 0; i < numbers.length - 1; i++) { //第i次排序
int k = i; //標(biāo)記最小值的位置
for (int j = i + 1; j < numbers.length; j++) { //在無序區(qū)中選擇最小的key
if (numbers[j] < numbers[k]) {
k = j;
}
}
if (k != i) { //交換
int temp = numbers[i];
numbers[i] = numbers[k];
numbers[k] = temp;
}
System.out.print("第" + (i + 1) + "次排序：");
fore(numbers);
}
}
2. 堆排序
堆排序是一種樹形選擇排序方法，在排序時(shí)將數(shù)組看成是一顆完全二叉樹的順序存儲(chǔ)結(jié)構(gòu)斜姥，利用完全二叉樹中雙親結(jié)點(diǎn)和孩子節(jié)點(diǎn)之間的內(nèi)在聯(lián)系鸿竖，在當(dāng)前無序區(qū)中選擇關(guān)鍵字最大的元素沧竟。
堆（完全二叉樹）的定義n個(gè)關(guān)鍵字的序列K1, K2... Kn，當(dāng)且僅當(dāng)該序列滿足以下屬性：
- Ki <= K2i且 Ki <= K2i+1 ：小根堆
或者： - Ki >= K2i且 Ki >= K2i+1 ：大根堆
算法思想：堆排序的關(guān)鍵在于構(gòu)造初始堆缚忧，假設(shè)完全二叉樹的某一個(gè)節(jié)點(diǎn)i悟泵，它的左右子樹都是堆，這時(shí)就需要將R[i]和R[2i]搔谴、R[2i + 1]之間的最大者進(jìn)行比較魁袜，如果R[i]較小，那么就將其與較大的孩子進(jìn)行交換敦第，這個(gè)交換過程中，可能會(huì)導(dǎo)致下一級(jí)的堆被破壞店量，因此需要用上述的方法遞歸構(gòu)造下一級(jí)堆芜果。
調(diào)整堆算法：
/**
* 調(diào)整堆算法
*
* @param numbers 數(shù)組
* @param low 要調(diào)整的節(jié)點(diǎn)
* @param high 最后一個(gè)節(jié)點(diǎn)的位置
*/
public static void sift(int[] numbers, int low, int high) {
int i = low, j = 2 * i; //j是i的左節(jié)點(diǎn)
int temp = numbers[i];
while (j <= high) {
if (j < high && numbers[j] < numbers[j + 1]) { //如果右孩子較大，則將j指向右孩子
j++;
}
if (temp < numbers[j]) {
numbers[i] = numbers[j]; //將numbers[j]調(diào)整到雙親節(jié)點(diǎn)上
i = j;
j = 2 * i; //修改i融师、j的值
} else
break;
}
numbers[i] = temp; //被篩選的節(jié)點(diǎn)（要調(diào)整的節(jié)點(diǎn)）放置到最終位置
}
在初始堆構(gòu)造好后右钾，根節(jié)點(diǎn)是最大的關(guān)鍵字節(jié)點(diǎn)，將其放置到序列的最后（和最后一個(gè)葉子節(jié)點(diǎn)交換）旱爆，由于最大元素已經(jīng)歸為舀射，待排序的元素會(huì)減少一個(gè)，根節(jié)點(diǎn)也改變了怀伦，就需要重新調(diào)用sift算法調(diào)整堆脆烟；然后重復(fù)上述步驟，直到完全二叉樹只剩最后一個(gè)根為止房待。
原始數(shù)組：
5, 2, 6, 7, 1, 3,
排序過程：
調(diào)整堆：5, 2, 6, 7, 1, 3,
調(diào)整堆：5, 7, 6, 2, 1, 3,
調(diào)整堆：7, 6, 5, 2, 1, 3,
初始堆完成：7, 6, 5, 2, 1, 3,
調(diào)整堆：6, 5, 3, 2, 1, 7,
調(diào)整堆：5, 3, 1, 2, 6, 7,
調(diào)整堆：3, 2, 1, 5, 6, 7,
調(diào)整堆：2, 1, 3, 5, 6, 7,
調(diào)整堆：1, 2, 3, 5, 6, 7,
排序數(shù)組
1, 2, 3, 5, 6, 7,
/**
* 堆排序
*
* @param numbers 數(shù)組
*/
public static void HeapSort(int[] numbers) {
int temp;
int n = numbers.length-1;
for (int i = n / 2; i >= 0; i--) { //構(gòu)造初始堆
sift(numbers, i, n);
}
System.out.print("初始堆完成：");
fore(numbers);
for (int i = n; i >= 1; i--) {
temp = numbers[0]; //將最后一個(gè)元素和當(dāng)前區(qū)內(nèi)的第一個(gè)節(jié)點(diǎn)交換
numbers[0] = numbers[i];
numbers[i] = temp;
sift(numbers, 0, i - 1); //得到i-1個(gè)節(jié)點(diǎn)的堆
}
}
