java中的常見排序示例代碼(含優(yōu)化方案和拓展方法)
更新時間：2026年01月07日 10:02:21 作者：YOU?OU
在Java中常見的排序算法包括冒泡排序、選擇排序、插入排序、希爾排序、歸并排序、快速排序和堆排序等,這篇文章主要介紹了java中常見排序(含優(yōu)化方案和拓展方法)的相關(guān)資料,需要的朋友可以參考下
常見的排序方法有以下7種，會一一講解，外加拓展的計數(shù)排序
一. 直接插入排序
public static void insetSort(int[] array){
for(int i=1;i<array.length;i++){
int j=i -1;
int tmp=array[i];
for(;j>=0;j--){
if(array[j]>tmp){
array[j+1]=array[j];
}else{
array[j+1]=tmp;
break;
}
}
array[j+1]= tmp;
}
}時間復(fù)雜度：O（N^2）
最壞情況下（逆序） 5 4 3 2 1
最好情況下（本身是有序的）O（N）
如果數(shù)據(jù)越有序，直接插入排序越快
空間復(fù)雜度：O（1）
穩(wěn)定性：穩(wěn)定的排序
本身如果是一個穩(wěn)定的排序，可以實現(xiàn)為不穩(wěn)定的
但是 如果一個排序 本身就是不穩(wěn)定，不能實現(xiàn)為穩(wěn)定的排序
二. 希爾排序
public static void shellSort(int[]array){
int gap=array.length;
while(gap>1){
gap=gap/2;
shell(array,gap);
}
}
private static void shell(int[] array, int gap) {
for(int i=gap;i<array.length;i++){
int j=i -gap;
int tmp=array[i];
for(;j>=0;j-=gap){
if(array[j]>tmp){
array[j+gap]=array[j];
array[j]=tmp;
}else{
array[j+gap]=tmp;
break;
}
}
array[j+gap]= tmp;
}
}時間復(fù)雜度： O（N^1.3~N^1.5）
空間復(fù)雜度：O（1)
穩(wěn)定性：不穩(wěn)定
三. 選擇排序
private static void swap(int[] array,int i,int j){
int tmp=array[i];
array[i]=array[j];
array[j]=tmp;
}方法一
public static void selectSort(int[] array){
int left=0;
int right=array.length-1;
while(left<right){
int minIndex=left;
int maxIndex=left;
for (int i = left+1; i <=right; i++) {
if(array[i]<array[minIndex]){
minIndex=i;
}
if(array[i]>array[maxIndex]){
maxIndex=i;
}
}
swap(array,left,minIndex);
if(maxIndex==0){
maxIndex=minIndex;
}
swap(array,right,maxIndex);
left++;
right--;
}
}方法二
public static void selectSort1(int[] array){
for (int i = 0; i < array.length; i++) {
int minIndex=i;
for (int j = i+1; j < array.length; j++) {
if(array[j]<array[minIndex]){
minIndex=j;
}
}
swap(array,i,minIndex);
}
}時間復(fù)雜度：O（N^2）
和數(shù)據(jù)是否與有序無關(guān)
空間復(fù)雜度：O（1）
穩(wěn)定性：不穩(wěn)定
四. 堆排序
private static void swap(int[] array,int i,int j){
int tmp=array[i];
array[i]=array[j];
array[j]=tmp;
}public static void heapsort(int[] array){
createHeap(array);
int end= array.length-1;
while(end>0){
swap(array,0,end);
siftDown(array,0,end);
end--;
}
}
private static void createHeap(int[] array){
for (int parent = (array.length-1-1)/2; parent>=0; parent--) {
siftDown(array,parent,array.length);
}
}
private static void siftDown(int[] array, int parent, int end) {
int child=parent*2+1;
while(child<end){
if(child+1<end && array[child]<array[child+1]){
child++;
}
if(array[child]>array[parent]){
swap(array,parent,child);
parent=child;
child=parent*2+1;
}else{
break;
}
}
}時間復(fù)雜度：O（n*logN）
空間復(fù)雜度：O（1）
穩(wěn)定性：不穩(wěn)定
五. 冒泡排序
加入flg的判斷是為了優(yōu)化此排序
public static void bubbleSort(int[]array){
for (int i = 0; i < array.length-1; i++) {
boolean flg=false;
for (int j = 0; j < array.length-1-i; j++) {
if(array[j]>array[j+1]){
swap(array,j,j+1);
flg=true;
}
}
if(!flg){
break;
}
}
}時間復(fù)雜度：O（N^2）
注意：冒泡排序優(yōu)化前的時間復(fù)雜度為O（
），優(yōu)化后可以達到O（N）
空間復(fù)雜度：O（1）
穩(wěn)定性：穩(wěn)定
六. 快速排序（已優(yōu)化）
insertSortRange() getMiddleNum() 是為了優(yōu)化快速排序
private static void swap(int[] nums,int i,int j){
int tmp=nums[i];
nums[i]=nums[j];
nums[j]=tmp;
} public static void quickSort(int[] array) {
//quick(array,0,array.length-1);
quickNor(array,0,array.length-1);
}private static void quick(int[] array,int start,int end){
if(start>=end){
return;
}
if(end-start+1<=10){
insertSortRange(array,start,end);
return ;
}
int midIndex=getMiddleNum(array,start,end);
swap(array,start,midIndex);
int pivot=partition(array,start,end);
quick(array,start,pivot-1);
quick(array,pivot+1,end);
} private static void insertSortRange(int[] array,int start,int end){
for(int i=start+1;i<=end;i++){
int j=i -1;
int tmp=array[i];
for(;j>=0;j--){
if(array[j]>tmp){
array[j+1]=array[j];
}else{
array[j+1]=tmp;
break;
}
}
array[j+1]= tmp;
}
} private static int getMiddleNum(int[] array,int left,int right){
int mid=(left+right)/2;
if(array[left]<array[right]){
if(array[left]>array[mid]){
return left;
}else if(array[right]<array[mid]){
return right;
}else{
return mid;
}
}else{
if(array[right]>array[mid]){
return right;
}else if(array[left]<array[mid]){
return right;
}else{
return mid;
}
}
} private static int partition2(int[] array, int left, int right){
int tmp=array[left]; //挖坑法
while(left<right){
while(left<right && array[right]>=tmp){
right--;
}
array[left]=array[right];
while(left<right && array[left]<=tmp){
left++;
}
array[right]=array[left];
}
array[left]=tmp;
return left;
}時間復(fù)雜度：O（N*logN）
最壞情況下： 當(dāng)數(shù)據(jù)給的是1 2 3 4 5 6 7 ……
9 8 7 6 5 4 1 ……
有序的情況下：O（N^2）
最好的情況下：O（N*logN）
注意：一般情況下，說快速排序的時間復(fù)雜度默認為 O（N*logN） 優(yōu)化過后
空間復(fù)雜度：O(logN)
最壞情況下：O(N)
最好情況下：O(logN)
穩(wěn)定性：不穩(wěn)定
拓展：
1.partition的實現(xiàn)方法
一共有三種實現(xiàn)方法：挖坑法（推薦）
Hoare版
前后指針法
//挖坑法
private static int partition2(int[] array, int left, int right){
int tmp=array[left]; //挖坑法
while(left<right){
while(left<right && array[right]>=tmp){
right--;
}
array[left]=array[right];
while(left<right && array[left]<=tmp){
left++;
}
array[right]=array[left];
}
array[left]=tmp;
return left;
} //hoare版
private static int partitionHoare(int[] array, int left, int right){
int tmp=array[left];
int tmpLeft=left;
while(left<right){
while(left<right && array[right]>=tmp){
right--;
}
while(left<right && array[left]<=tmp){
left++;
}
swap(array,left,right);
}
swap(array,left,tmpLeft);
return left;
} //前后指針法
private static int partition(int[] array, int left, int right){
int cur=left+1;
int prev=left;
while(cur<=right){
if(array[cur]<array[left] && array[++prev]!=array[cur]){
swap(array,cur,prev);
}
cur++;
}
swap(array,prev,left);
return prev;
}2.非遞歸quick實現(xiàn)方法
public static void quickNor(int[] array,int start,int end){
Deque<Integer> stack =new ArrayDeque<>();
int pivot=partition(array,start,end);
if(pivot>start+1){
stack.push(start);
stack.push(pivot-1);
}
if(pivot<end-1){
stack.push(pivot+1);
stack.push(end);
}
while(!stack.isEmpty()){
end=stack.pop();
start=stack.pop();
pivot=partition(array,start,end);
if(pivot>start+1){
stack.push(start);
stack.push(pivot-1);
}
if(pivot<end-1){
stack.push(pivot+1);
stack.push(end);
}
}
}七. 歸并排序
public static void mergesort(int[] array){
mergeSortTmp(array,0,array.length-1);
} private static void mergeSortTmp(int[] array,int left,int right){
if(left>=right){
return;
}
int mid=(left+right)/2;
mergeSortTmp(array,left,mid);
mergeSortTmp(array,mid+1,right);
merge(array,left,mid,right);
}
private static void merge(int[] array, int left, int mid, int right){
int[] tmp=new int[[right-left+1];
int k=0;
int s1=left;
int s2=mid+1;
while(s1<=mid && s2<=right){
if(array[s1]<array[s2]){
tmp[k++]=array[s1++];
}else{
tmp[k++]=array[s2++];
}
}
while(s1<=mid){
tmp[k++]=array[s1++];
}
while(s2<=right){
tmp[k++]=array[s2++];
}
for (int i = 0; i < k; i++) {
array[i+left]=tmp[i];
}
}時間復(fù)雜度：O（N*logN）
空間復(fù)雜度：O（N）
穩(wěn)定性：穩(wěn)定
拓展：非遞歸實現(xiàn)
public static void mergeSortNor(int[] array){
int gap=1;
while(gap<array.length){
for (int i = 0; i < array.length; i=i+gap*2) {
int left=i;
int mid=left+gap-1;
if(mid>=array.length){
mid=array.length-1;
}
int right=mid+gap;
if(right>=array.length){
right=array.length-1;
}
merge(array,left,mid,right);
}
gap*=2;
}
}八. 計數(shù)排序（非基于比較排序）
public static void countSort(int[] array){
int maxVal=array[0];
int minVal=array[0];
for (int i = 0; i < array.length; i++) {
if(minVal>array[i]){
minVal=array[i];
}
if(maxVal<array[i]){
maxVal=array[i];
}
}
int len=maxVal-minVal+1;
int[] count=new int[len];
for (int i = 0; i < array.length; i++) {
int index=array[i];
count[index-minVal]++;
}
int index=0;
for (int i = 0; i < count.length; i++) {
while(count[i]!=0){
array[index]=i+minVal;
index++;
count[i]--;
}
}
}適用范圍：數(shù)據(jù)集中在一定的范圍內(nèi)
如：0~9 89~99 等
時間復(fù)雜度：O（范圍+N）
范圍越大 越慢
空間復(fù)雜度：O（范圍）
穩(wěn)定性：穩(wěn)定
總結(jié)：
穩(wěn)定的排序：
冒泡排序、插入排序、歸并排序
表格對比：
到此這篇關(guān)于java中常見排序的文章就介紹到這了,更多相關(guān)java常見排序內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
教你用java?stream對集合中的對象按指定字段進行分組并統(tǒng)計
這篇文章主要給大家介紹了關(guān)于用java?stream對集合中的對象按指定字段進行分組并統(tǒng)計的相關(guān)資料,本文主要介紹了如何利用Java的Stream流來實現(xiàn)在list集合中,對具有相同name屬性的對象進行匯總計算的需求,需要的朋友可以參考下2024-10-10
Intellij IDEA創(chuàng)建spring-boot項目的圖文教程
本文通過圖文并茂的形式給大家介紹了Intellij IDEA創(chuàng)建spring-boot項目的教程，本文給大家介紹的非常詳細，具有參考借鑒價值，需要的朋友參考下吧2018-01-01
詳解MyBatis開發(fā)Dao層的兩種方式（Mapper動態(tài)代理方式）
這篇文章主要介紹了詳解MyBatis開發(fā)Dao層的兩種方式（Mapper動態(tài)代理方式），小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2018-12-12
文章介紹了如何使用ClassPathScanningCandidateComponentProvider從指定包中掃描接口實現(xiàn)類,并通過接口統(tǒng)一管理和獲取實現(xiàn)對象,這種方法避免了手動創(chuàng)建對象和修改代碼的問題,并且可以處理鏈路方式下的多處理器順序處理2025-11-11
Java虛擬機之對象創(chuàng)建過程與類加載機制及雙親委派模型
這篇文章主要給大家介紹了關(guān)于Java虛擬機之對象創(chuàng)建過程與類加載機制及雙親委派模型的相關(guān)資料,本文通過示例代碼以及圖文介紹的非常詳細,對大家學(xué)習(xí)或者使用java具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2021-11-11
這篇文章主要介紹了說明Java的傳遞與回調(diào)機制的代碼示例分享,傳遞與回調(diào)機制是Java入門學(xué)習(xí)中的基礎(chǔ)知識,需要的朋友可以參考下2015-09-09
OOM是JVM拋出的錯誤,表示內(nèi)存分配失敗,這篇文章主要介紹了線上Java?OOM問題定位與解決方案的相關(guān)資料,文中通過代碼介紹的非常詳細,需要的朋友可以參考下2025-09-09
jedis獲取redis中二進制圖片轉(zhuǎn)Base64方式
這篇文章主要介紹了jedis獲取redis中二進制圖片轉(zhuǎn)Base64方式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-07-07
Java線程編程中isAlive()和join()的使用詳解
這篇文章主要介紹了Java線程編程中isAlive()和join()的使用詳解,是Java入門學(xué)習(xí)中的基礎(chǔ)知識,需要的朋友可以參考下2015-09-09
2022?最新?IntelliJ?IDEA?詳細配置步驟演示(推薦)
作為一名開發(fā)人員，第一肯定是選擇一款趁手的開發(fā)利器，本人使用?Java?偏多，這里推薦使用?IntelliJ?IDEA,?俗稱神級開發(fā)工具，具體的安裝過程就不過多贅述了，有需要了解的朋友可以參考下本文2022-09-09