排序算法
先說(shuō)一些 關(guān)于排序的定義吧
- 排序算法 通常所說(shuō)的排序算法往往指的是內(nèi)部排序算法，即數(shù)據(jù)記錄在內(nèi)存中進(jìn)行排序
- 算法分類 比較排序 非比較排序
- 比較排序 通過(guò)比較來(lái)決定元素間的相對(duì)次序, 時(shí)間復(fù)雜度O(nlogn) ~ O(n^2)，主要有：冒泡排序，選擇排序，插入排序，歸并排序，堆排序，快速排序等。
- 非比較排序 時(shí)間復(fù)雜度可以達(dá)到O(n)，主要有：計(jì)數(shù)排序，基數(shù)排序，桶排序等。
- 時(shí)間復(fù)雜度 對(duì)排序數(shù)據(jù)的總的操作次數(shù)。反映當(dāng)n變化時(shí)，操作次數(shù)呈現(xiàn)什么規(guī)律。
- 空間復(fù)雜度 是指算法在計(jì)算機(jī)內(nèi)執(zhí)行時(shí)所需存儲(chǔ)空間的度量，它也是數(shù)據(jù)規(guī)模n的函數(shù)。
- 穩(wěn)定與不穩(wěn)定 如果a原本在b前面，而a=b，排序之后a仍然在b的前面 , 這就是穩(wěn)定的, 反之就是不穩(wěn)定的.
- 穩(wěn)定的好處 排序算法如果是穩(wěn)定的，那么從一個(gè)鍵上排序，然后再?gòu)牧硪粋€(gè)鍵上排序，前一個(gè)鍵排序的結(jié)果可以為后一個(gè)鍵排序所用
分析表
- n: 數(shù)據(jù)規(guī)模
- k: “桶”的個(gè)數(shù)
- In-place: 占用常數(shù)內(nèi)存，不占用額外內(nèi)存
- Out-place: 占用額外內(nèi)存
結(jié)構(gòu)圖
在冒泡排序之類的排序中，問(wèn)題規(guī)模為n，又因?yàn)樾枰容^n次，所以平均時(shí)間復(fù)雜度為O(n2)。在歸并排序、快速排序之類的排序中，問(wèn)題規(guī)模通過(guò)分治法消減為logN次，所以時(shí)間復(fù)雜度平均O(nlogn)。
冒泡排序
描述
- 比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換它們兩個(gè)
- 對(duì)每一對(duì)相鄰元素作同樣的工作，從開始第一對(duì)到結(jié)尾的最后一對(duì)，這樣在最后的元素應(yīng)該會(huì)是最大的數(shù)
- 針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)
- 重復(fù)步驟1~3，直到排序完成
代碼實(shí)現(xiàn)
public static int[] bubbleSort(int[] array) {
if (array.length == 0)
return array;
for (int i = 0; i < array.length; i++)
for (int j = 0; j < array.length - 1 - i; j++)
if (array[j + 1] < array[j]) {
int temp = array[j + 1];
array[j + 1] = array[j];
array[j] = temp;
}
return array;
}
雞尾酒排序
描述
雞尾酒排序，也叫定向冒泡排序，是冒泡排序的一種改進(jìn)。此算法與冒泡排序的不同處在于從低到高然后從高到低，而冒泡排序則僅從低到高去比較序列里的每個(gè)元素。他可以得到比冒泡排序稍微好一點(diǎn)的效能。
//示例入?yún)?shù)組; src = {5,2,4,1,3}
public static void cocktail_sort(int[] src){
System.out.println(Arrays.toString(src));
long startTime = System.nanoTime();
//該算法是只需要向左或右推數(shù)組長(zhǎng)度的一半次數(shù)就夠了
for (int i = 0; i < src.length / 2; i++){
//第一個(gè)for循環(huán)是將數(shù)組中最大的數(shù)，向最后推。結(jié)果最大的數(shù)總會(huì)在最右邊
//例如上面的數(shù)組
//第一次：5因?yàn)樽畲?，所以在?zhí)行下面循環(huán)之后，一定位于數(shù)組最后面。（以此類推，第二次，是4最大，會(huì)位于5的前面）
for (int j = i; j < src.length - i - 1; j++){
if (src[j] > src[j + 1]){
int temp = src[j];
src[j] = src[j + 1];
src[j + 1] = temp;
}
}
//第二個(gè)循環(huán)是將數(shù)組中最小的數(shù)，往最前面推。結(jié)果最小的數(shù)總會(huì)在最右邊
//例如上面的數(shù)組
//第一次往右，1是最小，循環(huán)執(zhí)行完畢后，1一定位于數(shù)組最前面。（類似地，第二次就會(huì)把第二小的數(shù)字2，向左推到1的后面）
for (int j = src.length - 1 - (i + 1); j >= i; j--){
if (src[j] > src[j + 1]){
int temp = src[j];
src[j] = src[j + 1];
src[j + 1] = temp;
}
}
//當(dāng)執(zhí)行完一輪循環(huán)之后，向右和向左推的數(shù)就不會(huì)再參與下一輪的循環(huán)了，不然就浪費(fèi)資源了。
}
long endTime = System.nanoTime();
System.out.println("take time = " + (endTime - startTime)+"ns");
System.out.println( Arrays.toString(src));
}
在亂數(shù)序列的狀態(tài)下，雞尾酒排序與冒泡排序的效率都很差勁。
選擇排序
描述
首先在未排序序列中找到最?。ù螅┰?，存放到排序序列的起始位置，然后，再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最?。ù螅┰?，然后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。
選擇排序是最穩(wěn)定的排序算法 因?yàn)闊o(wú)論什么數(shù)據(jù)進(jìn)去都是O(n2)的時(shí)間復(fù)雜度
- 初始狀態(tài)：無(wú)序區(qū)為R[1..n]，有序區(qū)為空；
- 第i趟排序(i=1,2,3…n-1)開始時(shí)，當(dāng)前有序區(qū)和無(wú)序區(qū)分別為R[1..i-1]和R(i..n）。該趟排序從當(dāng)前無(wú)序區(qū)中-選出關(guān)鍵字最小的記錄 R[k]，將它與無(wú)序區(qū)的第1個(gè)記錄R交換，使R[1..i]和R[i+1..n)分別變?yōu)橛涗泜€(gè)數(shù)增加1個(gè)的新有序區(qū)和記錄個(gè)數(shù)減少1個(gè)的新無(wú)序區(qū)；
- n-1趟結(jié)束，數(shù)組有序化了。
[圖片上傳失敗...(image-fcf727-1540559993055)]
for (int i = 0; i < array.length; i++) {
int minIndex = i;
for (int j = i; j < array.length; j++) {
if (array[j] < array[minIndex]) //找到最小的數(shù)
minIndex = j; //將最小數(shù)的索引保存
}
int temp = array[minIndex];
array[minIndex] = array[i];
array[i] = temp;
}
插入排序
描述
通過(guò)構(gòu)建有序序列，對(duì)于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。
[圖片上傳失敗...(image-aa6581-1540559993055)]
- 從第一個(gè)元素開始，該元素可以認(rèn)為已經(jīng)被排序；
- 取出下一個(gè)元素，在已經(jīng)排序的元素序列中從后向前掃描；
- 如果該元素（已排序）大于新元素，將該元素移到下一位置；
- 重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置；
- 將新元素插入到該位置后；
- 重復(fù)步驟2~5。
int current;
for (int i = 0; i < array.length - 1; i++) {
current = array[i + 1];
int preIndex = i;
while (preIndex >= 0 && current < array[preIndex]) {
array[preIndex + 1] = array[preIndex];
preIndex--;
}
array[preIndex + 1] = current;
}
希爾排序
描述(ShellSort)
是對(duì)插入排序的優(yōu)化升級(jí) 該算法是沖破O(n2）的第一批算法之一 它與插入排序的不同之處在于，它會(huì)優(yōu)先比較距離較遠(yuǎn)的元素。希爾排序又叫縮小增量排序。
希爾排序是把記錄按下表的一定增量分組，對(duì)每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關(guān)鍵詞越來(lái)越多，當(dāng)增量減至1時(shí)，整個(gè)文件恰被分成一組，算法便終止
[圖片上傳失敗...(image-42fbf7-1540559993055)]
算法描述
我們來(lái)看下希爾排序的基本步驟，在此我們選擇增量gap=length/2，縮小增量繼續(xù)以gap = gap/2的方式，這種增量選擇我們可以用一個(gè)序列來(lái)表示，{n/2,(n/2)/2...1}，稱為增量序列。希爾排序的增量序列的選擇與證明是個(gè)數(shù)學(xué)難題，我們選擇的這個(gè)增量序列是比較常用的，也是希爾建議的增量，稱為希爾增量，但其實(shí)這個(gè)增量序列不是最優(yōu)的。此處我們做示例使用希爾增量。
- 選擇一個(gè)增量序列t1，t2，…，tk，其中ti>tj，tk=1；
- 按增量序列個(gè)數(shù)k，對(duì)序列進(jìn)行k 趟排序；
- 每趟排序，根據(jù)對(duì)應(yīng)的增量ti，將待排序列分割成若干長(zhǎng)度為m的子序列，分別對(duì)各子表進(jìn)行直接插入排序。僅增量因子為1時(shí)，整個(gè)序列作為一個(gè)表來(lái)處理，表長(zhǎng)度即為整個(gè)序列的長(zhǎng)度。
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;
}
歸并排序
描述(mergeSort)
和選擇排序一樣，歸并排序的性能不受輸入數(shù)據(jù)的影響，始終都是O(n log n）的時(shí)間復(fù)雜度。代價(jià)是需要額外的內(nèi)存空間。
歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用。歸并排序是一種穩(wěn)定的排序方法。將已有序的子序列合并，得到完全有序的序列；即先使每個(gè)子序列有序，再使子序列段間有序。若將兩個(gè)有序表合并成一個(gè)有序表，稱為2-路歸并。
算法描述
- 把長(zhǎng)度為n的輸入序列分成兩個(gè)長(zhǎng)度為n/2的子序列；
- 對(duì)這兩個(gè)子序列分別采用歸并排序；
- 將兩個(gè)排序好的子序列合并成一個(gè)最終的排序序列。
[圖片上傳失敗...(image-5f1cd2-1540559993055)]
/**
* 歸并排序
*
* @param array
* @return
*/
public static int[] MergeSort(int[] array) {
if (array.length < 2) return array;
int mid = array.length / 2;
int[] left = Arrays.copyOfRange(array, 0, mid);
int[] right = Arrays.copyOfRange(array, mid, array.length);
return merge(MergeSort(left), MergeSort(right));
}
/**
* 歸并排序——將兩段排序好的數(shù)組結(jié)合成一個(gè)排序數(shù)組
*
* @param left
* @param right
* @return
*/
public static int[] merge(int[] left, int[] right) {
int[] result = new int[left.length + right.length];
for (int index = 0, i = 0, j = 0; index < result.length; index++) {
if (i >= left.length)
result[index] = right[j++];
else if (j >= right.length)
result[index] = left[i++];
else if (left[i] > right[j])
result[index] = right[j++];
else
result[index] = left[i++];
}
return result;
}
快速排序
快速排序的基本思想：通過(guò)一趟排序?qū)⒋庞涗浄指舫瑟?dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分的關(guān)鍵字小，則可分別對(duì)這兩部分記錄繼續(xù)進(jìn)行排序，以達(dá)到整個(gè)序列有序
算法描述
快速排序使用分治法來(lái)把一個(gè)串（list）分為兩個(gè)子串（sub-lists）。具體算法描述如下：
- 從數(shù)列中挑出一個(gè)元素，稱為 “基準(zhǔn)”（pivot）；
- 重新排序數(shù)列，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面（相同的數(shù)可以到任一邊）。在這個(gè)分區(qū)退出之后，該基準(zhǔn)就處于數(shù)列的3. 中間位置。這個(gè)稱為分區(qū)（partition）操作；
遞歸地（recursive）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序
[圖片上傳失敗...(image-d505a2-1540559993056)]
/**
* 快速排序方法
* @param array
* @param start
* @param end
* @return
*/
public static int[] QuickSort(int[] array, int start, int end) {
if (array.length < 1 || start < 0 || end >= array.length || start > end) return null;
int smallIndex = partition(array, start, end);
if (smallIndex > start)
QuickSort(array, start, smallIndex - 1);
if (smallIndex < end)
QuickSort(array, smallIndex + 1, end);
return array;
}
/**
* 快速排序算法——partition
* @param array
* @param start
* @param end
* @return
*/
public static int partition(int[] array, int start, int end) {
int pivot = (int) (start + Math.random() * (end - start + 1));
int smallIndex = start - 1;
swap(array, pivot, end);
for (int i = start; i <= end; i++)
if (array[i] <= array[end]) {
smallIndex++;
if (i > smallIndex)
swap(array, i, smallIndex);
}
return smallIndex;
}
/**
* 交換數(shù)組內(nèi)兩個(gè)元素
* @param array
* @param i
* @param j
*/
public static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
堆排序
堆排序（Heapsort）是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法。堆積是一個(gè)近似完全二叉樹的結(jié)構(gòu)，并同時(shí)滿足堆積的性質(zhì)：即子結(jié)點(diǎn)的鍵值或索引總是小于（或者大于）它的父節(jié)點(diǎn)。
算法描述
- 將初始待排序關(guān)鍵字序列(R1,R2….Rn)構(gòu)建成大頂堆，此堆為初始的無(wú)序區(qū)；
- 將堆頂元素R[1]與最后一個(gè)元素R[n]交換，此時(shí)得到新的無(wú)序區(qū)(R1,R2,……Rn-1)和新的有序區(qū)(Rn),且滿足R[1,2…n-1]<=R[n]；
- 由于交換后新的堆頂R[1]可能違反堆的性質(zhì)，因此需要對(duì)當(dāng)前無(wú)序區(qū)(R1,R2,……Rn-1)調(diào)整為新堆，然后再次將R[1]與無(wú)序區(qū)最后一個(gè)元素交換，得到新的無(wú)序區(qū)(R1,R2….Rn-2)和新的有序區(qū)(Rn-1,Rn)。不斷重復(fù)此過(guò)程直到有序區(qū)的元素個(gè)數(shù)為n-1，則整個(gè)排序過(guò)程完成。
[圖片上傳失敗...(image-7ac786-1540559993056)]
//聲明全局變量，用于記錄數(shù)組array的長(zhǎng)度；
static int len;
/**
* 堆排序算法
*
* @param array
* @return
*/
public static int[] HeapSort(int[] array) {
len = array.length;
if (len < 1) return array;
//1.構(gòu)建一個(gè)最大堆
buildMaxHeap(array);
//2.循環(huán)將堆首位（最大值）與末位交換，然后在重新調(diào)整最大堆
while (len > 0) {
swap(array, 0, len - 1);
len--;
adjustHeap(array, 0);
}
return array;
}
/**
* 建立最大堆
*
* @param array
*/
public static void buildMaxHeap(int[] array) {
//從最后一個(gè)非葉子節(jié)點(diǎn)開始向上構(gòu)造最大堆
for (int i = (len/2 - 1); i >= 0; i--) { //感謝 @讓我發(fā)會(huì)呆 網(wǎng)友的提醒，此處應(yīng)該為 i = (len/2 - 1)
adjustHeap(array, i);
}
}
/**
* 調(diào)整使之成為最大堆
*
* @param array
* @param i
*/
public static void adjustHeap(int[] array, int i) {
int maxIndex = i;
//如果有左子樹，且左子樹大于父節(jié)點(diǎn)，則將最大指針指向左子樹
if (i * 2 < len && array[i * 2] > array[maxIndex])
maxIndex = i * 2;
//如果有右子樹，且右子樹大于父節(jié)點(diǎn)，則將最大指針指向右子樹
if (i * 2 + 1 < len && array[i * 2 + 1] > array[maxIndex])
maxIndex = i * 2 + 1;
//如果父節(jié)點(diǎn)不是最大值，則將父節(jié)點(diǎn)與最大值交換，并且遞歸調(diào)整與父節(jié)點(diǎn)交換的位置。
if (maxIndex != i) {
swap(array, maxIndex, i);
adjustHeap(array, maxIndex);
}
}
