Java 數(shù)據(jù)結(jié)構(gòu)七大排序使用分析
一、插入排序
1、直接插入排序
當(dāng)插入第i(i>=1)個元素時，前面的array[0],array[1],…,array[i-1]已經(jīng)排好序，此時用array[i]與array[i-1],array[i-2],…進(jìn)行比較，找到插入位置即將array[i]插入，原來位置上的元素順序后移。
數(shù)據(jù)越接近有序，直接插入排序的時間消耗越少。
時間復(fù)雜度：O(N^2)
空間復(fù)雜度O(1)，是一種穩(wěn)定的算法
直接插入排序：
public static void insertSort(int[] array){
for (int i = 1; i < array.length; i++) {
int tmp=array[i];
int j=i-1;
for(;j>=0;--j){
if(array[j]>tmp){
array[j+1]=array[j];
}else{
break;
}
}
array[j+1]=tmp;
}
}2、希爾排序
希爾排序法的基本思想是：先選定一個整數(shù)gap，把待排序文件中所有記錄分成gap個組，所有距離為gap的數(shù)分在同一組內(nèi)，并對每一組內(nèi)的數(shù)進(jìn)行直接插入排序。然后取gap=gap/2，重復(fù)上述分組和排序的工作。當(dāng)gap=1時，所有數(shù)在一組內(nèi)進(jìn)行直接插入排序。
- 希爾排序是對直接插入排序的優(yōu)化。
- 當(dāng)gap > 1時都是預(yù)排序，目的是讓數(shù)組更接近于有序。當(dāng)gap == 1時，數(shù)組已經(jīng)接近有序的了，直接插入排序會很快。
- 希爾排序的時間復(fù)雜度不好計算，因為gap的取值方法很多，導(dǎo)致很難去計算。
希爾排序 ：
public static void shellSort(int[] array){
int size=array.length;
//這里定義gap的初始值為數(shù)組長度的一半
int gap=size/2;
while(gap>0){
//間隔為gap的直接插入排序
for (int i = gap; i < size; i++) {
int tmp=array[i];
int j=i-gap;
for(;j>=0;j-=gap){
if(array[j]>tmp){
array[j+gap]=array[j];
}else{
break;
}
}
array[j+gap]=tmp;
}
gap/=2;
}
}二、選擇排序
1、選擇排序
- 在元素集合array[i]--array[n-1]中選擇最小的數(shù)據(jù)元素
- 若它不是這組元素中的第一個，則將它與這組元素中的第一個元素交換
- 在剩余的集合中，重復(fù)上述步驟，直到集合剩余1個元素
時間復(fù)雜度：O(N^2)
空間復(fù)雜度為O(1)，不穩(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 chooseSort(int[] array){
for (int i = 0; i < array.length; i++) {
int minIndex=i;//記錄最小值的下標(biāo)
for (int j = i+1; j < array.length; j++) {
if (array[j]<array[minIndex]) {
minIndex=j;
}
}
swap(array,i,minIndex);
}
}2、堆排序
堆排序的兩種思路（以升序為例）：
- 創(chuàng)建小根堆，依次取出堆頂元素放入數(shù)組中，直到堆為空
- 創(chuàng)建大根堆，定義堆的尾元素位置key，每次交換堆頂元素和key位置的元素（key--），直到key到堆頂，此時將堆中元素層序遍歷即為升序（如下）
時間復(fù)雜度：O(N^2)
空間復(fù)雜度：O(N)，不穩(wěn)定
堆排序：
//向下調(diào)整
public static void shiftDown(int[] array,int parent,int len){
int child=parent*2+1;
while(child<len){
if(child+1<len){
if(array[child+1]>array[child]){
child++;
}
}
if(array[child]>array[parent]){
swap(array,child,parent);
parent=child;
child=parent*2+1;
}else{
break;
}
}
}
//創(chuàng)建大根堆
private static void createHeap(int[] array){
for (int parent = (array.length-1-1)/2; parent >=0; parent--) {
shiftDown(array,parent,array.length);
}
}
//堆排序
public static void heapSort(int[] array){
//創(chuàng)建大根堆
createHeap(array);
//排序
for (int i = array.length-1; i >0; i--) {
swap(array,0,i);
shiftDown(array,0,i);
}
}三、交換排序
1、冒泡排序
兩層循環(huán)，第一層循環(huán)表示要排序的趟數(shù)，第二層循環(huán)表示每趟要比較的次數(shù)；這里的冒泡排序做了優(yōu)化，在每一趟比較時，我們可以定義一個計數(shù)器來記錄數(shù)據(jù)交換的次數(shù)，如果沒有交換，則表示數(shù)據(jù)已經(jīng)有序，不需要再進(jìn)行排序了。
時間復(fù)雜度：O(N^2)
空間復(fù)雜度為O(1),是一個穩(wěn)定的排序
冒泡排序：
public static void bubbleSort(int[] array){
for(int i=0;i<array.length-1;++i){
int count=0;
for (int j = 0; j < array.length-1-i; j++) {
if(array[j]>array[j+1]){
swap(array,j,j+1);
count++;
}
}
if(count==0){
break;
}
}
}2、快速排序
任取待排序元素序列中的某元素作為基準(zhǔn)值，按照該排序碼將待排序集合分割成兩子序列，左子序列中所有元素均小于基準(zhǔn)值，右子序列中所有元素均大于基準(zhǔn)值，然后最左右子序列重復(fù)該過程，直到所有元素都排列在相應(yīng)位置上為止。
時間復(fù)雜度：最好O(n*logn):每次可以盡量將待排序的序列均勻分割
最壞O(N^2)：待排序序列本身是有序的
空間復(fù)雜度：最好O(logn)、 最壞O(N)。不穩(wěn)定的排序
（1）挖坑法
當(dāng)數(shù)據(jù)有序時，快速排序就相當(dāng)于二叉樹沒有左子樹或右子樹，此時空間復(fù)雜度會達(dá)到O(N)，如果大量數(shù)據(jù)進(jìn)行排序，可能會導(dǎo)致棧溢出。
public static void quickSort(int[] array,int left,int right){
if(left>=right){
return;
}
int l=left;
int r=right;
int tmp=array[l];
while(l<r){
while(array[r]>=tmp&&l<r){
//等號不能省略，如果省略，當(dāng)序列中存在相同的值時，程序會死循環(huán)
r--;
}
array[l]=array[r];
while(array[l]<=tmp&&l<r){
l++;
}
array[r]=array[l];
}
array[l]=tmp;
quickSort(array,0,l-1);
quickSort(array,l+1,right);
}（2）快速排序的優(yōu)化
三數(shù)取中法選key
關(guān)于key值的選取，如果待排序序列是有序的，那么我們選取第一個或最后一個作為key可能導(dǎo)致分割的左邊或右邊為空，這時快速排序的空間復(fù)雜度會比較大，容易造成棧溢出。那么我們可以采用三數(shù)取中法來取消這種情況。找到序列的第一個，最后一個，以及中間的一個元素，以他們的中間值作為key值。
//key值的優(yōu)化，只在快速排序中使用，則可以為private
private int threeMid(int[] array,int left,int right){
int mid=(left+right)/2;
if(array[left]>array[right]){
if(array[mid]>array[left]){
return left;
}
return array[mid]<array[right]?right:mid;
}else{
if(array[mid]<array[left]){
return left;
}
return array[mid]>array[right]?right:mid;
}
}遞歸到小的子區(qū)間時，可以考慮用插入排序
隨著我們遞歸的進(jìn)行，區(qū)間會變的越來越小，我們可以在區(qū)間小到一個值的時候，對其進(jìn)行插入排序，這樣代碼的效率會提高很多。
（3）快速排序的非遞歸實現(xiàn)
//找到一次劃分的下標(biāo)
public static int patition(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;
}
//快速排序的非遞歸
public static void quickSort2(int[] array){
Stack<Integer> stack=new Stack<>();
int left=0;
int right=array.length-1;
stack.push(left);
stack.push(right);
while(!stack.isEmpty()){
int r=stack.pop();
int l=stack.pop();
int p=patition(array,l,r);
if(p-1>l){
stack.push(l);
stack.push(p-1);
}
if(p+1<r){
stack.push(p+1);
stack.push(r);
}
}
}四、歸并排序
歸并排序（MERGE-SORT）：該算法是采用分治法（Divide and Conquer）的一個非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為二路歸并。
時間復(fù)雜度：O(n*logN)（無論有序還是無序）
空間復(fù)雜度：O（N）。是穩(wěn)定的排序。
//歸并排序：遞歸
public static void mergeSort(int[] array,int left,int right){
if(left>=right){
return;
}
int mid=(left+right)/2;
//遞歸分割
mergeSort(array,left,mid);
mergeSort(array,mid+1,right);
//合并
merge(array,left,right，mid);
}
//非遞歸
public static void mergeSort1(int[] array){
int gap=1;
while(gap<array.length){
for (int i = 0; i < array.length; i+=2*gap) {
int left=i;
int mid=left+gap-1;
if(mid>=array.length){
mid=array.length-1;
}
int right=left+2*gap-1;
if(right>=array.length){
right=array.length-1;
}
merge(array,left,right,mid);
}
gap=gap*2;
}
}
//合并：合并兩個有序數(shù)組
public static void merge(int[] array,int left,int right，int mid){
int[] tmp=new int[right-left+1];
int k=0;
int s1=left;
int e1=mid;
int s2=mid+1;
int e2=right;
while(s1<=e1&&s2<=e2){
if(array[s1]<=array[s2]){
tmp[k++]=array[s1++];
}else{
tmp[k++]=array[s2++];
}
}
while(s1<=e1){
tmp[k++]=array[s1++];
}
while(s2<=e2){
tmp[k++]=array[s2++];
}
for (int i = left; i <= right; i++) {
array[i]=tmp[i-left];
}
}五、排序算法的分析
| 排序方法 | 最好時間復(fù)雜度 | 最壞時間復(fù)雜度 | 空間復(fù)雜度 | 穩(wěn)定性 |
| 直接插入排序 | O(n) | O(n^2) | O(1) | 穩(wěn)定 |
| 希爾排序 | O(n) | O(n^2) | O(1） | 不穩(wěn)定 |
| 直接排序 | O(n^2) | O(n^2) | O(1) | 不穩(wěn)定 |
| 堆排序 | O(nlog(2)n) | O(nlog(2)n) | O(1) | 不穩(wěn)定 |
| 冒泡排序 | O(n) | O(n^2) | O(1) | 穩(wěn)定 |
| 快速排序 | O(nlog(2)n) | O(n^2) | O(nlog(2)n) | 不穩(wěn)定 |
| 歸并排序 | O(nlog(2)n) | O(nlog(2)n) | O(n) | 穩(wěn)定 |
到此這篇關(guān)于Java 數(shù)據(jù)結(jié)構(gòu)七大排序使用分析的文章就介紹到這了,更多相關(guān)Java 排序內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
- Java數(shù)據(jù)結(jié)構(gòu)常見幾大排序梳理
- Java 數(shù)據(jù)結(jié)構(gòu)與算法系列精講之排序算法
- java 數(shù)據(jù)結(jié)構(gòu)與算法 (快速排序法)
- Java深入了解數(shù)據(jù)結(jié)構(gòu)中常見的排序算法
- Java數(shù)據(jù)結(jié)構(gòu)之二叉排序樹的實現(xiàn)
- 帶你了解Java數(shù)據(jù)結(jié)構(gòu)和算法之高級排序
- Java數(shù)據(jù)結(jié)構(gòu)和算法之冒泡,選擇和插入排序算法
- ?Java數(shù)據(jù)結(jié)構(gòu)的十大排序
相關(guān)文章
在本篇文章里小編給大家整理分享的是關(guān)于java向上轉(zhuǎn)型發(fā)生的時機知識點內(nèi)容，有興趣的讀者們可以參考下。2021-05-05
這篇文章主要介紹了Spring如何在一個事務(wù)中開啟另一個事務(wù),文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2020-01-01
這篇文章主要給大家介紹了關(guān)于Java中方法使用的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-08-08
本文簡單介紹了緩存的種類，緩存常見的問題，對大家的學(xué)習(xí)和工作有一定的參考價值，需要的小伙伴可以參考一下2021-08-08
JAVA Iterator接口與增強for循環(huán)的實現(xiàn)
這篇文章主要介紹了JAVA Iterator接口與增強for循環(huán)的實現(xiàn)，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-11-11
全面匯總SpringBoot和SpringClould常用注解
Java注解是附加在代碼中的一些元信息，用于一些工具在編譯、運行時進(jìn)行解析和使用，起到說明、配置的功能,這篇文章就帶你來了解一下2021-08-08
這篇文章主要介紹了IDEA之web項目導(dǎo)入jar包方式,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2024-05-05
快速解決springboot在yml配置了啟動端口但啟動還是8080問題
這篇文章主要介紹了快速解決springboot在yml配置了啟動端口但啟動還是8080問題,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2025-03-03
如何使用Spring Security手動驗證用戶的方法示例
這篇文章主要介紹了如何使用Spring Security手動驗證用戶的方法示例，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2019-05-05
下面小編就為大家?guī)硪黄獪\談java指令重排序的問題。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-09-09