????????數(shù)據(jù)結(jié)構(gòu)中的八大排序算法是計算機(jī)科學(xué)領(lǐng)域經(jīng)典的排序方法，它們各自具有不同的特點(diǎn)和適用場景。以下是這八大排序算法的詳細(xì)介紹：

一、插入排序（Insertion Sort）

• 核心思想：將數(shù)組中的所有元素依次跟前面已經(jīng)排好的元素相比較，如果選擇的元素比已排序的元素小，則交換，再和前一個比較，直到全部元素都比較過。
• 時間復(fù)雜度：O(n^2)，其中n是待排序元素的個數(shù)。在元素接近有序時，時間復(fù)雜度可以降低到O(n)。
• 空間復(fù)雜度：O(1)，因為排序過程中只需要常量的額外空間。
• 穩(wěn)定性：穩(wěn)定，即相同元素在排序后的相對位置不變。

package 排序;import java.util.Arrays;public class Insert{//插入排序public  static void main(String[] args) {int[] arr= {5,7,4,2,0,3,1,6};sort(arr);System.out.println(Arrays.toString(arr));}public static void sort(int[] arr) {for(int i=1;i<arr.length;i++) {for(int j=i-1;j>=0;j--) {if(arr[j]>arr[j+1]) {int temp =arr[j];arr[j]=arr[j+1];arr[j+1]=temp;}else {break;}}}}
}

二、希爾排序（Shell Sort）

• 核心思想：希爾排序是插入排序的一種優(yōu)化版本，也稱為縮小增量排序。它先將數(shù)組分成若干子數(shù)組，每個子數(shù)組進(jìn)行插入排序，然后逐漸縮小子數(shù)組的大小，直到整個數(shù)組有序。
• 時間復(fù)雜度：不固定，但通常在O(n2)之間，取決于gap的取值方法。
• 空間復(fù)雜度：O(1)。
• 穩(wěn)定性：不穩(wěn)定，因為相同元素可能在不同的子數(shù)組中進(jìn)行排序，導(dǎo)致相對位置改變。

package 排序;import java.util.Arrays;public class Shell{//希爾排序（縮小增量）public  static void main(String[] args) {int[] arr= {5,7,4,2,0,3,1,6};sort(arr);System.out.println(Arrays.toString(arr));}public static void sort(int[] arr) {for(int grep=arr.length/2;grep>0;grep=grep/2) {	for(int i=grep;i<arr.length;i++) {for(int j=i-grep;j>=0;j=j-grep) {if(arr[j]>arr[j+grep]) {int temp =arr[j];arr[j]=arr[j+grep];arr[j+grep]=temp;}else {break;}}}}}
}

三、冒泡排序（Bubble Sort）

• 核心思想：相鄰兩個元素進(jìn)行比較，如果前一個比后一個大，則交換它們的位置。這樣，每一輪循環(huán)都會將一個最大的元素“冒泡”到數(shù)組的末尾。
• 時間復(fù)雜度：O(n^2)，因為每一輪都需要遍歷整個數(shù)組。
• 空間復(fù)雜度：O(1)。
• 穩(wěn)定性：穩(wěn)定，因為相同元素不會進(jìn)行交換。

package 排序;import java.util.Arrays;public class Bubble{//冒泡public  static void main(String[] args) {int[] arr= {5,6,71,25,31,42,36,9,4};sort(arr);System.out.println(Arrays.toString(arr));}public static void sort(int[] arr) {for(int j=0;j<arr.length;j++) {for(int i=0;i<arr.length-1;i++) {if(arr[i]>arr[i+1]) {int temp =arr[i];arr[i]=arr[i+1];arr[i+1]=temp;}}}}
}

四、快速排序（Quick Sort）

• 核心思想：選擇一個元素作為基準(zhǔn)（pivot），將數(shù)組分成兩部分，一部分小于基準(zhǔn)，一部分大于基準(zhǔn)。然后遞歸地對這兩部分進(jìn)行排序。
• 時間復(fù)雜度：平均情況下為O(nlogn)，但在最壞情況下（如數(shù)組已經(jīng)有序）會蛻化為冒泡排序，時間復(fù)雜度為O(n^2)。不過，通過隨機(jī)選擇基準(zhǔn)或三數(shù)取中法等方法可以降低最壞情況的發(fā)生概率。
• 空間復(fù)雜度：O(logn)（遞歸調(diào)用棧空間），但在最壞情況下會達(dá)到O(n)（當(dāng)數(shù)組極度不平衡時）。
• 穩(wěn)定性：不穩(wěn)定，因為相同元素可能在不同的分區(qū)過程中被交換。

package 排序;import java.util.Arrays;public class Quick{//快速排序public static void main(String[] args) {int[] arr= {5,6,71,25,36,9,4};int left=0;int right=arr.length-1;sort(arr,left,right);System.out.println(Arrays.toString(arr));}private static void sort(int[] arr,int left,int right) {if(left>=right) {return;}int base=arr[left];int i=left;int j=right;while(i!=j) {while(arr[j]>=base&&i<j) {j--;}//i游標(biāo)從前往后走找比基準(zhǔn)數(shù)大的while(arr[i]<=base&&i<j) {i++;}//i和j進(jìn)行交換int temp=arr[i];arr[i]=arr[j];arr[j]=temp;}//i和j相遇 基準(zhǔn)數(shù)和相遇位置進(jìn)行交換arr[left]=arr[i];arr[i]=base;//排序左邊sort(arr,left,i-1);//排序右邊sort(arr,i+1,right);}}