java中的常見(jiàn)排序示例代碼(含優(yōu)化方案和拓展方法)
更新時(shí)間：2026年01月07日 10:02:21 作者：YOU?OU
在Java中常見(jiàn)的排序算法包括冒泡排序、選擇排序、插入排序、希爾排序、歸并排序、快速排序和堆排序等,這篇文章主要介紹了java中常見(jiàn)排序(含優(yōu)化方案和拓展方法)的相關(guān)資料,需要的朋友可以參考下
常見(jiàn)的排序方法有以下7種，會(huì)一一講解，外加拓展的計(jì)數(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;
}
}時(shí)間復(fù)雜度：O（N^2）
最壞情況下（逆序） 5 4 3 2 1
最好情況下（本身是有序的）O（N）
如果數(shù)據(jù)越有序，直接插入排序越快
空間復(fù)雜度：O（1）
穩(wěn)定性：穩(wěn)定的排序
本身如果是一個(gè)穩(wěn)定的排序，可以實(shí)現(xiàn)為不穩(wěn)定的
但是 如果一個(gè)排序 本身就是不穩(wěn)定，不能實(shí)現(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;
}
}時(shí)間復(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);
}
}時(shí)間復(fù)雜度：O（N^2）
和數(shù)據(jù)是否與有序無(wú)關(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;
}
}
}時(shí)間復(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;
}
}
}時(shí)間復(fù)雜度：O（N^2）
注意：冒泡排序優(yōu)化前的時(shí)間復(fù)雜度為O（
），優(yōu)化后可以達(dá)到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;
}時(shí)間復(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）
注意：一般情況下，說(shuō)快速排序的時(shí)間復(fù)雜度默認(rèn)為 O（N*logN） 優(yōu)化過(guò)后
空間復(fù)雜度：O(logN)
最壞情況下：O(N)
最好情況下：O(logN)
穩(wěn)定性：不穩(wěn)定
拓展：
1.partition的實(shí)現(xiàn)方法
一共有三種實(shí)現(xiàn)方法：挖坑法（推薦）
Hoare版
前后指針?lè)?/p>
//挖坑法
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;
} //前后指針?lè)?
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實(shí)現(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];
}
}時(shí)間復(fù)雜度：O（N*logN）
空間復(fù)雜度：O（N）
穩(wěn)定性：穩(wěn)定
拓展：非遞歸實(shí)現(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;
}
}八. 計(jì)數(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 等
時(shí)間復(fù)雜度：O（范圍+N）
范圍越大 越慢
空間復(fù)雜度：O（范圍）
穩(wěn)定性：穩(wěn)定
總結(jié)：
穩(wěn)定的排序：
冒泡排序、插入排序、歸并排序
表格對(duì)比：
到此這篇關(guān)于java中常見(jiàn)排序的文章就介紹到這了,更多相關(guān)java常見(jiàn)排序內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
Java使用pdfbox實(shí)現(xiàn)給pdf文件加圖片水印
有時(shí)候需要給pdf加水印，市面上工具都是收費(fèi)的要會(huì)員，還是自食其力吧；嘗試過(guò) spire.pdf.free 那個(gè)超過(guò)10頁(yè)就不行了！所以本文還是使用了pdfbox，感興趣的可以了解一下2022-11-11
這篇文章主要介紹了 Java 比較字符串實(shí)例詳解的相關(guān)資料,需要的朋友可以參考下2017-06-06
這篇文章主要介紹了C語(yǔ)言指針數(shù)組案例詳解,本文通過(guò)案例詳細(xì)的解釋了指針與數(shù)組的初始化還有關(guān)系與應(yīng)用,需要的朋友可以參考下這篇文章2021-07-07
這篇文章主要介紹了詳談java集合框架 ,需要的朋友可以參考下2015-05-05
本篇文章主要介紹了java 兩個(gè)數(shù)組合并的方法，小編覺(jué)得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2017-08-08
RocketMQ?Broker消息如何刷盤(pán)源碼解析
這篇文章主要為大家介紹了RocketMQ?Broker消息如何刷盤(pán)源碼解析，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2023-05-05
Spring中InitializingBean接口和@PostConstruct注解的使用詳解
InitializingBean 是 Spring 框架中的一個(gè)接口,用在 Bean 初始化后執(zhí)行自定義邏輯,@PostConstruct 是 Java EE/Jakarta EE 中的一個(gè)注解用于標(biāo)記一個(gè)方法在依賴(lài)注入完成后執(zhí)行初始化操作,下面我們就來(lái)深入了解下二者的使用吧2025-04-04
在 java web開(kāi)發(fā)過(guò)程中，難免會(huì)有一些系統(tǒng)異?；蛉藶楫a(chǎn)生一些異常。在 RESTful springboot 項(xiàng)目中如何優(yōu)雅的處理？下面腳本之家小編給大家?guī)?lái)了springboot 錯(cuò)誤處理小結(jié)，感興趣的朋友一起看看吧2018-03-03
Java實(shí)現(xiàn)仿淘寶滑動(dòng)驗(yàn)證碼研究代碼詳解
這篇文章主要介紹了Java實(shí)現(xiàn)仿淘寶滑動(dòng)驗(yàn)證碼研究代碼詳解的相關(guān)資料,非常不錯(cuò)，具有參考借鑒價(jià)值，需要的朋友可以參考下2016-06-06
這篇文章主要介紹了通過(guò)實(shí)例了解java序列化機(jī)制,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2019-11-11