Java中七種排序算法總結(jié)分析
前言:對(duì)文章出現(xiàn)的一些名詞進(jìn)行解釋
排序: 使一串記錄,按照其中的某個(gè)或某些關(guān)鍵字的大小,遞增或者遞減排列起來的操作。
穩(wěn)定性: 假定在排序的記錄序列中,存在多個(gè)具有相同的關(guān)鍵字的記錄,若經(jīng)過排序,這些記錄的相對(duì)次序保持不變,即在原序列中,a=b,且a在b之前,而在排序后的序列中,a仍然在b之前則這種排序算法是穩(wěn)定的,否則就是不穩(wěn)定的。
內(nèi)部排序: 數(shù)據(jù)元素全部放在內(nèi)存中的排序。
外部排序: 數(shù)據(jù)元素太多不能同時(shí)放在內(nèi)存中,根據(jù)排序過程的要求不能在內(nèi)外存之間移動(dòng)數(shù)據(jù)的排序。
文中所有排序都是升序。
一、插入排序
直接插入排序是一種簡(jiǎn)單的插入排序法。
1.基本思想
把待排序的記錄按照其關(guān)鍵碼值的大小逐個(gè)插入到一個(gè)已經(jīng)排好序的有序序列中,直到所有記錄全部插完為止,得到一個(gè)新的有序序列。這種思想在我們玩撲克牌的時(shí)候用到過,在我們碼牌時(shí),抽出一個(gè)牌,會(huì)從后往前依次比較牌面值,然后插入到一個(gè)比前面大且比后面小的位置中。

2.直接插入排序
步驟:
1.第一次排序先將第一個(gè)元素看成是已排序區(qū)間,將其內(nèi)容保存起來
2.待排序區(qū)間是其后面的所有元素,從其后面第一個(gè)開始,依次和已排序區(qū)間里的元素比較(這里的比較是從后向前比較,也就是從其前一個(gè)元素比較到0號(hào)位置的元素)
3.如果小于已排序區(qū)間中的元素,則將該位置向后挪一位
4.直到找到第一個(gè)比其小的元素,此時(shí)其后面的所有元素都是比它大的,且都向后挪了一位,這時(shí)其后面的位置是空的,將該元素放進(jìn)來即可。
5.之后取第二個(gè),第三個(gè)…第i個(gè)依次這樣比較即可,即循環(huán)起來。其中每次[0,i)是已排序區(qū)間,[i,size)是待排序區(qū)間。
動(dòng)圖演示:

代碼實(shí)現(xiàn):
public static void insertSort(int[] array){
int j=0;
//i位置與之前所有下標(biāo)從后往前進(jìn)行比較,該位置大于i則繼續(xù)往前,小于則插入到后邊
//[0,bound)已排序區(qū)間
//[bound,size)待排序區(qū)間
for(int bound=1;bound<array.length;bound++) {
int temp = array[bound];
//先取已排序區(qū)間的最后一個(gè),依次往前進(jìn)行比較
for (j = bound - 1; j >= 0; j--) {
//如果temp小于,則將元素往后移一位
if (array[j]>temp) {
array[j + 1] = array[j];
} else {
break;
}
}
//找到合適位置,填充
array[j + 1] = temp;
}
}
相關(guān)特性總結(jié):
時(shí)間復(fù)雜度:O(N2)
空間復(fù)雜度:O(1)
穩(wěn)定性:穩(wěn)定(是從后往前依次比較的)
應(yīng)用場(chǎng)景:元素越接近有序越好(因?yàn)樵浇咏行虮容^次數(shù)就會(huì)越少,算法的時(shí)間效率就會(huì)越高)
3.希爾排序(縮小增量排序)
基本思想:
把待排序區(qū)間中所有記錄分成幾個(gè)組,設(shè)置一個(gè)gap值,所有距離為gap的記錄分在同一組內(nèi),并分別對(duì)每個(gè)組內(nèi)的記錄進(jìn)行排序,然后讓gap以一定的規(guī)律減小,然后重復(fù)上述分組和排序的工作,當(dāng)gap達(dá)到1時(shí),所有記錄已經(jīng)排好序。
步驟:
1.設(shè)置gap值(每個(gè)組內(nèi)元素之間間隔)
2.在每個(gè)組內(nèi)進(jìn)行直接插入排序
3.縮小gap值(這里我按照2倍縮?。?br />
4.gap為1時(shí)排序完畢
圖象解釋:

代碼實(shí)現(xiàn):
public static void shellSort(int[] array){
int gap= array.length/2;
while(gap>0){
int j=0;
//i位置與之前所有下標(biāo)從后往前進(jìn)行比較,該位置大于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;
}
}
相關(guān)特性總結(jié):
希爾排序是對(duì)直接插入排序的優(yōu)化
當(dāng)gap>1時(shí)都是預(yù)排序,目的是讓數(shù)組更接近有序,當(dāng)gap==1時(shí),數(shù)組已經(jīng)接近有序,這樣就很會(huì)快,整體而言,可以達(dá)到優(yōu)化的效果
時(shí)間復(fù)雜度不確定,因?yàn)間ap取值方法有很多
空間復(fù)雜度:O(1)
穩(wěn)定性:不穩(wěn)定(元素之間是跳著交換的)
二、選擇排序
1.基本思想
每一次從待排序的數(shù)據(jù)元素中選出最?。ɑ蜃畲螅┑囊粋€(gè)元素,存放在序列的起始位置,直到全部待排序的數(shù)據(jù)元素排完。
2.直接選擇排序
步驟:
1.先記錄下標(biāo)為0元素為最小值
2.從下標(biāo)為1開始往后遍歷,遇到比最小值還小的就標(biāo)記起來,遍歷完成即找到最小值
3.將找到的最小值與下標(biāo)為0的元素進(jìn)行交換
4.此時(shí)[0,1)為已排序區(qū)間,即不再動(dòng),[1,size)是待排序區(qū)間
5.從下標(biāo)為1繼續(xù)上面的操作,即循環(huán)起來
6.循環(huán)到最后只剩一個(gè)元素結(jié)束,排序完成
動(dòng)圖演示:

代碼實(shí)現(xiàn):
public static void selectSort(int[] nums) {
//每次都和第一個(gè)元素相比,如果小于則和一個(gè)元素則交換
for(int bound=0;bound<nums.length-1;bound++){
//先記錄最小值為第一個(gè)元素
int min=bound;
//從其后一個(gè)開始遍歷,找出后面所有元素中的最小值
for(int i=bound+1;i<nums.length;i++){
if(nums[min]>nums[i]){
min=i;
}
}
//將最小值與待排序區(qū)間第一個(gè)進(jìn)行交換
swap(nums,bound,min);
}
}
相關(guān)特性總結(jié):
時(shí)間復(fù)雜度:O(N2)
空間復(fù)雜度:O(1)
穩(wěn)定性:不穩(wěn)定
效率不是很好,實(shí)際中很少使用
3.堆排序
堆排序是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法,它是選擇排序的一種。它是通過堆來進(jìn)行選擇數(shù)據(jù)。
注意:排升序要建大堆,排降序要建小堆
步驟:
1.創(chuàng)建一個(gè)大堆(升序)
從倒數(shù)第一個(gè)非葉子結(jié)點(diǎn)開始向下調(diào)整,直到根結(jié)點(diǎn),創(chuàng)建一個(gè)大堆
2.將根結(jié)點(diǎn)與最后一個(gè)結(jié)點(diǎn)進(jìn)行交換,此時(shí)最后一個(gè)元素一定是所有元素中最大的
3.將size–
4.將堆繼續(xù)調(diào)整好形成一個(gè)大堆,繼續(xù)上面的操作,即循環(huán)起來
5.最終排序完成
圖像解釋:

代碼實(shí)現(xiàn):
//寫一個(gè)交換函數(shù)
private static void swap(int[] array,int parent,int child){
int temp=array[child];
array[child]=array[parent];
array[parent]=temp;
}
//排升序建大堆
//向下調(diào)整,上篇博客提到了
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)建一個(gè)堆
int size=array.length;
for(int root=(size-2)/2;root>=0;root--){
shiftDown(array,root,size);
}
while(size>1){
//將第一個(gè)和最后一個(gè)元素進(jìn)行交換
swap(array,0,size-1);
//交換完成向下調(diào)整
size--;
shiftDown(array,0,size);
}
}
相關(guān)特性總結(jié):
時(shí)間復(fù)雜度:O(NlogN)
空間復(fù)雜度:O(1)
穩(wěn)定性:不穩(wěn)定
使用堆來選數(shù),效率高了很多
三、交換排序
1.基本思想
交換,就是根據(jù)序列中兩個(gè)記錄鍵值的比較結(jié)果來兌換這兩個(gè)記錄在序列中的位置,交換序列的特點(diǎn)是:將鍵值較大的記錄向序列的尾部移動(dòng),鍵值較小的記錄向序列的頭部移動(dòng)
2.冒泡排序
步驟:
1.從0號(hào)位置開始,將元素和他后面的元素比較,如果大于則交換
2.當(dāng)遍歷完成,最大的元素肯定在數(shù)組的最后
3.之后再比較時(shí),最后一個(gè)元素就是已排序區(qū)間,不再參與比較
4.重復(fù)上述步驟,即循環(huán)起來
動(dòng)圖演示:

代碼實(shí)現(xiàn):
public static void bubbleSort(int[] nums) {
//外層循環(huán)控制循環(huán)次數(shù)
for(int num=1;num<nums.length;num++){
//內(nèi)層循環(huán)控制交換哪兩個(gè)元素
for(int i=0;i<nums.length-num;i++){
if(nums[i+1]<nums[i]){
swap(nums,i+1,i);
}
}
}
}
相關(guān)特性總結(jié):
時(shí)間復(fù)雜度:O(N2)
空間復(fù)雜度:O(1)
穩(wěn)定性:穩(wěn)定
冒泡排序在最開始就已經(jīng)學(xué)到,很容易理解
3.快速排序(遞歸與非遞歸)
快速排序是Hoare于1962年提出的一種二叉樹結(jié)構(gòu)的交換排序方法,其基本思想為:任取待排序元素序列中的某元素作為基準(zhǔn)值,按照該基準(zhǔn)值將待排序集合分割成兩子序列,左子序列中所有元素均小于基準(zhǔn)值,右子序列中所有元素均大于基準(zhǔn)值,然后左右子序列重復(fù)該過程,直到所有元素都排列在相應(yīng)的位置上為止。
主框架實(shí)現(xiàn):
public static void quickSort(int[] array,int left,int right){
if((right-left)<=1){
return;
}
//按照基準(zhǔn)值對(duì)array數(shù)組的[left,right)區(qū)間中的元素進(jìn)行劃分
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);
}
從上述程序可以看出,程序結(jié)構(gòu)與二叉樹前序遍歷規(guī)則非常像。
接下來按照基準(zhǔn)值劃分就是快排的核心,常見方法有三種:
1.Hoare版
步驟:
1.這里我們?nèi)∽钣覀?cè)為基準(zhǔn)值
2.設(shè)置begin和end用來標(biāo)記,讓begin從左往右走,end從右往左走
3.當(dāng)begin小于end時(shí),因?yàn)槲覀內(nèi)〉没鶞?zhǔn)值為最右側(cè),所以應(yīng)先讓begin從左往右走,找到比基準(zhǔn)值大的元素就停下來
4.這時(shí)讓end從右往左走,找到比基準(zhǔn)值小的元素就停下來,兩者交換位置
5.循環(huán)起來
6.當(dāng)循環(huán)結(jié)束時(shí),兩個(gè)最終走到了同一個(gè)位置,將其和基準(zhǔn)值進(jìn)行交換
動(dòng)圖演示:

代碼實(shí)現(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--;
}
//當(dāng)兩個(gè)在同一個(gè)位置時(shí),不需要交換,減少交換次數(shù)
if(begin!=end){
swap(array,begin,end);
}
}
if(begin!=right-1){
swap(array,begin,right-1);
}
return begin;
}
2.挖坑法
步驟:
1.先將基準(zhǔn)值(這里是最右側(cè)元素)放在臨時(shí)變量temp中,這里就形成第一個(gè)坑位
2.設(shè)置begin和end用來標(biāo)記,讓begin從左往右走,end從右往左走
3.當(dāng)begin小于end時(shí),讓begin從左往右走,找到比temp大的值,去填end的坑,同時(shí)begin這里形成一個(gè)坑位
4.然后讓end從右往左走,找到比temp小的值,去填begin的坑,同時(shí)end這里形成了一個(gè)新的坑位
5.就這樣一直循環(huán),互相填坑,直到不滿足循環(huán)條件
6.這時(shí)begin和end在同一個(gè)坑位,且是最后一個(gè)坑位,使用基準(zhǔn)值填充
圖象解釋:

代碼實(shí)現(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從前往后找比基準(zhǔn)值大的元素
while(array[begin]<=temp&&begin<end){
begin++;
}
if(begin!=end){
//begin位置找到了一個(gè)比temp大的元素,填end的坑
array[end]=array[begin];
//begin位置形成了一個(gè)新的坑位
}
//讓end從后往前找比基準(zhǔn)值小的元素
while(array[end]>=temp&&begin<end){
end--;
}
if(begin!=end){
//end位置找到了一個(gè)比temp小的元素,填begin的坑
array[begin]=array[end];
//end位置形成了一個(gè)新的坑位
}
}
//begin和end位置是最后的一個(gè)坑位
//這個(gè)坑位使用基準(zhǔn)值填充
array[begin]=temp;
return begin;
}
3.前后標(biāo)記法(難理解)
小編其實(shí)也是根據(jù)大佬的代碼分析出來的,要問為什么這么做咱確實(shí)也是不太理解,另外如理解錯(cuò)誤歡迎指正
這里真誠發(fā)問,大佬們的腦子是不是和我的腦子不太一樣?
步驟:
1.采用cur和prev來標(biāo)記,兩者都是從左往右走,不一樣的是,最開始cur在0號(hào)位置,prev在cur前一個(gè)位置上
2.當(dāng)遇到比temp大的元素時(shí),prev不動(dòng),cur向前走一步,當(dāng)兩者一前一后的狀態(tài)時(shí),cur也會(huì)往前走一步,而prev不動(dòng)
3.這樣兩者逐漸拉開差距,此時(shí)遇到比基準(zhǔn)值小的元素,cur中的元素就會(huì)與prev中的元素交換
4.走到最后prev的下一個(gè)元素與基準(zhǔn)值位置交換
圖象解釋:

代碼實(shí)現(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從前往后找比基準(zhǔn)值小的元素
while(cur<right){
if(array[cur]<temp&&++prev!=cur){
swap(array,cur,prev);
}
cur++;
}
//將基準(zhǔn)值的位置放置好
if(++prev!=right-1){
swap(array,prev,right-1);
}
return prev;
}
但是會(huì)發(fā)現(xiàn):
當(dāng)我們選取的基準(zhǔn)值越靠近整個(gè)數(shù)組的中間時(shí),效率越好,這時(shí)可以看作是將數(shù)組逐漸分成了一個(gè)滿二叉樹,因此效率為O(NlogN)
最差時(shí)是取到其最大或者最小的元素,還是要?jiǎng)澐謓次,效率為O(N2)
一般時(shí)間復(fù)雜度都是看起最差情況,那為什么快速排序的時(shí)間復(fù)雜度是O(NlogN)呢?
其實(shí)是可以對(duì)取基準(zhǔn)值進(jìn)行優(yōu)化的,詳情請(qǐng)看下面:
4.快速排序優(yōu)化
1.三數(shù)取中法選temp
之前我們只取一個(gè)基準(zhǔn)值
優(yōu)化后,我們?cè)谧筮吶∫粋€(gè),中間取一個(gè),右邊取一個(gè)
比較三個(gè)數(shù)的大小,誰在中間就取誰為基準(zhǔn)值
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;
}
}
在更改上面的劃分方法中,只需要看看上面取出的基準(zhǔn)值在不在最右側(cè),如果不在就與最右側(cè)的值交換,這樣代碼改動(dòng)就比較小。
int index=getIndexOfMid(array,left,right);
if(index!=right-1){
swap(array,index,right-1);
}
2.遞歸到小的子區(qū)間時(shí),可以考慮使用插入排序
在Idea的內(nèi)層方法中,用的是小于47使用直接插入排序
5.快速排序非遞歸
如果直接轉(zhuǎn)為循環(huán)不好轉(zhuǎn),之前提到可以使用棧來實(shí)現(xiàn),利用棧后進(jì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);
//先壓入基準(zhǔn)值的右半側(cè)
s.push(right);
s.push(div+1);
//再壓入基準(zhǔn)值的左半側(cè)
s.push(div);
s.push(left);
}
}
}
6.相關(guān)特性總結(jié)
時(shí)間復(fù)雜度:O(NlogN)
空間復(fù)雜度:O(logN)(遞歸單次沒有借助輔助空間,高度即是深度)
穩(wěn)定性:不穩(wěn)定
快速排序整體綜合性能和使用場(chǎng)景都是比較好的,所以才叫快速排序
四、歸并排序(遞歸與非遞歸)
歸并排序是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法的一個(gè)非常典型的應(yīng)用。將已有的子序列合并,得到完全有序的序列,即先使每個(gè)子序列有序,再使子序列段間有序。若將兩個(gè)有序表合并成一個(gè)有序表,稱為二路歸并。
動(dòng)圖演示:

歸并排序核心步驟:將兩個(gè)有序數(shù)組合并成一個(gè)有序數(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同時(shí)下標(biāo)后移一位
if(array[begin1]>array[begin2]){
temp[index++]=array[begin2++];
}else {
temp[index++]=array[begin1++];
}
}
//看兩個(gè)數(shù)組哪個(gè)還沒有遍歷完成,直接順次放入temp數(shù)組的后面
while(begin1<end1){
temp[index++] = array[begin1++];
}
while(begin2<end2){
temp[index++]=array[begin2++];
}
}
主程序(遞歸):
步驟:
1.先對(duì)待排序區(qū)間進(jìn)行均分為兩個(gè)
2.使用遞歸,直到均分為每個(gè)區(qū)間只剩下一個(gè)元素時(shí),每?jī)蓚€(gè)使用二路歸并
3.將兩個(gè)有序數(shù)組合并為一個(gè)有序數(shù)組,將結(jié)果保存在temp中
4.最終temp保存的就是排序完成的數(shù)組,再拷貝回原數(shù)組中
private static void mergeSort(int[] array,int left,int right,int[] temp){
if((right-left>1)){
//先對(duì)[left,right)區(qū)間中的元素進(jìn)行均分
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對(duì)數(shù)組進(jìn)行分割,每次分割完成對(duì)gap*2,一開始為2個(gè)采用二路歸并,之后4個(gè),8個(gè),直到大于等于size結(jié)束。
非遞歸比遞歸思路更加簡(jiǎn)單。
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){
//劃分好要?dú)w并的區(qū)域,第一次每個(gè)區(qū)間只有一個(gè)元素
//[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;
}
}
相關(guān)特性總結(jié):
時(shí)間復(fù)雜度:O(NlogN)
空間復(fù)雜度:O(N)
穩(wěn)定性:穩(wěn)定
缺點(diǎn)在于需要O(N)的空間復(fù)雜度,歸并排序解決更多的是磁盤中的外排序問題
到此這篇關(guān)于Java中七種排序算法總結(jié)分析的文章就介紹到這了,更多相關(guān)Java 排序算法內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
SpringBoot集成shiro,MyRealm中無法@Autowired注入Service的問題
今天小編就為大家分享一篇關(guān)于SpringBoot集成shiro,MyRealm中無法@Autowired注入Service的問題,小編覺得內(nèi)容挺不錯(cuò)的,現(xiàn)在分享給大家,具有很好的參考價(jià)值,需要的朋友一起跟隨小編來看看吧2019-03-03
springboot Interceptor攔截器excludePathPatterns忽略失效
這篇文章主要介紹了springboot Interceptor攔截器excludePathPatterns忽略失效的問題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2021-07-07
Java對(duì)數(shù)組實(shí)現(xiàn)選擇排序算法的實(shí)例詳解
這篇文章主要介紹了Java對(duì)數(shù)組實(shí)現(xiàn)選擇排序算法的實(shí)例,選擇排序的比較次數(shù)為 O(N^2)而交換數(shù)為O(N),需要的朋友可以參考下2016-04-04
Java ServletContext對(duì)象用法解析
這篇文章主要介紹了Java ServletContext對(duì)象用法解析,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-05-05
Spring實(shí)戰(zhàn)之使用c:命名空間簡(jiǎn)化配置操作示例
這篇文章主要介紹了Spring實(shí)戰(zhàn)之使用c:命名空間簡(jiǎn)化配置操作,結(jié)合實(shí)例形式詳細(xì)分析了Spring使用c:命名空間簡(jiǎn)化配置的相關(guān)接口與配置操作技巧,需要的朋友可以參考下2019-12-12

