一、插入排序
1、直接插入排序
當插入第i(i>=1)個元素時，前面的array[0],array[1],…,array[i-1]已經排好序，此時用array[i]與array[i-1],array[i-2],…進行比較，找到插入位置即將array[i]插入，原來位置上的元素順序後移。
資料越接近有序，直接插入排序的時間消耗越少。
時間複雜度：O(N^2)
空間複雜度O(1)，是一種穩定的演算法
#直接插入排序：
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、希爾排序
希爾排序法的基本想法是：先選定一個整數gap，把待排序檔案中所有記錄分成gap組，所有距離為gap的數分在同一組內，並對每一組內的數進行直接插入排序。然後取gap=gap/2，重複上述分組和排序的工作。當gap=1時，所有數字在一組內進行直接插入排序。
希爾排序是直接插入排序的最佳化。
目的是讓陣列更接近有序，因此當gap > 1時進行預先排序。插入排序在gap為1時可以快速地對接近有序的陣列進行排序。
希爾排序的時間複雜度不好計算，因為gap的取值方法很多，導致很難去計算。
希爾排序：
public static void shellSort(int[] array){
int size=array.length;
//这里定义gap的初始值为数组长度的一半
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]中選擇最小的資料元素
- 若它不是這組元素中的第一個，則將它與這組元素中的第一個元素交換
- 在剩餘的集合中，重複上述步驟，直到集合剩餘1個元素
#
//交换
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;//记录最小值的下标
for (int j = i+1; j < array.length; j++) {
if (array[j]<array[minIndex]) {
minIndex=j;
}
}
swap(array,i,minIndex);
}
}2、堆排序堆排序的兩個想法（以升序為例）：
- 建立小根堆，依次取出堆頂元素放入陣列中，直到堆為空
- 建立大根堆，定義堆的尾元素位置key，每次交換堆頂元素和key位置的元素（key --），直到key到堆頂，此時將堆中元素層序遍歷即為升序（如下）
空間複雜度：O(N)，不穩定堆排序：
//向下调整
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;
}
}
}
//创建大根堆
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){
//创建大根堆
createHeap(array);
//排序
for (int i = array.length-1; i >0; i--) {
swap(array,0,i);
shiftDown(array,0,i);
}
}三、交換排序1 、冒泡排序兩層循環，第一層循環表示要排序的趟數，第二層循環表示每趟要比較的次數；這裡的冒泡排序做了優化，在每一趟比較時，我們可以定義一個計數器來記錄資料交換的次數，如果沒有交換，則表示資料已經有序，不需要再進行排序了。 時間複雜度：O(N^2)空間複雜度為O(1),是一個穩定的排序#冒泡排序：
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、快速排序任取待排序元素序列中的某元素作為基準值，並依照該排序碼將待排序集合分割成兩個子序列，左子序列中所有元素均小於基準值，右子序列中所有元素均大於基準值，然後最左右子序列重複此過程，直到所有元素都排列在對應位置上為止。 時間複雜度：最好O(n*logn):每次可以盡量將待排序的序列均勻分割 最壞有順序的空間複雜度：最好O(logn)、 最壞O(N)。不穩定的排序（1）挖坑法當資料有序時，快速排序就相當於二元樹沒有左子樹或右子樹，此時空間複雜度會達到O(N)，如果大量資料進行排序，可能會導致棧溢位。 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){
//等号不能省略，如果省略，当序列中存在相同的值时，程序会死循环
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）快速排序的最佳化三數取中法選key關於key值的選取，如果待排序序列是有順序的，那麼我們選取第一個或最後一個作為key可能導致分割的左邊或右邊為空，這時快速排序的空間複雜度會比較大，容易造成棧溢位。那我們可以採用三數取中法來取消這種情況。以序列中第一個、最後一個、中間一個元素的中間值作為key值。 //key值的优化，只在快速排序中使用，则可以为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;
}
}遞歸到小的子區間時，可以考慮用插入排序
随着我们递归的进行，区间会变的越来越小，我们可以在区间小到一个值的时候，对其进行插入排序，这样代码的效率会提高很多。
（3）快速排序的非递归实现
//找到一次划分的下标
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）的一个非常典型的应用。实现序列的完全有序，需要将已经有序的子序列合并，即先让每个子序列有序，然后再将相邻的子序列段有序。若将两个有序表合并成一个有序表，称为二路归并。
时间复杂度：O(n*logN)（无论有序还是无序）
空间复杂度：O（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;
}
}
//合并：合并两个有序数组
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];
}
}五、排序算法的分析
| 排序方法 | 最好时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 稳定性 |
| 直接插入排序 | O(n) | O(n^2) | O(1) | 稳定 |
| 希尔排序 | O(n) | O(n^2) | O(1） | 不稳定 |
| 直接排序 | O(n^2) | O(n^2) | O(1) | 不稳定 |
| 堆排序 | O(nlog(2)n) | O(nlog(2)n) | O(1) | 不稳定 |
| 冒泡排序 | O(n) | O(n^2) | O(1) | 稳定 |
| 快速排序 | O(nlog(2)n) | O(n^2) | O(nlog(2)n) | 不稳定 |
| 归并排序 | O(nlog(2)n) | O(nlog(2)n) | O(n) | 稳定 |
以上是Java資料結構七大排序怎麼使用的詳細內容。更多資訊請關注PHP中文網其他相關文章！
如何將Maven或Gradle用於高級Java項目管理，構建自動化和依賴性解決方案？Mar 17, 2025 pm 05:46 PM本文討論了使用Maven和Gradle進行Java項目管理，構建自動化和依賴性解決方案，以比較其方法和優化策略。
如何使用適當的版本控制和依賴項管理創建和使用自定義Java庫（JAR文件）？Mar 17, 2025 pm 05:45 PM本文使用Maven和Gradle之類的工具討論了具有適當的版本控制和依賴關係管理的自定義Java庫（JAR文件）的創建和使用。
如何使用咖啡因或Guava Cache等庫在Java應用程序中實現多層緩存？Mar 17, 2025 pm 05:44 PM本文討論了使用咖啡因和Guava緩存在Java中實施多層緩存以提高應用程序性能。它涵蓋設置，集成和績效優勢，以及配置和驅逐政策管理最佳PRA
如何將JPA（Java持久性API）用於具有高級功能（例如緩存和懶惰加載）的對象相關映射？Mar 17, 2025 pm 05:43 PM本文討論了使用JPA進行對象相關映射，並具有高級功能，例如緩存和懶惰加載。它涵蓋了設置，實體映射和優化性能的最佳實踐，同時突出潛在的陷阱。[159個字符]
Java的類負載機制如何起作用，包括不同的類載荷及其委託模型？Mar 17, 2025 pm 05:35 PMJava的類上載涉及使用帶有引導，擴展程序和應用程序類負載器的分層系統加載，鏈接和初始化類。父代授權模型確保首先加載核心類別，從而影響自定義類LOA
如何將Java的RMI（遠程方法調用）用於分佈式計算？Mar 11, 2025 pm 05:53 PM本文解釋了用於構建分佈式應用程序的Java的遠程方法調用（RMI）。 它詳細介紹了接口定義，實現，註冊表設置和客戶端調用，以解決網絡問題和安全性等挑戰。
如何使用Java的插座API進行網絡通信？Mar 11, 2025 pm 05:53 PM本文詳細介紹了用於網絡通信的Java的套接字API，涵蓋了客戶服務器設置，數據處理和關鍵考慮因素，例如資源管理，錯誤處理和安全性。 它還探索了性能優化技術，我
如何在Java中創建自定義網絡協議？Mar 11, 2025 pm 05:52 PM本文詳細介紹了創建自定義Java網絡協議。 它涵蓋協議定義（數據結構，框架，錯誤處理，版本控制），實現（使用插座），數據序列化和最佳實踐（效率，安全性，維護
熱AI工具
Undresser.AI Undress
人工智慧驅動的應用程序，用於創建逼真的裸體照片
AI Clothes Remover
用於從照片中去除衣服的線上人工智慧工具。
Undress AI Tool
免費脫衣圖片
Clothoff.io
AI脫衣器
AI Hentai Generator
免費產生 AI 無盡。
熱門文章
熱工具
Safe Exam Browser
Safe Exam Browser是一個安全的瀏覽器環境，安全地進行線上考試。該軟體將任何電腦變成一個安全的工作站。它控制對任何實用工具的訪問，並防止學生使用未經授權的資源。
SublimeText3 Mac版
神級程式碼編輯軟體(SublimeText3)
Atom編輯器mac版下載
最受歡迎的的開源編輯器
SublimeText3 英文版
推薦：為Win版本，支援程式碼提示！
記事本++7.3.1
好用且免費的程式碼編輯器
