数据结构——八大排序（上）
数据结构中的八大排序算法是计算机科学领域经典的排序方法，它们各自具有不同的特点和适用场景。以下是这八大排序算法的详细介绍：
一、插入排序（Insertion Sort）
- 核心思想：将数组中的所有元素依次跟前面已经排好的元素相比较，如果选择的元素比已排序的元素小，则交换，再和前一个比较，直到全部元素都比较过。
- 时间复杂度：O(n^2)，其中n是待排序元素的个数。在元素接近有序时，时间复杂度可以降低到O(n)。
- 空间复杂度：O(1)，因为排序过程中只需要常量的额外空间。
- 稳定性：稳定，即相同元素在排序后的相对位置不变。
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）
- 核心思想：希尔排序是插入排序的一种优化版本，也称为缩小增量排序。它先将数组分成若干子数组，每个子数组进行插入排序，然后逐渐缩小子数组的大小，直到整个数组有序。
- 时间复杂度：不固定，但通常在O(n2)之间，取决于gap的取值方法。
- 空间复杂度：O(1)。
- 稳定性：不稳定，因为相同元素可能在不同的子数组中进行排序，导致相对位置改变。
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）
- 核心思想：相邻两个元素进行比较，如果前一个比后一个大，则交换它们的位置。这样，每一轮循环都会将一个最大的元素“冒泡”到数组的末尾。
- 时间复杂度：O(n^2)，因为每一轮都需要遍历整个数组。
- 空间复杂度：O(1)。
- 稳定性：稳定，因为相同元素不会进行交换。
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）
- 核心思想：选择一个元素作为基准（pivot），将数组分成两部分，一部分小于基准，一部分大于基准。然后递归地对这两部分进行排序。
- 时间复杂度：平均情况下为O(nlogn)，但在最坏情况下（如数组已经有序）会蜕化为冒泡排序，时间复杂度为O(n^2)。不过，通过随机选择基准或三数取中法等方法可以降低最坏情况的发生概率。
- 空间复杂度：O(logn)（递归调用栈空间），但在最坏情况下会达到O(n)（当数组极度不平衡时）。
- 稳定性：不稳定，因为相同元素可能在不同的分区过程中被交换。
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游标从前往后走找比基准数大的while(arr[i]<=base&&i<j) {i++;}//i和j进行交换int temp=arr[i];arr[i]=arr[j];arr[j]=temp;}//i和j相遇 基准数和相遇位置进行交换arr[left]=arr[i];arr[i]=base;//排序左边sort(arr,left,i-1);//排序右边sort(arr,i+1,right);}}