1 簡(jiǎn)單排序算法
1.1 冒泡排序
排序原理
比較相鄰兩數(shù)據(jù)珍语，如果數(shù)據(jù)反序，則交換兩數(shù)據(jù)的位置迹辐；指針后移，繼續(xù)比較步做，直到未排序隊(duì)列尾部桂敛。每一趟將待排序隊(duì)列最大或最小數(shù)據(jù)冒泡至待排序隊(duì)列尾部缀遍。最終達(dá)到完全有序。
代碼實(shí)現(xiàn)
/**
* 冒泡排序
*/
public static void bubbleSort(int[] array) {
for (int i = array.length - 1; i > 0; i--) {
for (int j = 0; j < i; j++) {
if (array[j] > array[j + 1]) {
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
}
算法效率
每一輪比較將有一項(xiàng)數(shù)據(jù)排好序杭朱，因此下一輪比較次數(shù)將減一
比較次數(shù)= (N-1) + (N-2) + ... + 2 + 1 = N(N-1)/2 即 O(N2)
大約有一半次數(shù)會(huì)進(jìn)行數(shù)據(jù)交換
交換次數(shù)=((N-1) + (N-2) + ... + 2 + 1)/2 = N(N-1)/4 即 O(N2)
時(shí)間復(fù)雜度:O(N2)
1.2 選擇排序
排序原理
每次遍歷從無(wú)序隊(duì)列中選擇最小數(shù)據(jù)將其放至無(wú)序隊(duì)列隊(duì)首阅仔。
代碼實(shí)現(xiàn)
/**
* 選擇排序
*/
public static void selectionSort(int[] array) {
for (int i = 0; i < array.length; i++) {
int minIndex = i;
for (int j = i + 1; j < array.length; j++) {
if (array[j] < array[minIndex]) {
minIndex = j;
}
}
if(minIndex != i){
int temp = array[i];
array[i] = array[minIndex];
array[minIndex] = temp;
}
}
}
算法效率
選擇排序與冒泡排序執(zhí)行了相同次數(shù)的比較
比較次數(shù)= (N-1) + (N-2) + ... + 2 + 1 = N(N-1)/2 即 O(N2)
但是交換次數(shù)減少至O(N)
交換次數(shù)= N 即 O(N)
時(shí)間復(fù)雜度:O(N2)
1.3 插入排序
排序原理
插入排序在遍歷時(shí)，遍歷數(shù)據(jù)左邊已經(jīng)有序弧械，將當(dāng)前數(shù)據(jù)插入左邊有序隊(duì)列中適當(dāng)位置八酒；遍歷完成時(shí)，整個(gè)隊(duì)列有序刃唐。
代碼實(shí)現(xiàn)
/**
* 插入排序
*/
public static void insertSort(int[] array) {
int value;
for (int i = 1; i < array.length; i++) {
value = array[i];
int j = i;
while (j > 0 && array[j - 1] > value) {
array[j] = array[j - 1];
j--;
}
array[j] = value;
}
}
算法效率
平均比較次數(shù)約為總的一半
比較次數(shù)= (1 + 2 + ... + (N-2) + (N-1))/2 = N(N-1)/4 即 O(N2)
復(fù)制與交換耗時(shí)不同羞迷，復(fù)制耗時(shí)更少界轩；復(fù)制次數(shù)約等同于比較次數(shù)
復(fù)制次數(shù)= N(N-1)/4 即 O(N2)
時(shí)間復(fù)雜度:O(N2)
總結(jié)
相對(duì)于隨機(jī)數(shù)據(jù),插入排序速度比冒泡排序快一倍，比選擇排序略快衔瓮。
2 復(fù)雜排序算法
2.1 歸并排序
排序原理
歸并排序算法將數(shù)據(jù)分為兩組耸棒，分別對(duì)每組數(shù)據(jù)排序，然后使用歸并算法报辱，歸并兩個(gè)有序數(shù)組与殃。對(duì)每個(gè)分組的排序則又可以使用歸并排序算法排序。
代碼實(shí)現(xiàn)
public class MergeSort {
/**
* 歸并排序算法
*/
public static void mergeSort(int[] sourceArray) {
int[] tempArray = new int[sourceArray.length];
mergeSort(sourceArray, tempArray, 0, sourceArray.length - 1);
}
private static void mergeSort(int[] sourceArray, int[] tempArray, int fromIndex, int lastIndex) {
if (fromIndex == lastIndex) {
return;
} else {
int midIndex = (fromIndex + lastIndex) / 2;
/* 對(duì)兩個(gè)子分組使用歸并排序 */
mergeSort(sourceArray, tempArray, fromIndex, midIndex);
mergeSort(sourceArray, tempArray, midIndex + 1, lastIndex);
/* 使用歸并算法將兩個(gè)有序子分組歸并為一個(gè)有序數(shù)組 */
merge(sourceArray, tempArray, fromIndex, midIndex, midIndex + 1, lastIndex);
}
}
private static void merge(int[] sourceArray, int[] tempArray, int firstFromIndex, int firstLastIndex,
int secondFromIndex, int secondLastIndex) {
int firstCountIndex = firstFromIndex;
int secondCountIndex = secondFromIndex;
int tempArrayIndex = 0;
while (firstCountIndex <= firstLastIndex && secondCountIndex <= secondLastIndex) {
if (sourceArray[firstCountIndex] < sourceArray[secondCountIndex]) {
tempArray[tempArrayIndex++] = sourceArray[firstCountIndex++];
} else if (sourceArray[firstCountIndex] > sourceArray[secondCountIndex]) {
tempArray[tempArrayIndex++] = sourceArray[secondCountIndex++];
} else {
tempArray[tempArrayIndex++] = sourceArray[firstCountIndex++];
tempArray[tempArrayIndex++] = sourceArray[secondCountIndex++];
}
}
while (firstCountIndex <= firstLastIndex) {
tempArray[tempArrayIndex++] = sourceArray[firstCountIndex++];
}
while (secondCountIndex <= secondLastIndex) {
tempArray[tempArrayIndex++] = sourceArray[secondCountIndex++];
}
for (int i = 0; i < tempArrayIndex; i++) {
sourceArray[firstFromIndex + i] = tempArray[i];
}
}
}
算法效率
時(shí)間復(fù)雜度:O(NlogN)
缺點(diǎn)
需要一個(gè)和待排序數(shù)組一樣大小的臨時(shí)存儲(chǔ)空間碍现。
2.2 希爾排序
排序原理
希爾排序又命增量排序幅疼。希爾排序通過(guò)加大插入排序中元素之間的間隔，并在這些有間隔的元素中進(jìn)行插入排序昼接，從而使數(shù)據(jù)項(xiàng)能大跨度的移動(dòng)爽篷。當(dāng)這些數(shù)據(jù)項(xiàng)排過(guò)一次序后，希爾排序算法減小數(shù)據(jù)項(xiàng)的間隔（即增量慢睡，通常用h表示）再進(jìn)行排序逐工，依此進(jìn)行下去，最后使用1-增量排序后漂辐，算法結(jié)束泪喊。
代碼實(shí)現(xiàn)
public class ShellSort {
public static void shellSort(int[] array) {
int h = 1;
/* 計(jì)算初始增量h */
while ((3 * h + 1) <= array.length) {
h = 3 * h + 1;
}
int temp;
/* 增量為0，排序結(jié)束 */
while (h > 0) {
/* 進(jìn)行h-增量排序 */
for (int i = h; i < array.length; i++) {
temp = array[i];
int j = i;
while (j > h - 1 && array[j - h] > temp) {
array[j] = array[j - h];
j -= h;
}
array[j] = temp;
}
/* 減少增量h */
h = (h - 1) / 3;
}
}
}
2.3 快速排序
排序原理
根據(jù)樞紐值髓涯，采用劃分算法袒啼，將數(shù)組分為左右兩個(gè)子數(shù)組，然后采用遞歸方式纬纪，分別對(duì)左右兩個(gè)子數(shù)組進(jìn)行排序蚓再。
代碼實(shí)現(xiàn)
public class QuickSort {
public static void quickSort(int[] array) {
quick(array, 0, array.length - 1);
}
private static void quick(int[] array, int left, int right) {
if (right <= left) {
return;
} else {
/* 計(jì)算劃分算法樞紐值 */
int pivot = (array[left] + array[right] + array[(left + right) / 2]) / 3;
/* 劃分算法劃分?jǐn)?shù)組，返回樞紐值位置 */
int parttion = partition(array, left, right, pivot);
/* 排序樞紐值左邊的子數(shù)組（遞歸調(diào)用快排） */
quick(array, left, parttion);
/* 排序樞紐值又邊的子數(shù)組（遞歸調(diào)用快排） */
quick(array, parttion + 1, right);
}
}
private static int partition(int[] array, int leftIndex, int rightIndex, int pivot) {
while (true) {
while (leftIndex < rightIndex && array[leftIndex] < pivot) {
leftIndex++;
}
while (rightIndex > leftIndex && array[rightIndex] > pivot) {
rightIndex--;
}
if (leftIndex >= rightIndex) {
break;
} else {
int temp = array[leftIndex];
array[leftIndex] = array[rightIndex];
array[rightIndex] = temp;
}
}
return array[leftIndex] > pivot ? leftIndex - 1 : leftIndex;
}
}
算法效率
時(shí)間復(fù)雜度:O(NlogN)
2.4 堆排序
2.4.1 什么是堆
堆的特性
①堆是完全二叉樹包各，除了樹的最后一層節(jié)點(diǎn)不需要是滿的摘仅，其它每一層從左到又都完全是滿的。
②堆中每一個(gè)節(jié)點(diǎn)關(guān)鍵字都大于（或等于）這個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)的關(guān)鍵字问畅。
③堆常常使用數(shù)組實(shí)現(xiàn)(由于是完全二叉樹娃属，數(shù)組不存在“空洞”)。
移除remove
移除是指刪除關(guān)鍵字最大的節(jié)點(diǎn)按声，這個(gè)節(jié)點(diǎn)總是根節(jié)點(diǎn)膳犹，其在數(shù)組中的索引為0。
一旦移除根節(jié)點(diǎn)签则，數(shù)組出現(xiàn)“空洞”(即數(shù)組索引為0的位置)须床，樹不再是完全二叉樹，因此需要填補(bǔ)渐裂，使其重新成為完全二叉樹豺旬。步驟如下：
①移除根钠惩。
②將最后一個(gè)節(jié)點(diǎn)(即數(shù)組中最后一個(gè)節(jié)點(diǎn))移到根的位置。
③向下篩選這個(gè)節(jié)點(diǎn)族阅，直到它處于一個(gè)大于它的節(jié)點(diǎn)之下篓跛，小于它的節(jié)點(diǎn)之上。
<p style="color:red">注意：篩選過(guò)程中坦刀，該節(jié)點(diǎn)需與較大子節(jié)點(diǎn)進(jìn)行交換愧沟。否則將使較小子節(jié)點(diǎn)成為較大子節(jié)點(diǎn)的父節(jié)點(diǎn)。</p>
插入insert
插入采用向上篩選方式：
①將節(jié)點(diǎn)插入堆的最后鲤遥，即數(shù)組的最后沐寺。
②與父節(jié)點(diǎn)比較，如果大于父節(jié)點(diǎn)則互換位置盖奈，直至節(jié)點(diǎn)出于一個(gè)大于它的父節(jié)點(diǎn)之下或成為根節(jié)點(diǎn)混坞。
基于數(shù)組的堆的代碼實(shí)現(xiàn)
在數(shù)組中，如果一個(gè)節(jié)點(diǎn)的索引為x钢坦，則
父節(jié)點(diǎn)索引為(x-1)/2
左子節(jié)點(diǎn)索引為2x+1
右子節(jié)點(diǎn)索引為2x+2
public class Heap {
private int[] heapArray;
private int count;
public Heap(int[] heapArray, int count) {
this.heapArray = heapArray;
this.count = count;
}
public void insert(int num) {
heapArray[count] = num;
trickleUp(count++);
}
public int remove() {
int returnVal = heapArray[0];
heapArray[0] = heapArray[--count];
trickleDown(0);
return returnVal;
}
/**
* 向上篩選
*/
public void trickleUp(int index) {
int parent = (index - 1) / 2;
int indexVal = heapArray[index];
while (index > 0 && heapArray[parent] < indexVal) {
heapArray[index] = heapArray[parent];
index = parent;
parent = (index - 1) / 2;
}
heapArray[index] = indexVal;
}
/**
* 向下篩選
*/
public void trickleDown(int index) {
int largerChildIndex;
int indexVal = heapArray[index];
int leftChildIndex = 2 * index + 1;
int rightChildIndex = leftChildIndex + 1;
while (leftChildIndex < count) {
if (rightChildIndex < count && heapArray[rightChildIndex] > heapArray[leftChildIndex]) {
largerChildIndex = rightChildIndex;
} else {
largerChildIndex = leftChildIndex;
}
if (indexVal > heapArray[largerChildIndex]) {
break;
} else {
heapArray[index] = heapArray[largerChildIndex];
index = largerChildIndex;
leftChildIndex = 2 * index + 1;
rightChildIndex = leftChildIndex + 1;
}
}
heapArray[index] = indexVal;
}
}
2.4.2 堆排序
排序原理
利用堆的特性究孕，調(diào)用insert方法，將待排序數(shù)組插入堆中爹凹，再調(diào)用remove方法厨诸，將數(shù)據(jù)取出，即完成排序逛万。
代碼實(shí)現(xiàn)
public class HeapSort {
public static void heapSort(int[] array) {
Heap heap = new Heap(new int[array.length], 0);
for (int i = 0; i < array.length; i++) {
heap.insert(array[i]);
}
for (int j = array.length - 1; j >= 0; j--) {
array[j] = heap.remove();
}
}
}
<p style="color:red">缺點(diǎn)：這種方式需要額外一個(gè)數(shù)組生成一個(gè)和待排序數(shù)組一樣大小的臨時(shí)空間泳猬。</p>
<label style="color:red">改進(jìn)方式：</label>將待排序數(shù)組看做是一個(gè)堆的數(shù)組表示，堆所有非葉子節(jié)點(diǎn)使用向下篩選trickleDown方法,篩選完成宇植，則數(shù)組變成一個(gè)正確的堆數(shù)組。然后再調(diào)用remove方法將數(shù)據(jù)移除埋心；由于移除一個(gè)數(shù)據(jù)后指郁，數(shù)組將空出一位，將移除數(shù)據(jù)拷呆，存入空出的空間即可闲坎。
代碼實(shí)現(xiàn)
public class HeapSort {
public static void heapSort(int[] array) {
Heap heap = new Heap(array, array.length);
for (int i = array.length / 2 - 1; i >= 0; i--) {
heap.trickleDown(i);
}
for (int j = array.length - 1; j >= 0; j--) {
array[j] = heap.remove();
}
}
}
算法效率
因?yàn)?code>insert和remove方法的時(shí)間復(fù)雜度都是O(logN),而每個(gè)方法需要執(zhí)行N此，因此
堆排序時(shí)間復(fù)雜度為O(NlogN)
由于其while循環(huán)中執(zhí)行操作要比快速排序復(fù)雜茬斧，其排序速度不如快速排序腰懂。
優(yōu)點(diǎn)：節(jié)省時(shí)間、節(jié)省內(nèi)存项秉。
