Java中七種排序算法總結分析
前言：對文章出現(xiàn)的一些名詞進行解釋
排序： 使一串記錄，按照其中的某個或某些關鍵字的大小，遞增或者遞減排列起來的操作。
穩(wěn)定性： 假定在排序的記錄序列中，存在多個具有相同的關鍵字的記錄，若經(jīng)過排序，這些記錄的相對次序保持不變，即在原序列中，a=b，且a在b之前，而在排序后的序列中，a仍然在b之前則這種排序算法是穩(wěn)定的，否則就是不穩(wěn)定的。
內部排序： 數(shù)據(jù)元素全部放在內存中的排序。
外部排序： 數(shù)據(jù)元素太多不能同時放在內存中，根據(jù)排序過程的要求不能在內外存之間移動數(shù)據(jù)的排序。
文中所有排序都是升序。
一、插入排序
直接插入排序是一種簡單的插入排序法。
1.基本思想
把待排序的記錄按照其關鍵碼值的大小逐個插入到一個已經(jīng)排好序的有序序列中，直到所有記錄全部插完為止，得到一個新的有序序列。這種思想在我們玩撲克牌的時候用到過，在我們碼牌時，抽出一個牌，會從后往前依次比較牌面值，然后插入到一個比前面大且比后面小的位置中。
2.直接插入排序
步驟：
1.第一次排序先將第一個元素看成是已排序區(qū)間，將其內容保存起來
2.待排序區(qū)間是其后面的所有元素，從其后面第一個開始，依次和已排序區(qū)間里的元素比較（這里的比較是從后向前比較，也就是從其前一個元素比較到0號位置的元素）
3.如果小于已排序區(qū)間中的元素，則將該位置向后挪一位
4.直到找到第一個比其小的元素，此時其后面的所有元素都是比它大的，且都向后挪了一位，這時其后面的位置是空的，將該元素放進來即可。
5.之后取第二個，第三個…第i個依次這樣比較即可，即循環(huán)起來。其中每次[0,i)是已排序區(qū)間，[i,size)是待排序區(qū)間。
動圖演示：
代碼實現(xiàn)：
public static void insertSort(int[] array){
int j=0;
//i位置與之前所有下標從后往前進行比較，該位置大于i則繼續(xù)往前，小于則插入到后邊
//[0,bound)已排序區(qū)間
//[bound,size)待排序區(qū)間
for(int bound=1;bound<array.length;bound++) {
int temp = array[bound];
//先取已排序區(qū)間的最后一個，依次往前進行比較
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)
穩(wěn)定性：穩(wěn)定（是從后往前依次比較的）
應用場景：元素越接近有序越好（因為越接近有序比較次數(shù)就會越少，算法的時間效率就會越高）
3.希爾排序(縮小增量排序)
基本思想：
把待排序區(qū)間中所有記錄分成幾個組，設置一個gap值，所有距離為gap的記錄分在同一組內，并分別對每個組內的記錄進行排序，然后讓gap以一定的規(guī)律減小，然后重復上述分組和排序的工作，當gap達到1時，所有記錄已經(jīng)排好序。
步驟：
1.設置gap值（每個組內元素之間間隔）
2.在每個組內進行直接插入排序
3.縮小gap值（這里我按照2倍縮小）
4.gap為1時排序完畢
圖象解釋：
代碼實現(xiàn)：
public static void shellSort(int[] array){
int gap= array.length/2;
while(gap>0){
int j=0;
//i位置與之前所有下標從后往前進行比較，該位置大于i則繼續(xù)往前，小于則插入到后邊
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;
}
}
相關特性總結：
希爾排序是對直接插入排序的優(yōu)化
當gap>1時都是預排序，目的是讓數(shù)組更接近有序，當gap==1時，數(shù)組已經(jīng)接近有序，這樣就很會快，整體而言，可以達到優(yōu)化的效果
時間復雜度不確定，因為gap取值方法有很多
空間復雜度：O(1)
穩(wěn)定性：不穩(wěn)定（元素之間是跳著交換的）
二、選擇排序
1.基本思想
每一次從待排序的數(shù)據(jù)元素中選出最?。ɑ蜃畲螅┑囊粋€元素，存放在序列的起始位置，直到全部待排序的數(shù)據(jù)元素排完。
2.直接選擇排序
步驟：
1.先記錄下標為0元素為最小值
2.從下標為1開始往后遍歷，遇到比最小值還小的就標記起來，遍歷完成即找到最小值
3.將找到的最小值與下標為0的元素進行交換
4.此時[0,1）為已排序區(qū)間，即不再動，[1,size)是待排序區(qū)間
5.從下標為1繼續(xù)上面的操作，即循環(huán)起來
6.循環(huán)到最后只剩一個元素結束，排序完成
動圖演示：
代碼實現(xiàn)：
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;
}
}
//將最小值與待排序區(qū)間第一個進行交換
swap(nums,bound,min);
}
}
相關特性總結：
時間復雜度：O(N2)
空間復雜度：O(1)
穩(wěn)定性：不穩(wěn)定
效率不是很好，實際中很少使用
3.堆排序
堆排序是指利用堆這種數(shù)據(jù)結構所設計的一種排序算法，它是選擇排序的一種。它是通過堆來進行選擇數(shù)據(jù)。
注意：排升序要建大堆，排降序要建小堆
步驟：
1.創(chuàng)建一個大堆（升序）
從倒數(shù)第一個非葉子結點開始向下調整，直到根結點，創(chuàng)建一個大堆
2.將根結點與最后一個結點進行交換，此時最后一個元素一定是所有元素中最大的
3.將size–
4.將堆繼續(xù)調整好形成一個大堆，繼續(xù)上面的操作，即循環(huán)起來
5.最終排序完成
圖像解釋：
代碼實現(xiàn)：
//寫一個交換函數(shù)
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){
//創(chuàng)建一個堆
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)
穩(wěn)定性：不穩(wěn)定
使用堆來選數(shù)，效率高了很多
三、交換排序
1.基本思想
交換，就是根據(jù)序列中兩個記錄鍵值的比較結果來兌換這兩個記錄在序列中的位置，交換序列的特點是：將鍵值較大的記錄向序列的尾部移動，鍵值較小的記錄向序列的頭部移動
2.冒泡排序
步驟：
1.從0號位置開始，將元素和他后面的元素比較，如果大于則交換
2.當遍歷完成，最大的元素肯定在數(shù)組的最后
3.之后再比較時，最后一個元素就是已排序區(qū)間，不再參與比較
4.重復上述步驟，即循環(huán)起來
動圖演示：
代碼實現(xiàn)：
public static void bubbleSort(int[] nums) {
//外層循環(huán)控制循環(huán)次數(shù)
for(int num=1;num<nums.length;num++){
//內層循環(huán)控制交換哪兩個元素
for(int i=0;i<nums.length-num;i++){
if(nums[i+1]<nums[i]){
swap(nums,i+1,i);
}
}
}
}
相關特性總結：
時間復雜度：O(N2)
空間復雜度：O(1)
穩(wěn)定性：穩(wěn)定
冒泡排序在最開始就已經(jīng)學到，很容易理解
3.快速排序（遞歸與非遞歸）
快速排序是Hoare于1962年提出的一種二叉樹結構的交換排序方法，其基本思想為：任取待排序元素序列中的某元素作為基準值，按照該基準值將待排序集合分割成兩子序列，左子序列中所有元素均小于基準值，右子序列中所有元素均大于基準值，然后左右子序列重復該過程，直到所有元素都排列在相應的位置上為止。
主框架實現(xiàn)：
public static void quickSort(int[] array,int left,int right){
if((right-left)<=1){
return;
}
//按照基準值對array數(shù)組的[left,right)區(qū)間中的元素進行劃分
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);
}
從上述程序可以看出，程序結構與二叉樹前序遍歷規(guī)則非常像。
接下來按照基準值劃分就是快排的核心，常見方法有三種：
1.Hoare版
步驟：
1.這里我們取最右側為基準值
2.設置begin和end用來標記，讓begin從左往右走，end從右往左走
3.當begin小于end時，因為我們取得基準值為最右側，所以應先讓begin從左往右走，找到比基準值大的元素就停下來
4.這時讓end從右往左走，找到比基準值小的元素就停下來，兩者交換位置
5.循環(huán)起來
6.當循環(huán)結束時，兩個最終走到了同一個位置，將其和基準值進行交換
動圖演示：
代碼實現(xiàn)：
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--;
}
//當兩個在同一個位置時，不需要交換，減少交換次數(shù)
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.就這樣一直循環(huán)，互相填坑，直到不滿足循環(huán)條件
6.這時begin和end在同一個坑位，且是最后一個坑位，使用基準值填充
圖象解釋：
代碼實現(xiàn)：
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.前后標記法（難理解）
小編其實也是根據(jù)大佬的代碼分析出來的，要問為什么這么做咱確實也是不太理解，另外如理解錯誤歡迎指正
這里真誠發(fā)問，大佬們的腦子是不是和我的腦子不太一樣？
步驟：
1.采用cur和prev來標記，兩者都是從左往右走，不一樣的是，最開始cur在0號位置，prev在cur前一個位置上
2.當遇到比temp大的元素時，prev不動，cur向前走一步，當兩者一前一后的狀態(tài)時，cur也會往前走一步，而prev不動
3.這樣兩者逐漸拉開差距，此時遇到比基準值小的元素，cur中的元素就會與prev中的元素交換
4.走到最后prev的下一個元素與基準值位置交換
圖象解釋：
代碼實現(xiàn)：
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;
}
但是會發(fā)現(xiàn)：
當我們選取的基準值越靠近整個數(shù)組的中間時，效率越好，這時可以看作是將數(shù)組逐漸分成了一個滿二叉樹，因此效率為O(NlogN)
最差時是取到其最大或者最小的元素，還是要劃分n次，效率為O(N2)
一般時間復雜度都是看起最差情況，那為什么快速排序的時間復雜度是O(NlogN)呢？
其實是可以對取基準值進行優(yōu)化的，詳情請看下面：
4.快速排序優(yōu)化
1.三數(shù)取中法選temp
之前我們只取一個基準值
優(yōu)化后，我們在左邊取一個，中間取一個，右邊取一個
比較三個數(shù)的大小，誰在中間就取誰為基準值
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.遞歸到小的子區(qū)間時，可以考慮使用插入排序
在Idea的內層方法中，用的是小于47使用直接插入排序
5.快速排序非遞歸
如果直接轉為循環(huán)不好轉，之前提到可以使用棧來實現(xiàn)，利用棧后進先出的特性
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)(遞歸單次沒有借助輔助空間，高度即是深度)
穩(wěn)定性：不穩(wěn)定
快速排序整體綜合性能和使用場景都是比較好的，所以才叫快速排序
四、歸并排序（遞歸與非遞歸）
歸并排序是建立在歸并操作上的一種有效的排序算法，該算法是采用分治法的一個非常典型的應用。將已有的子序列合并，得到完全有序的序列，即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為二路歸并。
動圖演示：
歸并排序核心步驟：將兩個有序數(shù)組合并成一個有序數(shù)組
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++];
}
}
//看兩個數(shù)組哪個還沒有遍歷完成，直接順次放入temp數(shù)組的后面
while(begin1<end1){
temp[index++] = array[begin1++];
}
while(begin2<end2){
temp[index++]=array[begin2++];
}
}
主程序（遞歸）：
步驟：
1.先對待排序區(qū)間進行均分為兩個
2.使用遞歸，直到均分為每個區(qū)間只剩下一個元素時，每兩個使用二路歸并
3.將兩個有序數(shù)組合并為一個有序數(shù)組，將結果保存在temp中
4.最終temp保存的就是排序完成的數(shù)組，再拷貝回原數(shù)組中
private static void mergeSort(int[] array,int left,int right,int[] temp){
if((right-left>1)){
//先對[left,right)區(qū)間中的元素進行均分
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中的元素拷貝回原數(shù)組中
System.arraycopy(temp,left,array,left,right-left);
}
}
主程序（非遞歸）：
直接采用gap對數(shù)組進行分割，每次分割完成對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){
//劃分好要歸并的區(qū)域，第一次每個區(qū)間只有一個元素
//[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中的元素拷貝回原數(shù)組中
System.arraycopy(temp,left,array,left,right-left);
}
//gap值翻二倍，繼續(xù)歸并
gap<<=1;
}
}
相關特性總結：
時間復雜度：O(NlogN)
空間復雜度：O(N)
穩(wěn)定性：穩(wěn)定
缺點在于需要O(N)的空間復雜度，歸并排序解決更多的是磁盤中的外排序問題
到此這篇關于Java中七種排序算法總結分析的文章就介紹到這了,更多相關Java 排序算法內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
本文主要介紹了Spring核心IoC和AOP的相關知識。具有很好的參考價值，下面跟著小編一起來看下吧2017-03-03
這篇文章主要為大家介紹了Java?NIO?通道概念選擇器使用示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪2023-10-10
SpringBoot集成shiro,MyRealm中無法@Autowired注入Service的問題
今天小編就為大家分享一篇關于SpringBoot集成shiro,MyRealm中無法@Autowired注入Service的問題，小編覺得內容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧2019-03-03
springboot Interceptor攔截器excludePathPatterns忽略失效
這篇文章主要介紹了springboot Interceptor攔截器excludePathPatterns忽略失效的問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-07-07
Java對數(shù)組實現(xiàn)選擇排序算法的實例詳解
這篇文章主要介紹了Java對數(shù)組實現(xiàn)選擇排序算法的實例,選擇排序的比較次數(shù)為 O(N^2)而交換數(shù)為O(N),需要的朋友可以參考下2016-04-04
這篇文章主要介紹了Java ServletContext對象用法解析,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2020-05-05
這篇文章主要介紹了利用Java OpenCV實現(xiàn)圖像背景的切換，文中的示例代碼講解詳細。對我們學習OpenCV有一定幫助，感興趣的同學可以了解一下2022-01-01
這篇文章主要介紹了java瀏覽器文件打包下載過程解析,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2019-10-10
java中通用的線程池實例代碼，需要的朋友可以參考一下2013-03-03
Spring實戰(zhàn)之使用c:命名空間簡化配置操作示例
這篇文章主要介紹了Spring實戰(zhàn)之使用c:命名空間簡化配置操作,結合實例形式詳細分析了Spring使用c:命名空間簡化配置的相關接口與配置操作技巧,需要的朋友可以參考下2019-12-12