Java中七種排序算法總結分析
前言：對文章出現的一些名詞進行解釋
排序： 使一串記錄，按照其中的某個或某些關鍵字的大小，遞增或者遞減排列起來的操作。
穩定性： 假定在排序的記錄序列中，存在多個具有相同的關鍵字的記錄，若經過排序，這些記錄的相對次序保持不變，即在原序列中，a=b，且a在b之前，而在排序後的序列中，a仍然在b之前則這種排序算法是穩定的，否則就是不穩定的。
內部排序： 數據元素全部放在內存中的排序。
外部排序： 數據元素太多不能同時放在內存中，根據排序過程的要求不能在內外存之間移動數據的排序。
文中所有排序都是升序。
一、插入排序
直接插入排序是一種簡單的插入排序法。
1.基本思想
把待排序的記錄按照其關鍵碼值的大小逐個插入到一個已經排好序的有序序列中，直到所有記錄全部插完為止，得到一個新的有序序列。這種思想在我們玩撲克牌的時候用到過，在我們碼牌時，抽出一個牌，會從後往前依次比較牌面值，然後插入到一個比前面大且比後面小的位置中。
2.直接插入排序
步驟：
1.第一次排序先將第一個元素看成是已排序區間，將其內容保存起來
2.待排序區間是其後面的所有元素，從其後面第一個開始，依次和已排序區間裡的元素比較（這裡的比較是從後向前比較，也就是從其前一個元素比較到0號位置的元素）
3.如果小於已排序區間中的元素，則將該位置向後挪一位
4.直到找到第一個比其小的元素，此時其後面的所有元素都是比它大的，且都向後挪瞭一位，這時其後面的位置是空的，將該元素放進來即可。
5.之後取第二個，第三個…第i個依次這樣比較即可，即循環起來。其中每次[0,i)是已排序區間，[i,size)是待排序區間。
動圖演示：
代碼實現：
public static void insertSort(int[] array){
int j=0;
//i位置與之前所有下標從後往前進行比較，該位置大於i則繼續往前，小於則插入到後邊
//[0,bound)已排序區間
//[bound,size)待排序區間
for(int bound=1;bound<array.length;bound++) {
int temp = array[bound];
//先取已排序區間的最後一個，依次往前進行比較
for (j = bound - 1; j >= 0; j--) {
//如果temp小於，則將元素往後移一位
if (array[j]>temp) {
array[j + 1] = array[j];
} else {
break;
}
}
//找到合適位置，填充
array[j + 1] = temp;
}
}
相關特性總結：
時間復雜度：O(N2)
空間復雜度：O(1)
穩定性：穩定（是從後往前依次比較的）
應用場景：元素越接近有序越好（因為越接近有序比較次數就會越少，算法的時間效率就會越高）
3.希爾排序(縮小增量排序)
基本思想：
把待排序區間中所有記錄分成幾個組，設置一個gap值，所有距離為gap的記錄分在同一組內，並分別對每個組內的記錄進行排序，然後讓gap以一定的規律減小，然後重復上述分組和排序的工作，當gap達到1時，所有記錄已經排好序。
步驟：
1.設置gap值（每個組內元素之間間隔）
2.在每個組內進行直接插入排序
3.縮小gap值（這裡我按照2倍縮小）
4.gap為1時排序完畢
圖象解釋：
代碼實現：
public static void shellSort(int[] array){
int gap= array.length/2;
while(gap>0){
int j=0;
//i位置與之前所有下標從後往前進行比較，該位置大於i則繼續往前，小於則插入到後邊
for(int bound=gap;bound<array.length;bound+=gap) {
int temp = array[bound];
for (j = bound - gap; j >= 0; j-=gap) {
if (array[j]>temp) {
array[j + gap] = array[j];
} else {
break;
}
}
array[j + gap] = temp;
}
gap=gap/2;
}
}
相關特性總結：
希爾排序是對直接插入排序的優化
當gap>1時都是預排序，目的是讓數組更接近有序，當gap==1時，數組已經接近有序，這樣就很會快，整體而言，可以達到優化的效果
時間復雜度不確定，因為gap取值方法有很多
空間復雜度：O(1)
穩定性：不穩定（元素之間是跳著交換的）
二、選擇排序
1.基本思想
每一次從待排序的數據元素中選出最小（或最大）的一個元素，存放在序列的起始位置，直到全部待排序的數據元素排完。
2.直接選擇排序
步驟：
1.先記錄下標為0元素為最小值
2.從下標為1開始往後遍歷，遇到比最小值還小的就標記起來，遍歷完成即找到最小值
3.將找到的最小值與下標為0的元素進行交換
4.此時[0,1）為已排序區間，即不再動，[1,size)是待排序區間
5.從下標為1繼續上面的操作，即循環起來
6.循環到最後隻剩一個元素結束，排序完成
動圖演示：
代碼實現：
public static void selectSort(int[] nums) {
//每次都和第一個元素相比，如果小於則和一個元素則交換
for(int bound=0;bound<nums.length-1;bound++){
//先記錄最小值為第一個元素
int min=bound;
//從其後一個開始遍歷，找出後面所有元素中的最小值
for(int i=bound+1;i<nums.length;i++){
if(nums[min]>nums[i]){
min=i;
}
}
//將最小值與待排序區間第一個進行交換
swap(nums,bound,min);
}
}
相關特性總結：
時間復雜度：O(N2)
空間復雜度：O(1)
穩定性：不穩定
效率不是很好，實際中很少使用
3.堆排序
堆排序是指利用堆這種數據結構所設計的一種排序算法，它是選擇排序的一種。它是通過堆來進行選擇數據。
註意：排升序要建大堆，排降序要建小堆
步驟：
1.創建一個大堆（升序）
從倒數第一個非葉子結點開始向下調整，直到根結點，創建一個大堆
2.將根結點與最後一個結點進行交換，此時最後一個元素一定是所有元素中最大的
3.將size–
4.將堆繼續調整好形成一個大堆，繼續上面的操作，即循環起來
5.最終排序完成
圖像解釋：
代碼實現：
//寫一個交換函數
private static void swap(int[] array,int parent,int child){
int temp=array[child];
array[child]=array[parent];
array[parent]=temp;
}
//排升序建大堆
//向下調整，上篇博客提到瞭
private static void shiftDown(int[] array,int parent,int size){
int child=parent*2+1;
while(child<size){
if(child+1<size&&array[child+1]>array[child]){
child+=1;
}
if(array[parent]<array[child]){
swap(array,parent,child);
parent=child;
child=parent*2+1;
}else{
return;
}
}
}
//堆排序
public static void heapSort(int[] array){
//創建一個堆
int size=array.length;
for(int root=(size-2)/2;root>=0;root--){
shiftDown(array,root,size);
}
while(size>1){
//將第一個和最後一個元素進行交換
swap(array,0,size-1);
//交換完成向下調整
size--;
shiftDown(array,0,size);
}
}
相關特性總結：
時間復雜度：O(NlogN)
空間復雜度：O(1)
穩定性：不穩定
使用堆來選數，效率高瞭很多
三、交換排序
1.基本思想
交換，就是根據序列中兩個記錄鍵值的比較結果來兌換這兩個記錄在序列中的位置，交換序列的特點是：將鍵值較大的記錄向序列的尾部移動，鍵值較小的記錄向序列的頭部移動
2.冒泡排序
步驟：
1.從0號位置開始，將元素和他後面的元素比較，如果大於則交換
2.當遍歷完成，最大的元素肯定在數組的最後
3.之後再比較時，最後一個元素就是已排序區間，不再參與比較
4.重復上述步驟，即循環起來
動圖演示：
代碼實現：
public static void bubbleSort(int[] nums) {
//外層循環控制循環次數
for(int num=1;num<nums.length;num++){
//內層循環控制交換哪兩個元素
for(int i=0;i<nums.length-num;i++){
if(nums[i+1]<nums[i]){
swap(nums,i+1,i);
}
}
}
}
相關特性總結：
時間復雜度：O(N2)
空間復雜度：O(1)
穩定性：穩定
冒泡排序在最開始就已經學到，很容易理解
3.快速排序（遞歸與非遞歸）
快速排序是Hoare於1962年提出的一種二叉樹結構的交換排序方法，其基本思想為：任取待排序元素序列中的某元素作為基準值，按照該基準值將待排序集合分割成兩子序列，左子序列中所有元素均小於基準值，右子序列中所有元素均大於基準值，然後左右子序列重復該過程，直到所有元素都排列在相應的位置上為止。
主框架實現：
public static void quickSort(int[] array,int left,int right){
if((right-left)<=1){
return;
}
//按照基準值對array數組的[left,right)區間中的元素進行劃分
int div=partition3(array,left,right);
//劃分成功後以div為邊界形成瞭左右兩部分[left,div)和[div+1,right)
//遞歸排[left,div)
quickSort(array,left,div);
//遞歸排[div+1,right)
quickSort(array,div+1,right);
}
從上述程序可以看出，程序結構與二叉樹前序遍歷規則非常像。
接下來按照基準值劃分就是快排的核心，常見方法有三種：
1.Hoare版
步驟：
1.這裡我們取最右側為基準值
2.設置begin和end用來標記，讓begin從左往右走，end從右往左走
3.當begin小於end時，因為我們取得基準值為最右側，所以應先讓begin從左往右走，找到比基準值大的元素就停下來
4.這時讓end從右往左走，找到比基準值小的元素就停下來，兩者交換位置
5.循環起來
6.當循環結束時，兩個最終走到瞭同一個位置，將其和基準值進行交換
動圖演示：
代碼實現：
private static int partition1(int[] array,int left,int right){
int temp=array[right-1];
//begin從左往右找
int begin=left;
//end從右往左找
int end=right-1;
while(begin<end){
//讓begin從前往後找比temp大的元素，找到之後停下來
while(array[begin]<=temp&&begin<end){
begin++;
}
//讓end從後往前找比temp小的元素，找到之後停下來
while(array[end]>=temp&&begin<end){
end--;
}
//當兩個在同一個位置時，不需要交換，減少交換次數
if(begin!=end){
swap(array,begin,end);
}
}
if(begin!=right-1){
swap(array,begin,right-1);
}
return begin;
}
2.挖坑法
步驟：
1.先將基準值（這裡是最右側元素）放在臨時變量temp中，這裡就形成第一個坑位
2.設置begin和end用來標記，讓begin從左往右走，end從右往左走
3.當begin小於end時，讓begin從左往右走，找到比temp大的值，去填end的坑，同時begin這裡形成一個坑位
4.然後讓end從右往左走，找到比temp小的值，去填begin的坑，同時end這裡形成瞭一個新的坑位
5.就這樣一直循環，互相填坑，直到不滿足循環條件
6.這時begin和end在同一個坑位，且是最後一個坑位，使用基準值填充
圖象解釋：
代碼實現：
private static int partition2(int[] array,int left,int right){
int temp=array[right-1];
int begin=left;
int end=right-1;
while(begin<end){
//讓begin從前往後找比基準值大的元素
while(array[begin]<=temp&&begin<end){
begin++;
}
if(begin!=end){
//begin位置找到瞭一個比temp大的元素，填end的坑
array[end]=array[begin];
//begin位置形成瞭一個新的坑位
}
//讓end從後往前找比基準值小的元素
while(array[end]>=temp&&begin<end){
end--;
}
if(begin!=end){
//end位置找到瞭一個比temp小的元素，填begin的坑
array[begin]=array[end];
//end位置形成瞭一個新的坑位
}
}
//begin和end位置是最後的一個坑位
//這個坑位使用基準值填充
array[begin]=temp;
return begin;
}
3.前後標記法（難理解）
小編其實也是根據大佬的代碼分析出來的，要問為什麼這麼做咱確實也是不太理解，另外如理解錯誤歡迎指正
這裡真誠發問，大佬們的腦子是不是和我的腦子不太一樣？
步驟：
1.采用cur和prev來標記，兩者都是從左往右走，不一樣的是，最開始cur在0號位置，prev在cur前一個位置上
2.當遇到比temp大的元素時，prev不動，cur向前走一步，當兩者一前一後的狀態時，cur也會往前走一步，而prev不動
3.這樣兩者逐漸拉開差距，此時遇到比基準值小的元素，cur中的元素就會與prev中的元素交換
4.走到最後prev的下一個元素與基準值位置交換
圖象解釋：
代碼實現：
private static int partition3(int[] array,int left,int right){
int temp=array[right-1];
int cur=left;
int prev=cur-1;
//讓cur從前往後找比基準值小的元素
while(cur<right){
if(array[cur]<temp&&++prev!=cur){
swap(array,cur,prev);
}
cur++;
}
//將基準值的位置放置好
if(++prev!=right-1){
swap(array,prev,right-1);
}
return prev;
}
但是會發現：
當我們選取的基準值越靠近整個數組的中間時，效率越好，這時可以看作是將數組逐漸分成瞭一個滿二叉樹，因此效率為O(NlogN)
最差時是取到其最大或者最小的元素，還是要劃分n次，效率為O(N2)
一般時間復雜度都是看起最差情況，那為什麼快速排序的時間復雜度是O(NlogN)呢？
其實是可以對取基準值進行優化的，詳情請看下面：
4.快速排序優化
1.三數取中法選temp
之前我們隻取一個基準值
優化後，我們在左邊取一個，中間取一個，右邊取一個
比較三個數的大小，誰在中間就取誰為基準值
private static int getIndexOfMid(int[] array,int left,int right){
int mid=left+((right-left)>>1);
if(array[left]<array[right-1]){
if(array[mid]<array[left]){
return left;
}else if(array[mid]>array[right-1]){
return right-1;
}else{
return mid;
}
}
在更改上面的劃分方法中，隻需要看看上面取出的基準值在不在最右側，如果不在就與最右側的值交換，這樣代碼改動就比較小。
int index=getIndexOfMid(array,left,right);
if(index!=right-1){
swap(array,index,right-1);
}
2.遞歸到小的子區間時，可以考慮使用插入排序
在Idea的內層方法中，用的是小於47使用直接插入排序
5.快速排序非遞歸
如果直接轉為循環不好轉，之前提到可以使用棧來實現，利用棧後進先出的特性
public static void quickSortNor(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)<47){
insertSortQuick(array,left,right);
}else{
int div=partition1(array,left,right);
//先壓入基準值的右半側
s.push(right);
s.push(div+1);
//再壓入基準值的左半側
s.push(div);
s.push(left);
}
}
}
6.相關特性總結
時間復雜度：O(NlogN)
空間復雜度：O(logN)(遞歸單次沒有借助輔助空間，高度即是深度)
穩定性：不穩定
快速排序整體綜合性能和使用場景都是比較好的，所以才叫快速排序
四、歸並排序（遞歸與非遞歸）
歸並排序是建立在歸並操作上的一種有效的排序算法，該算法是采用分治法的一個非常典型的應用。將已有的子序列合並，得到完全有序的序列，即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合並成一個有序表，稱為二路歸並。
動圖演示：
歸並排序核心步驟：將兩個有序數組合並成一個有序數組
private static void mergeData(int[] array,int left,int mid,int right,int[] temp){
int begin1=left,end1=mid;
int begin2=mid,end2=right;
int index=left;
while(begin1<end1&&begin2<end2){
//依次比較每一位上的元素，小的放入temp同時下標後移一位
if(array[begin1]>array[begin2]){
temp[index++]=array[begin2++];
}else {
temp[index++]=array[begin1++];
}
}
//看兩個數組哪個還沒有遍歷完成，直接順次放入temp數組的後面
while(begin1<end1){
temp[index++] = array[begin1++];
}
while(begin2<end2){
temp[index++]=array[begin2++];
}
}
主程序（遞歸）：
步驟：
1.先對待排序區間進行均分為兩個
2.使用遞歸，直到均分為每個區間隻剩下一個元素時，每兩個使用二路歸並
3.將兩個有序數組合並為一個有序數組，將結果保存在temp中
4.最終temp保存的就是排序完成的數組，再拷貝回原數組中
private static void mergeSort(int[] array,int left,int right,int[] temp){
if((right-left>1)){
//先對[left,right)區間中的元素進行均分
int mid=left+((right-left)>>1);
//[left,mid)
mergeSort(array,left,mid,temp);
//[mid,right)
mergeSort(array,mid,right,temp);
//二路歸並
mergeData(array,left,mid,right,temp);
//將temp中的元素拷貝回原數組中
System.arraycopy(temp,left,array,left,right-left);
}
}
主程序（非遞歸）：
直接采用gap對數組進行分割，每次分割完成對gap*2，一開始為2個采用二路歸並，之後4個，8個，直到大於等於size結束。
非遞歸比遞歸思路更加簡單。
public static void mergeSortNor(int[] array){
int size=array.length;
int gap=1;
while(gap<size){
for(int i=0;i<size;i+=2*gap){
//劃分好要歸並的區域，第一次每個區間隻有一個元素
//[left,mid)
int left=i;
int mid=left+gap;
//[mid,right)
int right=mid+gap;
if(mid>size){
mid=size;
}
if(right>size){
right=size;
}
int[] temp=new int[size];
//二路歸並
mergeData(array,left,mid,right,temp);
//將temp中的元素拷貝回原數組中
System.arraycopy(temp,left,array,left,right-left);
}
//gap值翻二倍，繼續歸並
gap<<=1;
}
}
相關特性總結：
時間復雜度：O(NlogN)
空間復雜度：O(N)
穩定性：穩定
缺點在於需要O(N)的空間復雜度，歸並排序解決更多的是磁盤中的外排序問題
到此這篇關於Java中七種排序算法總結分析的文章就介紹到這瞭,更多相關Java 排序算法內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！