Java超詳細(xì)整理講解各種排序
更新時(shí)間：2022年07月29日 09:20:07 作者：菜菜不恰菜
這篇文章主要介紹了Java常用的排序算法及代碼實(shí)現(xiàn),在Java開(kāi)發(fā)中，對(duì)排序的應(yīng)用需要熟練的掌握，這樣才能夠確保Java學(xué)習(xí)時(shí)候能夠有扎實(shí)的基礎(chǔ)能力。那Java有哪些排序算法呢？本文小編就來(lái)詳細(xì)說(shuō)說(shuō)Java常見(jiàn)的排序算法,需要的朋友可以參考一下
穩(wěn)定性
兩個(gè)相等的數(shù)據(jù)，如果經(jīng)過(guò)排序后，排序算法能保證其相對(duì)位置不發(fā)生變化，則我們稱(chēng)該算法是具備穩(wěn)定性的排序算法。
直接插入排序
直接插入排序就是每次選擇無(wú)序區(qū)間的第一個(gè)元素，在有序區(qū)間內(nèi)選擇合適的位置插入。
從數(shù)組下標(biāo)為1開(kāi)始，將下標(biāo)為1上的值取出來(lái)放在tmp中，然后它和前面的下標(biāo)j上的值進(jìn)行比較，如果前面下標(biāo)j上的值比它大，則前面下標(biāo)j上的值往后走一步，直到比到j(luò)回退到了-1或者j下標(biāo)上的值比tmp小為止，然后把tmp插入到下標(biāo)為[j+1]的位置上。然后i就繼續(xù)往后走，繼續(xù)比較，直到i走到數(shù)組的最后。
代碼示例：
/**
*直接插入排序
*時(shí)間復(fù)雜度 O(N^2)
*空間復(fù)雜度 O(1)
*穩(wěn)定性 ：穩(wěn)定（看在比較的過(guò)程當(dāng)中是否發(fā)生了跳躍式的交換，如果發(fā)生了跳躍式的交換那么就是不穩(wěn)定的排序）
* 一個(gè)穩(wěn)定的排序，可以實(shí)現(xiàn)為不穩(wěn)定的排序
* 但是一個(gè)本身就不穩(wěn)定的排序，是不可以變成穩(wěn)定的排序的
* 經(jīng)常使用在數(shù)據(jù)量不多且整體數(shù)據(jù)趨于有序了
*/
public static void insertSort(int[] array) {
for(int i=1;i<array.length;i++) {
int tmp = array[i];
int j = 0;
for (j = i - 1; j >= 0; j--) {
if (tmp < array[j]) {
array[j + 1] = array[j];
} else {
break;
}
}
array[j + 1] = tmp;
}
}希爾排序
希爾排序是對(duì)直接插入排序的優(yōu)化。將數(shù)據(jù)進(jìn)行相應(yīng)的分組，分為gap組，然后按照直接插入排序的方法排序。 當(dāng)gap > 1時(shí)都是預(yù)排序，目的是讓數(shù)組更接近于有序。當(dāng)gap == 1時(shí)，數(shù)組已經(jīng)接近有序的了，這樣就會(huì)很快。這樣整體而言，可以達(dá)到優(yōu)化的效果。
/**
* 時(shí)間復(fù)雜度（和增量有關(guān)系的）：O(n^1.3 - n^1.5)
* 空間復(fù)雜度：O(1)
* 穩(wěn)定性：不穩(wěn)定的
* 看在比較的過(guò)程當(dāng)中是否發(fā)生了跳躍式的交換，如果發(fā)生了跳躍式的交換那么就是不穩(wěn)定的排序
*/
public static void shellSort(int[] array) {
int gap=array.length-1;
while(gap>1){
shell(array,gap);
gap/=2;
}
shell(array,1);//保證最后是1組
}
public static void shell(int[] array,int gap) {
for(int i=gap;i< array.length;i++){
int tmp=array[i];
int j=i-gap;
for (j = i-gap; j >=0; j=j-gap) {
if(tmp<array[j]){
array[j+gap]=array[j];
}else{
break;
}
}
array[j+gap]=tmp;
}
}選擇排序
每一次從無(wú)序區(qū)間選出最大（或最?。┑囊粋€(gè)元素，存放在無(wú)序區(qū)間的最后（或最前），直到全部待排序的數(shù)據(jù)元素排完 。
代碼示例：
/**
*選擇排序
*空間復(fù)雜度：O(N^2)
* 時(shí)間復(fù)雜度：O(1)
* 穩(wěn)定性：不穩(wěn)定
* 看在比較的過(guò)程當(dāng)中是否發(fā)生了跳躍式的交換，如果發(fā)生了跳躍式的交換那么就是不穩(wěn)定的排序
*/
public static void selectSort(int[] array){
for(int i=0;i<array.length;i++){
for(int j=i+1;j< array.length;j++){
if(array[j]<array[i]){
swap(array,i,j);
}
}
}
}
public static void swap(int[] array,int i,int j){
int tmp=array[i];
array[i]=array[j];
array[j]=tmp;
}
//選擇排序還可以找到最小值下標(biāo)再交換
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++) {
//找到最小值下標(biāo)
if(array[j] < array[minIndex]) {
minIndex = j;
}
}
swap(array,i,minIndex);
}堆排序
基本原理也是選擇排序，只是不在使用遍歷的方式查找無(wú)序區(qū)間的最大的數(shù)，而是通過(guò)堆來(lái)選擇無(wú)序區(qū)間的最大的數(shù)。
注意： 排升序要建大堆；排降序要建小堆。 （在堆那里有提過(guò)）
代碼示例：
/**
* 堆排序
* 時(shí)間復(fù)雜度：O(N*log2^N)
* 空間復(fù)雜度：O(1)
* 穩(wěn)定性：不穩(wěn)定
*/
public static void heapSort(int[] array){
creatHeap(array);//先創(chuàng)建堆
int end=array.length-1;
//交換后調(diào)整（N*log2^N)
while(end>0){
swap(array,0,end);
shiftDown(array,0,end);
end--;
}
}
//建堆
public static void creatHeap(int[] array){
for(int parent=(array.length-1-1)/2;parent>=0;parent--){
shiftDown(array,parent,array.length);
}
}
//調(diào)整
public static void shiftDown(int[] array,int parent,int len){
int child=2*parent+1;//左孩子下標(biāo)
while(child<len){
//左右孩子比較
if(child+1<len && array[child]<array[child+1]){
child++;
}
if(array[child]>array[parent]){
swap(array,child,parent);
parent=child;
child=parent*2-1;
}else{
break;
}
}
}冒泡排序
在無(wú)序區(qū)間，通過(guò)相鄰數(shù)的比較，將最大的數(shù)冒泡到無(wú)序區(qū)間的最后，持續(xù)這個(gè)過(guò)程，直到數(shù)組整體有序。
代碼示例：
/**
* 冒泡排序
* 時(shí)間復(fù)雜度：O(N^2)
* 空間復(fù)雜度：O(1)
* 穩(wěn)定性：穩(wěn)定
* i為需要排的次數(shù)
* j為每次需要比較的開(kāi)始到結(jié)束位置
*/
public static void bubbleSort(int[] array){
for (int i = 0; i < array.length-1; i++) {
for (int j = 0; j < array.length-1-i; j++) {
if(array[j+1]<array[j]){
swap(array,j,j+1);
}
}
}
}
public static void swap(int[] array,int i,int j){
int tmp=array[i];
array[i]=array[j];
array[j]=tmp;
}快速排序
1、 從待排序區(qū)間選擇一個(gè)數(shù)，作為基準(zhǔn)值 (pivot) ;
2、 partition: 遍歷整個(gè)待排序區(qū)間，將比基準(zhǔn)值小的（可以包含相等的）放到基準(zhǔn)值的左邊，將比基準(zhǔn)值大的（可以包含相等的）放到基準(zhǔn)值的右邊;
3、 采用分治思想，對(duì)左右兩個(gè)小區(qū)間按照同樣的方式處理，直到小區(qū)間的長(zhǎng)度 == 1 ，代表已經(jīng)有序，或者小區(qū)間的長(zhǎng)度 == 0 ，代表沒(méi)有數(shù)據(jù)。 代碼示例：
/**
* 時(shí)間復(fù)雜度：
* 最好(每次可以均勻的分割待排序序列)：O(N*log2^n)log以2為底的N次方
* 最壞：數(shù)據(jù)有序或者逆序的情況 O(N^2)
* 空間復(fù)雜度：
* 最好：O(log2^n)
* 最壞：O(n) 單分支的一棵樹(shù)
* 穩(wěn)定性：不穩(wěn)定的排序
*/
//遞歸方式實(shí)現(xiàn)
public static void quickSort(int[] array){
quick(array,0,array.length-1);
}
public static void quick(int[] array,int left,int right){
if(left>=right){
return;
}
//找基準(zhǔn)值，然后基準(zhǔn)值左邊右邊分別按同樣的方式處理
int pivot=partition(array,left,right);
quick(array,left,pivot-1);
quick(array,pivot+1,right);
}
//找基準(zhǔn)點(diǎn)(兩邊開(kāi)始找)
public static int partition(int[] array,int start,int end){
int tmp=array[start];
while(start<end){
while(start<end && array[end]>=tmp){
end--;
}
array[start]=array[end];
while(start<end && array[start]<=tmp){
start++;
}
array[end]=array[start];
}
array[start]=tmp;//start==end時(shí)，找到了基準(zhǔn)點(diǎn)
return end;
}上面代碼還有待優(yōu)化，如果我們是一個(gè)有序數(shù)組，我們?cè)谡一鶞?zhǔn)值進(jìn)行相應(yīng)處理的時(shí)候可能會(huì)出現(xiàn)單分支情況，這時(shí)候我們可以讓start下標(biāo)的值為中間值，這樣可以避免出現(xiàn)單分支情況。
代碼示例：
public static void quickSort(int[] array){
quick(array,0,array.length-1);
}
public static void quick(int[] array,int left,int right){
if(left>=right){
return;
}
//優(yōu)化--找基準(zhǔn)前，先找到中間值，三數(shù)取中法(防止有序情況下出現(xiàn)單分支）
int minValIndex=findValINdex(array,left,right);
swap(array,minValIndex,left);
int pivot=partition(array,left,right);
quick(array,left,pivot-1);
quick(array,pivot+1,right);
}
//三數(shù)取中
private static int findValINdex(int[] array,int start,int end){
int mid=start+((end-start)>>>1);
//(start+end)/2
if(array[start]<array[end]){
if(array[mid]>array[end]){
return end;
} else if (array[mid]<array[start]) {
return start;
}else{
return mid;
}
}else{
if(array[mid]>array[start]) {
return start;
}else if(array[mid]<array[end]){
return end;
}else{
return mid;
}
}
}當(dāng)排序數(shù)據(jù)過(guò)多時(shí)還能繼續(xù)優(yōu)化，如果區(qū)間內(nèi)的數(shù)據(jù)，在排序的過(guò)程當(dāng)中，小于某個(gè)范圍了，可以使用直接插入排序。
代碼示例：
public static void quickSort(int[] array){
quick(array,0,array.length-1);
}
//遞歸，找到了基準(zhǔn)點(diǎn)，分別再對(duì)基準(zhǔn)點(diǎn)左邊和基準(zhǔn)點(diǎn)右邊找
public static void quick(int[] array,int left,int right){
if(left>=right){
return;
}
//優(yōu)化--如果區(qū)間內(nèi)的數(shù)據(jù)，在排序的過(guò)程當(dāng)中，小于某個(gè)范圍了，可以使用直接插入排序
if(right-left+1<150){
insertSort1(array,left,right);
return;
}
//優(yōu)化--找基準(zhǔn)前，先找到中間值，三數(shù)取中法(防止有序情況下出現(xiàn)單分支）
int minValIndex=findValINdex(array,left,right);
swap(array,minValIndex,left);
int pivot=partition(array,left,right);
quick(array,left,pivot-1);
quick(array,pivot+1,right);
}
private static void insertSort1(int[] array,int start,int end){
for (int i = 1; i <= end; i++) {
int tmp=array[i];
int j=i-1;
for(j=i-1;j>=start;j--){
if(array[j]>tmp){
array[j+1]=array[j];
}else{
//array[j+1]=tmp;
break;
}
}
array[j+1]=tmp;
}
}非遞歸實(shí)現(xiàn)：
public static void quickSort1(int[] array){
int left=0;
int right=array.length-1;
Stack<Integer> stack=new Stack<>();
int pivot=partition(array,left,right);
//如果左邊或者右邊只剩下一個(gè)數(shù)據(jù)了，那就已經(jīng)有序了，不需要在排序
if(left+1<pivot){
//左邊至少有兩個(gè)元素
stack.push(left);
stack.push(pivot-1);
}
if(right-1>pivot){
//右邊至少有兩個(gè)元素
stack.push(right);
stack.push(pivot+1);
}
while(!stack.isEmpty()){
left=stack.pop();
right=stack.pop();
pivot=partition(array,left,right);
if(left+1<pivot){
//左邊至少有兩個(gè)元素
stack.push(left);
stack.push(pivot-1);
}
if(right-1>pivot){
//右邊至少有兩個(gè)元素
stack.push(right);
stack.push(pivot+1);
}
}
}歸并排序
歸并排序 是建立在歸并操作上的一種有效的排序算法 , 將已有序的子序列合并，得到完全有序的序列。即先使每個(gè)子序列有序，再使子 序列段間有序。若將兩個(gè)有序表合并成一個(gè)有序表，稱(chēng)為二路歸并。
代碼示例：
/**
* 歸并排序--遞歸
* 時(shí)間復(fù)雜度：O(N*log2^N)
* 空間復(fù)雜度：O(N)
* 穩(wěn)定性：穩(wěn)定
* 學(xué)過(guò)的排序：穩(wěn)定的只有三個(gè)
* 冒泡 插入 歸并
*/
//遞歸方式實(shí)現(xiàn)
public static void mergeSort(int[] array){
mergeSortInternal(array,0,array.length-1);
}
public static void mergeSortInternal(int[] array,int left,int right){
if(left>=right){
return;
}
int mid=left+((right-left)>>>1);
//mid=(left+right)/2;
//左邊
mergeSortInternal(array,left,mid);
//右邊
mergeSortInternal(array,mid+1,right);
//合并
merge(array,left,mid,right);
}
public static void merge(int[] array,int start,int mid,int end) {
int s1 = start;
int e1 = mid;
int s2 = mid+1;
int e2 = end;
int i = 0;
int[] tmp = new int[array.length];
while (s1 <= e1 && s2 <= e2) {
if (array[s1] <=array[s2]) {
tmp[i] = array[s1];
//tmp[i++]=array1[s1++];
i++;
s1++;
} else {
tmp[i] = array[s2];
i++;
s2++;
}
}
while(s1<=e1){
tmp[i++]=array[s1++];
}
while(s2<=e2){
tmp[i++]=array[s2++];
}
for (int j = 0; j < i; j++) {
array[j+start]=tmp[j];
}
}非遞歸方式--分組歸并（先tmp個(gè)元素有序然后在合并）
//tmp:代表組內(nèi)元素個(gè)數(shù)
public static void mergeSort1(int[] array){
int tmp=1;
while(tmp<array.length-1){
//數(shù)組每次都要進(jìn)行遍歷,確定要?dú)w并的區(qū)間
for (int i = 0; i < array.length; i+=tmp*2) {
int left=i;
int mid=left+tmp-1;
//防止越界
if(mid>=array.length){
mid=array.length-1;
}
int right=mid+tmp;
//防止越界
if(right>=array.length){
right=array.length-1;
}
//下標(biāo)確定之后進(jìn)行合并
merge(array,left,mid,right);
}
tmp=tmp*2;
}
}計(jì)數(shù)排序
以上排序都是通過(guò)比較的排序，接下來(lái)介紹一種不需要比較的排序--計(jì)數(shù)排序。
代碼示例：
/**
* 計(jì)數(shù)排序：
* 時(shí)間復(fù)雜度：O(N)
* 空間復(fù)雜度：O(M) M:代表當(dāng)前數(shù)據(jù)的范圍
* 穩(wěn)定性：當(dāng)前代碼是不穩(wěn)定的，但是本質(zhì)是穩(wěn)定的
* 一般適用于有n個(gè)數(shù)，數(shù)據(jù)范圍是0-n之間的
*/
public static void countingSort(int[] array) {
int minVal=array[0];
int maxVal=array[0];
for(int i=0;i<array.length;i++){
if(array[i]<minVal){
minVal=array[i];
}
if(array[i]>maxVal){
maxVal=array[i];
}
}
int[] count=new int[maxVal-minVal+1];//下標(biāo)默認(rèn)從0開(kāi)始
for (int i=0;i<array.length;i++){
//統(tǒng)計(jì)array數(shù)組當(dāng)中，每個(gè)數(shù)據(jù)出現(xiàn)的次數(shù)
int index=array[i];
//為了空間的合理使用 這里需要index-minVal 防止623-600
count[index-minVal]++;
}
//說(shuō)明，在計(jì)數(shù)數(shù)組當(dāng)中，已經(jīng)把a(bǔ)rray數(shù)組當(dāng)中，每個(gè)數(shù)據(jù)出現(xiàn)的次數(shù)已經(jīng)統(tǒng)計(jì)好了
//接下來(lái)，只需要，遍歷計(jì)數(shù)數(shù)組，把數(shù)據(jù)寫(xiě)回array
int indexArray=0;
for(int i=0;i<count.length;i++){
while (count[i]>0){
array[indexArray]=i+minVal;
count[i]--;
indexArray++;
}
}
}到此這篇關(guān)于Java超詳細(xì)整理講解各種排序的文章就介紹到這了,更多相關(guān)Java排序內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
Java實(shí)現(xiàn)線(xiàn)程同步的四種方式總結(jié)
Java線(xiàn)程同步屬于Java多線(xiàn)程與并發(fā)編程的核心點(diǎn)，需要重點(diǎn)掌握，下面我就來(lái)詳解Java線(xiàn)程同步的4種主要的實(shí)現(xiàn)方式，需要的可以參考一下2022-09-09
劍指Offer之Java算法習(xí)題精講二叉樹(shù)專(zhuān)項(xiàng)解析
跟著思路走，之后從簡(jiǎn)單題入手，反復(fù)去看，做過(guò)之后可能會(huì)忘記，之后再做一次，記不住就反復(fù)做，反復(fù)尋求思路和規(guī)律，慢慢積累就會(huì)發(fā)現(xiàn)質(zhì)的變化2022-03-03
SpringBoot之logback-spring.xml不生效的解決方法
這篇文章主要介紹了SpringBoot之logback-spring.xml不生效的解決方法，小編覺(jué)得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2018-01-01
SpringBoot接口正確接收時(shí)間參數(shù)的幾種方式
這篇文章主要給大家介紹了關(guān)于SpringBoot接口正確接收時(shí)間參數(shù)的相關(guān)資料,文中通過(guò)代碼示例介紹的非常詳細(xì),對(duì)大家學(xué)習(xí)或者使用springboot具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2023-09-09
JAVA NIO按行讀寫(xiě)大文件出現(xiàn)中文亂碼問(wèn)題的解決
這篇文章主要為大家詳細(xì)介紹了JAVA在使用NIO進(jìn)行按行讀寫(xiě)大文件時(shí)出現(xiàn)中文亂碼問(wèn)題是如何解決的,文中的示例代碼簡(jiǎn)潔易懂,有需要的小伙伴可以參考一下2025-02-02
這篇文章主要為大家詳細(xì)介紹了java設(shè)計(jì)優(yōu)化中的單例模式,深入學(xué)習(xí)java單例模式，感興趣的朋友可以參考一下2016-03-03
這篇文章主要給大家介紹了關(guān)于java程序中protobuf的基本用法,protobuf 與json相比具有 壓縮比高 、解壓縮速度更快的優(yōu)點(diǎn),本文通過(guò)示例代碼介紹的非常詳細(xì),需要的朋友可以參考下2021-08-08
本文主要介紹了SpringBoot2.x集成Dozer的示例代碼，文中通過(guò)示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-08-08
java使用Process調(diào)用exe程序及Process.waitFor()死鎖問(wèn)題解決
在編寫(xiě)Java程序時(shí),有時(shí)候我們需要調(diào)用其他的諸如exe,shell這樣的程序或腳本,下面這篇文章主要給大家介紹了關(guān)于java使用Process調(diào)用exe程序及Process.waitFor()死鎖問(wèn)題解決的相關(guān)資料,需要的朋友可以參考下2022-12-12
Java中EasyExcel使用自定義Converter處理方法詳解
EasyExcel自定義Converter是指在使用EasyExcel進(jìn)行Excel讀寫(xiě)操作時(shí),可以自定義轉(zhuǎn)換器來(lái)處理一些不支持的數(shù)據(jù)類(lèi)型,這篇文章主要給大家介紹了關(guān)于Java中EasyExcel使用自定義Converter處理的相關(guān)資料,需要的朋友可以參考下2024-08-08