Java實現(xiàn)基本排序算法的示例代碼
1. 概述
排序概念：就是將一串記錄按照其中某個或某些關(guān)鍵字的大小，遞增或遞減的排列起來的操作。
穩(wěn)定性：通俗的將就是數(shù)據(jù)元素不發(fā)生有間隔的交換，例如：
內(nèi)部排序：數(shù)據(jù)元素全部放在內(nèi)存中的排序
外部排序：數(shù)據(jù)元素太多不能一次加載到內(nèi)存中，根據(jù)排序過程的要求不能在內(nèi)外存之間移動數(shù)據(jù)的排序。
注意：以下的排序默認(rèn)排升序。默認(rèn)待排序列為：2，5，1，3，8，6，9，4，7，0，6
2. 插入排序
把待排序的記錄按其關(guān)鍵碼值的大小逐個插入到一個已經(jīng)排好序的有序序列中，直到所有的記錄插入完為止，得到一個新的有序序列
2.1 直接插入排序
1. 思想：
對于一個元素，將其與前面元素進行比較，將其插入到合適的位置。
排升序：將待排元素依次與序列中元素從右往左比，若待排元素小，則繼續(xù)往前比，找到合適位置插入，原來元素的位置按順序往后搬移。
2. 畫圖說明：
說明：第一個元素默認(rèn)它有序，所以從第二個元素開始進行比較然后插入，5比2大，繼續(xù)下一個，將1依次比較插入2前面，將3依次比較插入5前面，8比5大，不用管，繼續(xù)下一個，將6依次比較插在8面，9比8大，不用管，將7依次比較，插在8前面，將0依次比較插在1前面，將6依次比較插在7前面，插入完成。
3.代碼展示：
public class InsertSort {
public static void insertSort(int[] array){
for(int i = 1;i < array.length;i++){ //讓從1下標(biāo)開始，因為如果只有一個元素，它自己默認(rèn)有序
int key = array[i]; //從數(shù)組中的第二個元素開始比較，進行插入
int end = i-1; //end的位置是要插入元素的前一個位置
while(end >= 0 && key < array[end]){ //end不能越界，找待插入的位置，此處注意：key不能小于等于array[end]，否則為不穩(wěn)定
array[end+1] = array[end];
end--;
}
array[end+1] = key; //找到位置進行插入，因為上面end--了，所以這里要插入的位置為end+1
}
}
public static void main(String[] args) {
int[] array = {2,5,1,3,8,6,9,4,7,0,6};
insertSort(array);
for(int i : array){
System.out.print(i+" ");
}
}
}
結(jié)果：
4.特性總結(jié)：
時間復(fù)雜度：循環(huán)嵌套，O(N^2)，最優(yōu)情況：當(dāng)序列接近有序，插入的元素比較少，為O(N)
空間復(fù)雜度：不借助輔助空間，O(1)
穩(wěn)定性：數(shù)據(jù)元素不發(fā)生有間隔的交換，穩(wěn)定
應(yīng)用場景：數(shù)據(jù)量小，接近有序
2.2 希爾排序（縮小增量排序）
1. 思想：
選一個整數(shù)為數(shù)據(jù)元素的間隔，將間隔相同的數(shù)據(jù)元素分為一組，分別對這些組進行插入排序，間隔減小，重復(fù)上述操作，當(dāng)間隔減少到1的時候，數(shù)據(jù)元素即排好序了。
2. 畫圖說明：
說明：gap為間隔，這里依次將gap=4，2，1，先把間隔為4的數(shù)據(jù)元素用插入排序排好序，再利用插入排序排gap=2 的數(shù)據(jù)元素，依次重復(fù)上述操作，即可。
3. 代碼展示：
public class ShellSort {
public static void shellSort(int[] array){
int gap = array.length;
while(gap > 1){
gap = gap/3+1;
for(int i = gap;i < array.length;i++){ //跟插入排序一樣，都從一組數(shù)的第二個元素開始，因為第一個數(shù)默認(rèn)有序
int key = array[i];
int end = i - gap; //end的位置也是代排數(shù)的前一個，但這里間隔為gap，所以前一個位置為i-gap
while(end >= 0 && key < array[end]){ //與插入排序保持不變,找待插入的位置
array[end+gap] = array[end]; // key小于前一個數(shù)，讓end位置的元素往后移一位，
end -= gap; //end每次向左走的時候一次走gap的間隔
}
array[end+gap] = key; //找到待排位置將key插入相應(yīng)位置
}
}
}
public static void main(String[] args) {
int[] array = {2,5,1,3,8,6,9,4,7,0,6};
shellSort(array);
for(int i : array){
System.out.print(i+" ");
}
}
}
結(jié)果：
4. 特性總結(jié)：
希爾排序是對直接插入排序的優(yōu)化。
當(dāng)gap>1時都是預(yù)排序，目的是讓數(shù)組元素接近有序，當(dāng)gap==1時，數(shù)組已經(jīng)接近有序了，這樣插入排序?qū)芸?，整體而言，達到了優(yōu)化的效果。
希爾排序的時間復(fù)雜度不好計算，因為gap的取值方法很多，導(dǎo)致很難去計算。
gap的取法有多種，最初shell提出取gap=n/2，gap=gap/2，直到gap=1，后來，Kunth提出取gap = [gap/3]+1。在Kunth所著的《計算機程序設(shè)計技巧》第3卷中，利用大量的實驗統(tǒng)計資料得出，當(dāng)n很大時，關(guān)鍵碼的平均比較次數(shù)和對象平均移動次數(shù)大約在n^1.25到1.6n^1.25范圍內(nèi)，這是利用直接插入排序作為子序列排序方法的情況下得到的。
故時間復(fù)雜度暫記為：O(N^1.25)~O(1.6N^1.25)
空間復(fù)雜度：沒有借助輔助空間，O(1)
穩(wěn)定性：數(shù)據(jù)元素發(fā)生了有間隔的交換，不穩(wěn)定
應(yīng)用場景：數(shù)據(jù)比較隨機
3. 選擇排序
每一次從待排數(shù)據(jù)元素中選出最?。ㄗ畲螅┑脑兀娣旁谛蛄械钠鹗迹┪玻┪恢?，直到全部待排序的數(shù)據(jù)元素全部排完。
3.1 直接選擇排序
1. 思想：
思路1：
找出序列中的最大的元素，若它不在序列的末尾，將它與末尾元素交換位置，依次循環(huán)。
思路2：
每次找元素的時候，找一個最大的和一個最小的，最大的和最后一個交換位置，最小的和第一個交換位置，依次循環(huán)
2. 畫圖說明：
思路1：
說明：先找到序列的最大元素與序列最后一個元素交換，序列的最后的位置朝前移一個，再找新序列的最大元素再與最后一個交換位置，依次循環(huán)。
思路2：
說明：這種方法是一次找兩個元素，跟上面那種本質(zhì)上一樣，只是一次交換了兩個元素，將最大的與最后一個交換，將最小的與第一個交換
3. 代碼展示：
public class SelectSort {
public static void selectSort1(int[] array){
int size = array.length;
for(int i = 0;i < size-1;i++){ //選擇的趟數(shù)，size-1是因為當(dāng)選擇到序列剩一個元素時就不用選了
int pos = 0; //pos標(biāo)記最大元素的位置，剛開始是默認(rèn)為第一個位置
for(int j = 1;j < size-i;j++){ //j=1是因為默認(rèn)第一個元素的位置為最大元素的位置，所以從第二個元素的位置開始比較
//size-i是因為每趟選擇完后，序列都要減少一個
if(array[j] > array[pos]){
pos = j; //找到最大元素位置，更新pos
}
}
if(pos != size-i-1){ //如果最大元素的位置剛好是最后一個位置，則不需要交換，反之進行交換
swap(array,pos,size-i-1);
}
}
}
public static void selectSort2(int[] array){
int left = 0; //序列的左邊界
int right = array.length-1; //序列的右邊界
while(left < right){ //當(dāng)序列中至少存在倆元素時
int minPos = left; //剛開始將最小元素的位置設(shè)定為序列的第一個位置
int maxPos = left; //剛開始將最大元素的位置也設(shè)定為序列的第一個位置
int index = left+1; //從序列的第二個元素開始找最大元素和最小元素的位置
//找最大元素和最小元素的位置
while(index <= right){
if(array[index] < array[minPos]){
minPos = index;
}
if(array[index] > array[maxPos]){
maxPos = index;
}
index++;
}
if(minPos != left){ //當(dāng)最小的元素不在序列的最左端時交換位置
swap(array,minPos,left);
}
//這里我是先交換最小的元素，但是如果最大的元素在最左側(cè)，那么會將maxPos位置的元素更新為最小的元素，導(dǎo)致后面
//交換最大元素的時候maxPos標(biāo)記的元素不準(zhǔn)確，所以下面將maxPos的位置更新了一下
//注意：如果是先交換最大的元素，則更新minPos的位置
if(maxPos == left){
maxPos = minPos;
}
// if(minPos == right){
// minPos = maxPos;
// }
if(maxPos != right){ //當(dāng)最大元素不在序列的最右端時交換位置
swap(array,maxPos,right);
}
left++; //左邊界+1
right--; //右邊界-1
}
}
public static void swap(int[] array,int a,int b){
int t = array[a];
array[a] = array[b];
array[b] = t;
}
public static void main(String[] args) {
int[] array = {9,5,1,3,8,6,2,4,7,6,0};
selectSort1(array);
for(int i : array){
System.out.print(i+" ");
}
System.out.println();
selectSort2(array);
for(int i : array){
System.out.print(i+" ");
}
}
}
4：特性總結(jié)：
時間復(fù)雜度：找元素，交換元素是循環(huán)嵌套，O(N^2)
空間復(fù)雜度：沒有借助輔助空間，O(1)
穩(wěn)定性：數(shù)據(jù)元素存在有間隔的交換，不穩(wěn)定
缺陷：找最大元素或者最小元素的時候重復(fù)比較
3.2 堆排序
1. 思想：
堆排序是利用堆積樹（堆）這種數(shù)據(jù)結(jié)構(gòu)設(shè)計的一種算法，它是選擇排序的一種，它是通過堆來進行選擇數(shù)據(jù)。
注意：排升序，建大根堆，排降序，建小根堆。
堆排序分為兩部分：建堆，利用向下調(diào)整建堆，再利用堆刪除的思想排序。
向下調(diào)整：
前提：要調(diào)整的節(jié)點的兩個左右子樹都已滿足堆的特性
方法：建大堆，將根的元素與左右孩子較大的元素交換，建小堆，將根的元素與左右孩子較小的元素交換
堆刪除思想：
將堆頂元素與最后一個元素交換位置
堆中有效元素減少一個
再對堆頂元素向下調(diào)整
2. 畫圖說明：
因為數(shù)據(jù)元素多，二叉樹的圖看著不太清晰，所以我用以下序列：0，5，3，4，1，2
建堆：
利用堆刪除思想排序：
3. 代碼展示：
public class HeapSort {
//向下調(diào)整
public static void shiftDown(int[] array,int parent,int size){
int child = parent*2+1; //默認(rèn)將左孩子設(shè)為parent的孩子，因為不知道右邊孩子是否存在
while(child<size){
if(child+1<size && array[child+1]>array[child]){ //如果右孩子存在，比較哪個孩子值大
child += 1; //將child設(shè)為較大的孩子
}
if(array[parent]<array[child]){ //如果parent小，將parent與child交換
swap(array,parent,child);
parent = child; //更新parent
child = parent*2+1; //更新child
}else{ //如果已經(jīng)滿足堆特性則直接返回
return;
}
}
}
//堆排序
public static void heapSort(int[] array){
//建堆
int size = array.length;
int lastLeaf = ((size-1)-1)/2; //找到倒數(shù)第一個非葉子節(jié)點
for(int root=lastLeaf;root>=0;root--){ //從該結(jié)點開始，依次向下調(diào)整直到根節(jié)點
shiftDown(array,root,size);
}
//利用堆刪除思想排序,從最后一個元素開始與堆頂元素交換，然后對堆頂元素進行向下調(diào)整
int end = size-1;
while(end>0){
swap(array,0,end);
shiftDown(array,0,end);
end--;
}
}
public static void swap(int[] array,int a,int b){
int t = array[a];
array[a] = array[b];
array[b] = t;
}
public static void main(String[] args) {
int[] array = {2,5,1,3,8,6,9,4,7,0,6};
heapSort(array);
for(int i : array){
System.out.print(i+" ");
}
}
}
結(jié)果：
4. 特性總結(jié)：
時間復(fù)雜度：n個元素進行比較，而且太向下調(diào)整，調(diào)整的深度為完全二叉樹的深度，故時間復(fù)雜度為：O(NlogN),logN是log以2為底的N
空間復(fù)雜度：沒有借助輔助空間，O(1)
穩(wěn)定性：元素發(fā)生了有間隔的交換，不穩(wěn)定
應(yīng)用場景：求前k個最小或者最大，可以和其他排序結(jié)合起來增加效率
4. 交換排序
基本思想就是根據(jù)序列中兩個記錄鍵值的比較結(jié)果來交換這兩個記錄在序列中的位置，交換排序的特點是：將鍵值較大的記錄向序列的尾部移動，鍵值較小的記錄向序列的前部移動
4.1 冒泡排序
1. 思想：
依次將序列元素進行比較，若array[i]>array[i+1],交換兩個元素的位置，直到最后一個元素，從中可以得出，每躺冒泡只能確定一個元素的位置，若序列有n個元素，則需要進行n-1躺冒泡，因為序列最后一個元素的位置不用確定。
從比較的次數(shù)可以看出：第一躺比較的次數(shù)為n-1，第二躺的比較次數(shù)為n-2.....即每趟冒泡比較的次數(shù)在遞減，即比較次數(shù)是為n-1-i，i為冒泡的趟數(shù)。
2. 畫圖說明：
3. 冒泡排序的優(yōu)化：
從上圖可以看出第10躺冒泡沒有進行，因為序列已經(jīng)有序，即數(shù)據(jù)元素不在發(fā)生交換。
優(yōu)化：在每趟進行的開始給一個標(biāo)記isChage=false，如果該躺冒泡發(fā)生了元素交換，將isChange=true，在每趟冒泡完進行判斷，如果是Change==false，即沒有發(fā)生交換，說明序列已經(jīng)有序，即不用在繼續(xù)冒泡，直接返回即可。
4. 代碼展示：
public class BubbleSort {
public static void bubbleSort(int[] array){
int size = array.length;
for(int i = 0;i < size-1;i++){
boolean isChange = false; //為了優(yōu)化冒泡排序給的標(biāo)記，當(dāng)元素不發(fā)生交換的時候說明已經(jīng)有序
for(int j = 0;j < size-1-i;j++){
if(array[j+1] < array[j]){
swap(array,j,j+1);
isChange = true;
}
}
if(isChange == false){ //如果元素不發(fā)生交換，直接返回
return;
}
}
}
public static void swap(int[] array,int a,int b){
int t = array[a];
array[a] = array[b];
array[b] = t;
}
public static void main(String[] args) {
int[] array = {2,5,1,3,8,6,9,4,7,0,6};
bubbleSort(array);
for(int i : array){
System.out.print(i+" ");
}
}
}
結(jié)果：
5. 特性總結(jié)：
時間復(fù)雜度：冒泡的趟數(shù)，每趟的比較次數(shù)，O(N^2)
空間復(fù)雜度：不借助輔助空間，O(1)
穩(wěn)定性：數(shù)據(jù)元素雖然發(fā)生了交換，但是沒有間隔交換，穩(wěn)定
4.2 快速排序
4.2.1. 思想
快速排序是Hoare提出的一種二叉樹結(jié)構(gòu)的交換排序方法。
基本思想為：任取待排元素序列中的某個元素作為基準(zhǔn)值（這里我們?nèi)∽钣覀?cè)元素為基準(zhǔn)值），按照該基準(zhǔn)值將序列劃分為兩個區(qū)間，左側(cè)比基準(zhǔn)值小，右側(cè)比基準(zhǔn)值大，再分別用快速排序遞歸排左區(qū)間和右區(qū)間。
參考代碼：
public static void quickSort(int[] array,int left,int right){ //左閉右開
if(right-left > 1){ //遞歸的返回條件，區(qū)間最少得有兩個元素
int div = partition(array,left,right);
quickSort(array,left,div); //遞歸排左側(cè)
quickSort(array,div+1,right); //遞歸排右側(cè)
}
}
故只要實現(xiàn)分割方法即可。
4.2.2 三種分割方式
1. Hoare法
思想：在左邊找比基準(zhǔn)值大的，右邊找比基準(zhǔn)值小的，兩個交換位置，最后將較大一側(cè)的第一個元素與基準(zhǔn)值交換位置。
畫圖說明：
參考代碼：
//分割區(qū)間方法1：hoare：左邊找比基準(zhǔn)值大的，右邊找比基準(zhǔn)值小的，兩個交換位置,最后再將基準(zhǔn)值放到中間的位置
public static int partition1(int[] array,int left,int right){
int key = array[right-1]; //找基準(zhǔn)值，以最右側(cè)元素為基準(zhǔn)值
int begin = left; //在左側(cè)找的下標(biāo)
int end = right-1; //在右側(cè)找的下標(biāo)
while(begin < end){
while(array[begin] <= key && begin < end){ //左側(cè)找大的，不能越界
begin++;
}
while(array[end] >= key && end > begin){ //右側(cè)找小的，不能越界
end--;
}
if(begin != end){
swap(array,begin,end); //begin與end不在同一位置的時候交換，否則沒有交換的必要
}
}
if(begin != right-1){
swap(array,begin,right-1); //將基準(zhǔn)值與begin位置的元素交換，begin或者end都行
}
return end; //將分割的位置返回，begin與end都可以
}
2. 挖坑法
思想：將基準(zhǔn)值存入key中，基準(zhǔn)值的位置為第一個坑位，在左側(cè)找比基準(zhǔn)值大的，放到第一個坑位上，此時這個元素的原始位置又形成了一個新的坑位，再從右側(cè)找比基準(zhǔn)值小的，放到前面的坑位上，依次循環(huán)，即將序列分割為兩部分。
畫圖說明：
參考代碼：
//分割區(qū)間方法二：挖坑法：基準(zhǔn)值是一個坑位，左側(cè)找大的放到基準(zhǔn)值的坑位上，此時形成了新的坑位，再在右側(cè)找小的放到上一個坑位，依次循環(huán)
public static int partition2(int[] array,int left,int right){
int key = array[right-1]; //取最右側(cè)元素為基準(zhǔn)值，end的位置形成了第一個坑位
int begin = left;
int end = right-1;
while(begin < end){
while(begin < end && key >= array[begin]){ //在左側(cè)找比基準(zhǔn)值大的
begin++;
}
if(begin < end){
array[end] = array[begin]; //填end坑位，重新生成begin坑位
}
while(begin < end && key <= array[end]){ //在右側(cè)找比基準(zhǔn)值小的
end--;
}
if(begin < end){
array[begin] = array[end]; //填begin坑位，重新生成end坑位
}
}
array[begin] = key; //將基準(zhǔn)值填充在最后一個坑位
return end;
}
3. 前后標(biāo)記法
思想：給兩個標(biāo)記cur，pre，pre標(biāo)記cur的前一個，cur開始標(biāo)記第一個元素，依次往后走，cur小于區(qū)間的右邊界，如果cur小于基準(zhǔn)值并且++pre不等于cur交換cur與pre位置的元素，最后交換++pre與基準(zhǔn)值位置的元素。
畫圖說明：
參考代碼：
//分割區(qū)間方法三：前后標(biāo)記法
public static int partition3(int[] array,int left,int right){
int key = array[right-1];
int cur = left;
int pre = cur-1;
while(cur < right){
if(array[cur] < key && ++pre != cur){ //當(dāng)cur位置的元素小于基準(zhǔn)值并且++pre！=cur的時候，交換
swap(array,cur,pre);
}
cur++;
}
if(++pre != right-1){ //++pre為與基準(zhǔn)值交換的位置，所以當(dāng)++pre！=right-1的時候，交換基準(zhǔn)值的位置
swap(array,pre,right-1);
}
return pre;
}
4.2.3 快速排序的優(yōu)化
快速排序的優(yōu)化：對基準(zhǔn)值的選取進行優(yōu)化，這樣做是為了選取的基準(zhǔn)值盡可能的將區(qū)間的左右側(cè)分的均勻一點兒。
優(yōu)化方法：三數(shù)取中法取基準(zhǔn)值，三數(shù)：區(qū)間的中間元素，最左側(cè)元素，最右側(cè)元素，取它們?nèi)齻€的中間值。
參考代碼：
//快排優(yōu)化：三數(shù)取中法來取基準(zhǔn)值，左側(cè)，右側(cè)，中間這三個數(shù)的中間值來作為基準(zhǔn)值,這里返回的是基準(zhǔn)值下標(biāo)
public static int getIndexOfMid(int[] array,int left,int right){
int mid = left+((right-left)>>1);
if(array[left] < array[right-1]){ //最右側(cè)的下標(biāo)為right-1
if(array[mid] < array[left]){
return left;
}else if(array[mid] > array[right-1]){
return right-1;
}else{
return mid;
}
}else{
if(array[mid] < array[right-1]){
return right-1;
}else if(array[mid] > array[left]){
return left;
}else{
return mid;
}
}
}
具體與之前代碼結(jié)合方式，我這里選取一種分割方法來進行優(yōu)化：
參考代碼：
//分割區(qū)間方法三：前后標(biāo)記法
public static int partition3(int[] array,int left,int right){
int index = getIndexOfMid(array,left,right); //用三數(shù)取中法獲得基準(zhǔn)值的下標(biāo)
if(index != right-1){
swap(array,index,right-1); //如果下表不在最右側(cè)就交換
}
int key = array[right-1];
int cur = left;
int pre = cur-1;
while(cur < right){
if(array[cur] < key && ++pre != cur){ //當(dāng)cur位置的元素小于基準(zhǔn)值并且++pre！=cur的時候，交換
swap(array,cur,pre);
}
cur++;
}
if(++pre != right-1){ //++pre為與基準(zhǔn)值交換的位置，所以當(dāng)++pre！=right-1的時候，交換基準(zhǔn)值的位置
swap(array,pre,right-1);
}
return pre;
}
4.2.4 快速排序的非遞歸方式
非遞歸的快速排序借助棧這一數(shù)據(jù)結(jié)構(gòu)
參考代碼：
//非遞歸的快速排序，利用棧來保存分割的區(qū)間，傳參只需要傳數(shù)組即可
public static void quickSort(int[] array){
Stack<Integer> s = new Stack<>();
s.push(array.length);
s.push(0);
while(!s.empty()){
int left = s.pop();
int right = s.pop();
if(right - left == 0){
continue;
}
int div = partition(array,left,right);
s.push(right);
s.push(div+1);
s.push(div);
s.push(left);
}
}
4.2.5 快速排序的特性總結(jié)
時間復(fù)雜度：有比較，遞歸，O(NlogN)
空間復(fù)雜度：存在遞歸，遞歸的深度為完全二叉樹的深度，O(logN)
穩(wěn)定性：數(shù)據(jù)元素發(fā)生有間隔的交換，不穩(wěn)定
應(yīng)用場景：數(shù)據(jù)凌亂且隨機
5. 歸并排序
1. 思想：
歸并排序是將兩個有序序列進行合并，但是我們拿到是一個數(shù)組，所以得先將數(shù)組遞歸均分為兩部分，再將兩部分進行合并。
2. 畫圖說明：
遞歸均分：
從下往上合并：
3. 代碼展示：
public class MergeSort {
public static void mergeSort(int[] array,int left,int right,int[] temp){
if(right - left > 1){
int mid = left+((right-left)>>1);
mergeSort(array,left,mid,temp); //遞歸均分左側(cè)
mergeSort(array,mid,right,temp); //遞歸均分右側(cè)
mergeData(array,left,mid,right,temp); //合并兩個序列，[left,mid) , [mid,right)
System.arraycopy(temp,left,array,left,right-left); //拷貝到原數(shù)組，源，起始位置，新，起始位置，長度
}
}
public static void mergeData(int[] array,int left,int mid,int right,int[] temp){
//[begin1,end1),[begin2,end2),為兩個合并的區(qū)間
int begin1 = left;
int end1 = mid;
int begin2 = mid;
int end2 = right;
int index = left; //輔助數(shù)組的下標(biāo)
while(begin1 < end1 && begin2 < end2){
if(array[begin1] <= array[begin2]){
temp[index++] = array[begin1++];
}else{
temp[index++] = array[begin2++];
}
}
while(begin1 < end1){
temp[index++] = array[begin1++];
}
while(begin2 < end2){
temp[index++] = array[begin2++];
}
}
//重新包裝一下，便于用戶傳參
public static void mergeSort(int[] array){
int[] temp = new int[array.length];
mergeSort(array,0,array.length,temp);
}
}
4. 非遞歸的歸并排序
給一個間隔，用間隔來表示區(qū)間
參考代碼：
//非遞歸的歸并排序
public static void mergeSortNor(int[] array){
int size = array.length;
int[] temp = new int[size];
int gap = 1; //先每兩個元素歸并
while(gap < size){
for(int i = 0;i < size;i+=gap*2){
int left = i;
int mid = i+gap;
int right = mid+gap;
if(mid > size){ //防止mid越界
mid = size;
}
if(right > size){ //防止right越界
right = size;
}
mergeData(array,left,mid,right,temp);
}
System.arraycopy(temp,0,array,0,size);
gap <<= 1;
}
}
5. 特性總結(jié)：
時間復(fù)雜度：O(NlogN)
空間復(fù)雜度：借助了輔助空間，為輔助數(shù)組的大小，O(N)
穩(wěn)定性：數(shù)據(jù)元素不發(fā)生有間隔的交換，穩(wěn)定
應(yīng)用場景：適合外部排序
6. 計數(shù)排序（非比較類型的排序）
1. 思想：
計數(shù)排序又稱鴿巢原理，是對哈希直接定址法的變形應(yīng)用
步驟：
統(tǒng)計相同元素出現(xiàn)次數(shù)
根據(jù)統(tǒng)計的結(jié)果將序列回收到原來的序列中
2. 畫圖說明：
3. 代碼展示：
public class CountSort {
public static void countSort(int[] array){
//找出數(shù)組的最大值與最小值
int maxNum = array[0];
int minNum = array[0];
for(int i = 1;i < array.length;i++){
if(array[i] > maxNum){
maxNum = array[i];
}
if(array[i] < minNum){
minNum = array[i];
}
}
int range = maxNum - minNum + 1; //序列元素的范圍大小
int[] count = new int[range]; //new一個范圍大小的數(shù)組
for(int i = 0;i < array.length;i++){
count[array[i]-minNum]++; //讀取
}
int index = 0; //存入原數(shù)組的下標(biāo)
for(int i = 0;i < range;i++){
while(count[i] > 0){
array[index] = i + minNum;
index++;
count[i]--;
}
}
}
}
4. 性能總結(jié)：
時間復(fù)雜度：O(N)
空間復(fù)雜度：O(M),M為數(shù)據(jù)范圍的大小
穩(wěn)定性：數(shù)據(jù)元素沒有進行有間隔的交換，穩(wěn)定
應(yīng)用場景：數(shù)據(jù)元素集中在某個范圍
7. 排序算法總結(jié)
| 排序方法 | 最好 | 平均 | 最壞 | 空間復(fù)雜度 | 穩(wěn)定性 |
| 插入排序 | O(n) | O(n^2) | O(n^2) | O(1) | 穩(wěn)定 |
| 希爾排序 | O(n) | O(n^1.3) | O(n^2) | O(1) | 不穩(wěn)定 |
| 選擇排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 不穩(wěn)定 |
| 堆排序 | O(n*log(n)) | O(n*log(n)) | O(n*log(n)) | O(1) | 不穩(wěn)定 |
| 冒泡排序 | O(n) | O(n^2) | O(n^2) | O(1) | 穩(wěn)定 |
| 快速排序 | O(n*log(n)) | O(n*log(n)) | O(n^2) | O(log(n)) | 不穩(wěn)定 |
| 歸并排序 | O(n*log(n)) | O(n*log(n)) | O(n*log(n)) | O(n) | 穩(wěn)定 |
以上就是Java實現(xiàn)基本排序算法的示例代碼的詳細內(nèi)容，更多關(guān)于Java排序算法的資料請關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
使用Java實現(xiàn)Excel導(dǎo)入并進行數(shù)據(jù)校驗
這篇文章主要為大家詳細介紹了Java如何根據(jù)下載的指定數(shù)據(jù)模板寫入數(shù)據(jù)和導(dǎo)入并進行數(shù)據(jù)校驗,文中的示例代碼講解詳細,需要的可以了解下2025-03-03
RestTemplate報錯I/O?error?on?POST?request?for的解決辦法
這篇文章主要給大家介紹了關(guān)于RestTemplate報錯I/O?error?on?POST?request?for的解決辦法,文中通過代碼實例將解決的辦法介紹的非常詳細,需要的朋友可以參考下2023-08-08
SpringMVC 參數(shù)綁定之視圖傳參到控制器的實現(xiàn)代碼
這篇文章主要介紹了SpringMVC 參數(shù)綁定之視圖傳參到控制器的相關(guān)知識，本文通過示例代碼給大家介紹的非常詳細，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下2023-03-03
SpringCloud之Feign代理,聲明式服務(wù)調(diào)用方式
這篇文章主要介紹了SpringCloud之Feign代理,聲明式服務(wù)調(diào)用方式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-03-03
Java實現(xiàn)遠程控制技術(shù)完整源代碼分享
這篇文章主要為大家詳細介紹了Java實現(xiàn)遠程控制技術(shù)完整源代碼，具有一定的參考價值，感興趣的小伙伴們可以參考一下2016-08-08
Jmeter命令行執(zhí)行腳本如何設(shè)置動態(tài)參數(shù)
這篇文章主要介紹了Jmeter命令行執(zhí)行腳本如何設(shè)置動態(tài)參數(shù),文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2020-08-08
這篇文章主要介紹了Spring讀取配置文件屬性實現(xiàn)方法,文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2020-04-04
歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide?and?Conquer）的一個非常典型的應(yīng)用。本文將用Java實現(xiàn)這一排序，需要的可以參考一下2022-08-08
使用springboot跳轉(zhuǎn)到指定頁面和(重定向,請求轉(zhuǎn)發(fā)的實例)
這篇文章主要介紹了使用springboot跳轉(zhuǎn)到指定頁面和(重定向,請求轉(zhuǎn)發(fā)的實例)，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-12-12
Java設(shè)計模式之單態(tài)模式（Singleton模式）介紹
這篇文章主要介紹了Java設(shè)計模式之單態(tài)模式（Singleton模式）介紹,本文講解了如何使用單例模式、使用單例模式注意事項等內(nèi)容,需要的朋友可以參考下2015-03-03