java排序算法总结_排序算法总结及Java实现
1. 整體介紹
分類(lèi)
排序大的分類(lèi)可以分為兩種，內(nèi)排序和外排序。在排序過(guò)程中，全部記錄存放在內(nèi)存，則稱(chēng)為內(nèi)排序，如果排序過(guò)程中需要使用外存，則稱(chēng)為外排序。主要需要理解的都是內(nèi)排序算法：
內(nèi)排序可以分為以下幾類(lèi)：
(1)、插入排序：直接插入排序、二分法插入排序、希爾排序。
(2)、選擇排序：簡(jiǎn)單選擇排序、堆排序。
(3)、交換排序：冒泡排序、快速排序。
(4)、歸并排序
(5)、基數(shù)排序
性能對(duì)比
穩(wěn)定性：就是能保證排序前兩個(gè)相等的數(shù)據(jù)其在序列中的先后位置順序與排序后它們兩個(gè)先后位置順序相同。即如果A?i == A?j，A?i原來(lái)在?A?j 位置前，排序后?Ai??仍然是在?Aj?位置前。
不穩(wěn)定：簡(jiǎn)單選擇排序、快速排序、希爾排序、堆排序不是穩(wěn)定的排序算法
穩(wěn)定：冒泡排序、直接插入排序、二分法插入排序，歸并排序和基數(shù)排序都是穩(wěn)定的排序算法。
時(shí)間復(fù)雜度：一個(gè)算法執(zhí)行所耗費(fèi)的時(shí)間。
O(nlogn):快速排序，歸并排序，希爾排序，堆排序。
O(n^2):直接插入排序，簡(jiǎn)單選擇排序，冒泡排序。
O(n): 桶、箱、基數(shù)排序
快速排序是目前基于比較的內(nèi)部排序中最好的方法， 其次是歸并和希爾，堆排序在數(shù)據(jù)量很大時(shí)效果明顯。當(dāng)數(shù)據(jù)是隨機(jī)分布時(shí)快速排序的平均時(shí)間最短。
空間復(fù)雜度：運(yùn)行完一個(gè)程序所需內(nèi)存的大小。
解釋：n: 數(shù)據(jù)規(guī)模；k:“桶”的個(gè)數(shù)；In-place: 占用常數(shù)內(nèi)存，不占用額外內(nèi)存；Out-place: 占用額外內(nèi)存。
排序方法的選擇
1.數(shù)據(jù)規(guī)模很小(插入、簡(jiǎn)單選擇、冒泡)
(1)數(shù)據(jù)基本有序的情況下，可選直接插入排序；
(2)數(shù)據(jù)無(wú)序時(shí)，對(duì)穩(wěn)定性不作要求宜用簡(jiǎn)單選擇排序，對(duì)穩(wěn)定性有要求宜用插入或冒泡
2.數(shù)據(jù)規(guī)模一般(快速排序、歸并排序)
(1)完全可以用內(nèi)存空間，序列雜亂無(wú)序，對(duì)穩(wěn)定性沒(méi)有要求，快速排序，此時(shí)要付出log(N)的額外空間。
(2)序列本身可能有序，對(duì)穩(wěn)定性有要求，空間允許下，宜用歸并排序
3.數(shù)據(jù)規(guī)模很大(歸并、桶)
(1)對(duì)穩(wěn)定性有求，則可考慮歸并排序。
(2)對(duì)穩(wěn)定性沒(méi)要求，宜用堆排序
4.待排序列初始基本有序(正序)，宜用直接插入，冒泡
2. 插入排序(Insertion Sort)
基本思想：依次遍歷元素，在已排序的序列中找到合適的位置將當(dāng)前遍歷的元素插入，直到所有元素都已排序。
方法：直接插入排序、二分插入排序、希爾排序
2.1 直接插入排序
算法思想：
<1>.從第一個(gè)元素開(kāi)始，該元素可以認(rèn)為已經(jīng)被排序；
<2>.取出下一個(gè)元素，在已經(jīng)排序的元素序列中從后向前掃描；
<3>.如果該元素(已排序)大于新元素，將該已排序元素移到下一位置；
<4>.重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置；
<5>.將新元素插入到該位置后；
<6>.重復(fù)步驟2~5。
時(shí)間復(fù)雜度：平均情況下：O(n-2)??????? 最好的情況下：正序有序(從小到大)，這樣只需要比較n次，不需要移動(dòng)。因此時(shí)間復(fù)雜度為O(n)
最壞的情況下：逆序有序,這樣每一個(gè)元素就需要比較n次，共有n個(gè)元素，因此實(shí)際復(fù)雜度為O(n-2)
穩(wěn)定性：穩(wěn)定。由算法思想易知，反向遍歷已排序元素，若已排序元素小于等于當(dāng)前元素，則將當(dāng)前元素插入該已排序元素后的位置，因此相對(duì)順序不變，插入排序是穩(wěn)定的。
Java實(shí)現(xiàn)：
public int[] insertSort(int[] arr){//從前向后遍歷待排序列
for (int i = 1; i < arr.length; i++) {//當(dāng)前正在遍歷的元素值
int key =arr[i];//從后向前掃描已排序序列，依次與當(dāng)前元素對(duì)比
int j = i - 1;while(j >= 0 && arr[j] >key){
arr[j+1] =arr[j];
j--;
}
arr[j+1] =key;
}returnarr;
}
2.2 二分排序(折半插入排序)
二分法查找基本思想：對(duì)于一個(gè)有序的待查序列，定義三個(gè)指針low、high、mid，分別指向待查序列所在范圍的下界、上界及區(qū)間中間位置，即mid=(low+high)/2。對(duì)比待查數(shù)據(jù)與mid所指的值，若相等則查找成功并返回mid，若待查數(shù)小于mid值，則令high=mid-1，否則令low=mid+1，得到新的需要查找的區(qū)間，如此循環(huán)直到找出或找不到。如下示例：
二分排序：從第二個(gè)數(shù)開(kāi)始往后遍歷，用二分法查找合適的插入位置。當(dāng)low
時(shí)間復(fù)雜度：二分插入排序的比較次數(shù)與待排序記錄的初始狀態(tài)無(wú)關(guān)，僅依賴(lài)于記錄的個(gè)數(shù)。當(dāng)n較大時(shí)，比直接插入排序的最大比較次數(shù)少得多。但大于直接插入排序的最小比較次數(shù)。算法的移動(dòng)次數(shù)與直接插入排序算法的相同，最壞的情況為n2/2，最好的情況為n，平均移動(dòng)次數(shù)為O(n2)。
穩(wěn)定性：穩(wěn)定。
Java實(shí)現(xiàn)：
public int[] binaryInsertSort(int[] arr) {intlow, high, mid;intkey;for (int i = 1; i < arr.length; i++) {
key=arr[i];
low= 0;
high= i - 1;//執(zhí)行二分查找，注意符號(hào)(
while(low <=high){
mid= (low + high)/2;if (key
high= mid -1;
}else{
low= mid + 1;
}
}//二分查找終止，說(shuō)明找到合適的位置low//將low位置及之后的所有元素右移一位，再將當(dāng)前遍歷元素插入到low處
for (int j = i - 1; j >= low; j--) {
arr[j+1] =arr[j];
}
arr[low]=key;
}returnarr;
}
2.3 希爾排序(Shell Sort)
基本思想：希爾排序也是一種插入排序方法,實(shí)際上是一種分組插入方法。先取定一個(gè)小于n的整數(shù)d1作為第一個(gè)增量,這樣可以把表的全部記錄分成d1個(gè)組：所有距離為d1的倍數(shù)的記錄放在同一個(gè)組中，在各組內(nèi)進(jìn)行直接插入排序；然后,取第二個(gè)增量d2(＜d1),重復(fù)上述的分組和排序,直至所取的增量dt=1(dt
希爾排序的核心在于間隔序列的設(shè)定。既可以提前設(shè)定好間隔序列，也可以動(dòng)態(tài)的定義間隔序列。
時(shí)間復(fù)雜度： ?平均情況下：O(N*logN)? ? ? ?最好情況：由于希爾排序的好壞和步長(zhǎng)d的選擇(di到di+1的選擇策略)有很多關(guān)系，因此，目前還沒(méi)有得出最好的步長(zhǎng)如何選擇(現(xiàn)在有些比較好的選擇了，但不確定是否是最好的)。所以，不知道最好的情況下的算法時(shí)間復(fù)雜度。
最壞情況：O(N*logN)，最壞的情況下和平均情況下差不多。
穩(wěn)定性：由于多次插入排序，我們知道一次插入排序是穩(wěn)定的，不會(huì)改變相同元素的相對(duì)順序，但在不同趟的插入排序過(guò)程中，相同的元素可能在各自的插入排序中移動(dòng)，最后其穩(wěn)定性就會(huì)被打亂，所以shell排序是不穩(wěn)定的。(有個(gè)猜測(cè)，方便記憶：一般來(lái)說(shuō)，若存在不相鄰元素間交換，則很可能是不穩(wěn)定的排序。)
Java實(shí)現(xiàn)：
public int[] shellSort(int[] arr) {//分組
int d = arr.length/2; //初始增量
while(d > 0){for (int i = d; i < arr.length; i++) { //i是當(dāng)前等待插入的元素的本來(lái)位置
int key =arr[i];int j = i - d; //j用來(lái)循環(huán)，i位置之前待比較的元素序列
while(j >= 0 && arr[j] > arr[i]){ //待插入元素小了
arr[j+d] = arr[j]; //比待插入元素大的都往后移，類(lèi)似于直接插入排序，但是增量由1改為d
j = j - d; //比較已排序序列的前一位置元素
}
arr[j+d] = key; //跳出循環(huán)說(shuō)明找到當(dāng)前a[j]
}
d= d / 2; //步長(zhǎng)算法，可以?xún)?yōu)化
}returnarr;
}
解釋：就是將增量(d)為1的直接插入排序，增量改為從d到1的遞減。不再是相鄰元素間的對(duì)比，而是以d為間隔的對(duì)比插入。
3. 交換排序
3.1 冒泡排序(Bubble Sort)
基本思想：通過(guò)無(wú)序區(qū)中相鄰記錄關(guān)鍵字間的比較和位置的交換,使關(guān)鍵字最小的記錄如氣泡一般逐漸往上“漂浮”直至“水面”。
時(shí)間復(fù)雜度：平均O(n2)
最好情況：正序有序，則只需要比較n次。故，為O(n)
最壞情況:逆序有序，則需要比較(n-1)+(n-2)+……+1，故，為O(N2)
穩(wěn)定性:穩(wěn)定。排序過(guò)程中只交換相鄰兩個(gè)元素的位置。因此，當(dāng)兩個(gè)數(shù)相等時(shí)，是沒(méi)必要交換兩個(gè)數(shù)的位置的。所以相對(duì)位置并沒(méi)有改變，冒泡排序算法是穩(wěn)定的！
算法描述：
<1>.比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換它們兩個(gè)；
<2>.對(duì)每一對(duì)相鄰元素作同樣的工作，從開(kāi)始第一對(duì)到結(jié)尾的最后一對(duì)，這樣在最后的元素應(yīng)該會(huì)是最大的數(shù)；
<3>.針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)；
<4>.重復(fù)步驟1~3，直到排序完成。
Java實(shí)現(xiàn)：
public int[] bubbleSort(int[] arr) {for (int i = arr.length - 1; i >= 0; i--) {for (int j = 0; j < i; j++) {if (arr[j]>arr[j+1]) {
swap(arr[j], arr[j+1]);
}
}
}returnarr;
}/*** 交換兩個(gè)數(shù)*/
public void swap(int a, intb) {int temp =a;
a=b;
b=temp;
}
冒泡排序改進(jìn)1：設(shè)置一標(biāo)志性變量pos,用于記錄每趟排序中最后一次進(jìn)行交換的位置。由于pos位置之后的記錄均已交換到位,故在進(jìn)行下一趟排序時(shí)只要掃描到pos位置即可。因?yàn)樯弦惠喢芭莸淖詈笠淮谓粨Q說(shuō)明該交換的元素是其位置以前的所有元素中最大的(畢竟是自己冒上來(lái)的)。下一趟找最大元素的冒泡從該位置開(kāi)始即可，不必從頭開(kāi)始兩兩交換
Java實(shí)現(xiàn)：
public int[] bubbleSort2(int[] arr){for (int i = arr.length - 1; i >= 0; i--) {int pos = 0; //每趟開(kāi)始，無(wú)交換記錄
for (int j = 0; j < i; j++) {if (arr[j]>arr[j+1]) {
swap(arr[j], arr[j+1]);
pos= j; //記錄交換位置
}
i= pos; //從上輪交換最后一次交換的位置開(kāi)始兩兩對(duì)比
}
}returnarr;
}
3.2?快速排序(Quick Sort)
基本思想：由冒泡排序改進(jìn)而來(lái)的。在待排序的n個(gè)記錄中任取一個(gè)記錄(通常取第一個(gè)記錄),把該記錄放入適當(dāng)位置后,數(shù)據(jù)序列被此記錄劃分成兩部分。所有關(guān)鍵字比該記錄關(guān)鍵字小的記錄放置在前一部分,所有比它大的記錄放置在后一部分,并把該記錄排在這兩部分的中間(稱(chēng)為該記錄歸位)。
核心思想：通過(guò)一趟排序?qū)⒋庞涗浄指舫瑟?dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分的關(guān)鍵字小，則可分別對(duì)這兩部分記錄繼續(xù)進(jìn)行排序，以達(dá)到整個(gè)序列有序。
時(shí)間復(fù)雜度：O(N*logN)
最好的情況：因?yàn)槊看味紝⑿蛄蟹譃閮蓚€(gè)部分(一般二分都復(fù)雜度都和logN相關(guān))，故為 O(N*logN)
最壞的情況：基本有序時(shí)，退化為冒泡排序，幾乎要比較N*N次，故為O(N*N)
穩(wěn)定性：不穩(wěn)定。由于每次都需要和中軸元素(不一定相鄰)交換，因此原來(lái)的順序就可能被打亂?？焖倥判蚴遣环€(wěn)定的。
算法描述：
快速排序使用分治法來(lái)把一個(gè)串(list)分為兩個(gè)子串(sub-lists)。具體算法描述如下：
<1>.從數(shù)列中挑出一個(gè)元素，稱(chēng)為 "基準(zhǔn)"(pivot)；
<2>.重新排序數(shù)列，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面(相同的數(shù)可以到任一邊)。在這個(gè)分區(qū)退出之后，該基準(zhǔn)就處于數(shù)列的中間位置。這個(gè)稱(chēng)為分區(qū)(partition)操作；
<3>.遞歸地(recursive)把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序。
Java實(shí)現(xiàn)：
public int[] quickSort(int[] arr,int low,inthigh){int i =low;int j =high;//if ((arr == null) || (arr.length == 0)){//return null;//}
while (i < j) { //查找基準(zhǔn)點(diǎn)下標(biāo)
while (i < j && arr[i] <= arr[j]) //以數(shù)組start下標(biāo)的數(shù)據(jù)為key，右側(cè)掃描
j--;
swap(arr[i], arr[j]);//從右往左掃描，找出第一個(gè)比key小的，交換位置
while (i < j && arr[i] < arr[j]) //從左往右掃描(此時(shí)a[j]中存儲(chǔ)著key值)
i++;
swap(arr[i], arr[j]);//找出第一個(gè)比key大的，交換位置
}if (i - low > 1) { //遞歸調(diào)用，把key前面的完成排序
quickSort(arr, 0, i - 1);
}if (high - j > 1) {
quickSort(arr, j+ 1, high); //遞歸調(diào)用，把key后面的完成排序
}returnarr;
}
4. 選擇排序
4.1 簡(jiǎn)單選擇排序(Selection Sort)
基本思想：首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最小元素，然后放到排序序列末尾。以此類(lèi)推，直到所有元素均排序完畢。具體做法是：選擇最小的元素與未排序部分的首部交換，使得序列的前面為有序。
時(shí)間復(fù)雜度：平均情況下：O(N2)
最好情況：交換0次，但是每次都要找到最小的元素，因此大約必須遍歷N*N次，因此為O(N*N)。減少了交換次數(shù)！
最壞情況：平均情況下：O(N*N)
穩(wěn)定性：不穩(wěn)定。?由于每次都是選取未排序序列A中的最小元素x與A中的第一個(gè)元素交換，因此跨距離了，很可能破壞了元素間的相對(duì)位置，因此選擇排序是不穩(wěn)定的！
算法描述：n個(gè)記錄的直接選擇排序可經(jīng)過(guò)n-1趟直接選擇排序得到有序結(jié)果。
<1>.初始狀態(tài)：無(wú)序區(qū)為R[1..n]，有序區(qū)為空；
<2>.第i趟排序(i=1,2,3...n-1)開(kāi)始時(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ū)；
<3>.n-1趟結(jié)束，數(shù)組有序化了。
Java實(shí)現(xiàn)：
public int[] selectionSort(int[] arr) {intminIndex;inttemp;//一趟找出一個(gè)最小值
for (int i = 0; i < arr.length - 1; i++) {
minIndex=i;for (int j = i + 1; j < arr.length ; j++) {if (arr[j]
minIndex=j;
}
}//將找到的最小值放到已排序序列的末尾
temp =arr[minIndex];
arr[minIndex]=arr[i];
arr[i]=temp;
}returnarr;
}
4.2 堆排序(Heap Sort)
基本思想：堆排序(Heapsort)是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法。堆積是一個(gè)近似完全二叉樹(shù)的結(jié)構(gòu)，并同時(shí)滿(mǎn)足堆積的性質(zhì)：即子結(jié)點(diǎn)的鍵值或索引總是小于(或者大于)它的父節(jié)點(diǎn)。用完全二叉樹(shù)中雙親節(jié)點(diǎn)和孩子節(jié)點(diǎn)之間的內(nèi)在關(guān)系，在當(dāng)前無(wú)序區(qū)中選擇關(guān)鍵字最大(或者最小)的記錄。也就是說(shuō)，以最小堆為例，根節(jié)點(diǎn)為最小元素，較大的節(jié)點(diǎn)偏向于分布在堆底附近。
時(shí)間復(fù)雜度：O(nlogn)。最壞情況下，接近于最差情況下：O(N*logN)，因此它是一種效果不錯(cuò)的排序算法。
穩(wěn)定性：不穩(wěn)定。需要不斷地調(diào)整堆。
算法描述：
<1>.將初始待排序關(guān)鍵字序列(R1,R2....Rn)構(gòu)建成大頂堆，此堆為初始的無(wú)序區(qū)；
<2>.將堆頂元素R[1]與最后一個(gè)元素R[n]交換，此時(shí)得到新的無(wú)序區(qū)(R1,R2,......Rn-1)和新的有序區(qū)(Rn),且滿(mǎn)足R[1,2...n-1]<=R[n]；
<3>.由于交換后新的堆頂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ò)程完成。
Java實(shí)現(xiàn):
5. 歸并排序
基本思想：多次將兩個(gè)或兩個(gè)以上的有序表合并成一個(gè)新的有序表。
時(shí)間復(fù)雜度：O(nlogn)
最好情況：一趟歸并需要n次，總共需要logN次，因此為O(N*logN)
最壞情況：接近于平均情況下，為O(N*logN)
穩(wěn)定性：歸并排序最大的特色就是它是一種穩(wěn)定的排序算法。歸并過(guò)程中是不會(huì)改變?cè)氐南鄬?duì)位置的。
缺點(diǎn)：它需要O(n)的額外空間。但是很適合于多鏈表排序。
6. 基數(shù)排序
基本思想：它是一種非比較排序。它是根據(jù)位的高低進(jìn)行排序的，也就是先按個(gè)位排序，然后依據(jù)十位排序……以此類(lèi)推。示例如下：
時(shí)間復(fù)雜度：分配需要O(n),收集為O(r),其中r為分配后鏈表的個(gè)數(shù)，以r=10為例，則有0～9這樣10個(gè)鏈表來(lái)將原來(lái)的序列分類(lèi)。而d，也就是位數(shù)(如最大的數(shù)是1234，位數(shù)是4，則d=4)，即"分配-收集"的趟數(shù)。因此時(shí)間復(fù)雜度為O(d*(n+r))
穩(wěn)定性：穩(wěn)定。
適用情況：如果有一個(gè)序列，知道數(shù)的范圍(比如1～1000)，用快速排序或者堆排序，需要O(N*logN)，但是如果采用基數(shù)排序，則可以達(dá)到O(4*(n+10))=O(n)的時(shí)間復(fù)雜度。算是這種情況下排序最快的！！
基數(shù)排序 vs 計(jì)數(shù)排序 vs 桶排序
這三種排序算法都利用了桶的概念，但對(duì)桶的使用方法上有明顯差異：
基數(shù)排序：根據(jù)鍵值的每位數(shù)字來(lái)分配桶
計(jì)數(shù)排序：每個(gè)桶只存儲(chǔ)單一鍵值
桶排序：每個(gè)桶存儲(chǔ)一定范圍的數(shù)值
參考鏈接：
http://www.cnblogs.com/jztan/p/5878630.html
http://blog.chinaunix.net/uid-25906157-id-3318529.html
http://www.cnblogs.com/leeplogs/p/5863846.html
總結(jié)
以上是生活随笔為你收集整理的java排序算法总结_排序算法总结及Java实现的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： java 重载 返回_java – 返
- 下一篇： linux下安装mysql的方式_lin