数据结构——八大排序（下）

        数据结构中的八大排序算法是计算机科学领域经典的排序方法，它们各自具有不同的特点和适用场景。以下是这八大排序算法的详细介绍：

五、选择排序（Selection Sort）

• 核心思想：每一轮从未排序的元素中选择最小（或最大）的元素，放到已排序的序列末尾。
• 时间复杂度：O(n^2)，因为每一轮都需要遍历整个未排序的数组。
• 空间复杂度：O(1)。
• 稳定性：不稳定，因为选择最小（或最大）元素时可能会破坏相同元素的相对位置。

package 排序;import java.util.Arrays;public class Selection{//选择排序public  static void main(String[] args) {int[] arr= {15,27,34,62,30,16};sort(arr);System.out.println(Arrays.toString(arr));}public static void sort(int[] arr) {for(int j=0;j<arr.length;j++) {int min=arr[j];int minIndex=j;for(int i=j;i<arr.length;i++) {if(arr[i]<min) {min=arr[i];minIndex=i;}}arr[minIndex]=arr[j];arr[j]=min;}	}
}

六、堆排序（Heap Sort）

• 核心思想：利用堆这种数据结构进行排序。首先构建一个大顶堆（或小顶堆），然后依次将堆顶元素（最大或最小）与堆底元素交换，并减少堆的大小。最后，对剩余的元素重新调整成堆，直到整个数组有序。
• 时间复杂度：O(nlogn)，因为构建堆和调整堆的时间复杂度都是O(logn)，而需要构建和调整n次。
• 空间复杂度：O(1)，因为排序过程中只需要常量的额外空间（用于交换元素）。
• 稳定性：不稳定，因为堆的调整过程中可能会破坏相同元素的相对位置。

package 排序;import java.util.Arrays;public class Heap{
//堆排序public static void main(String[] args) {int[] arr= {5,7,4,2,0,1,6};//一、构建大顶堆for (int p=arr.length-1;p>=0;p--) {sort(arr, p, arr.length);}//二、堆底堆顶元素进行交换for(int i=arr.length-1;i>0;i--) {int temp=arr[i];arr[i]=arr[0];arr[0]=temp;sort(arr, 0, i);}//打印System.out.println("堆排序的结果为：");System.out.println(Arrays.toString(arr));}//堆的维护public static void sort(int[] arr,int parent,int length) {//定义左孩子int child=2*parent+1;while(child<length) {//定义右孩子int rchild=child+1;if(rchild<length && arr[rchild]>arr[child]) {child++;}//child指向左右孩子中的最大值//父子节点进行比较if(arr[parent]<arr[child]) {//父子节点进行交换int temp=arr[parent];arr[parent]=arr[child];arr[child]=temp;//parent指向child,child继续指向左右孩子中的最大值parent=child;child=2*child+1;}else {break;}}}
}

七、归并排序（Merge Sort）

• 核心思想：将数组分成两部分，分别进行排序，然后将两部分合并成一个有序数组。这个过程可以递归地进行。
• 时间复杂度：O(nlogn)，因为每次合并都需要遍历两个有序数组。
• 空间复杂度：O(n)，因为需要额外的空间来存储合并后的有序数组（虽然可以使用原地归并算法来减少空间复杂度，但实现起来较为复杂）。
• 稳定性：稳定，因为合并过程中相同元素会保持相对位置不变。

package 排序;import java.util.Arrays;public class Merge{public static void main(String[] args) {int[] arr= {11,22,33,55,2,11,24,63};mergeSort(arr,0,arr.length-1);System.out.println(Arrays.toString(arr));}//拆分public static void mergeSort(int[] arr, int left, int right) {//递归出口if(left==right) {return;}int mid=(left+right)/2;//向左拆分mergeSort(arr,left,mid);//向右拆分mergeSort(arr,mid+1,right);//合并merge(arr,left,right,mid);}public static void merge(int[] arr,int left,int right,int mid) {//定义第一段和第二段的开始int s1=left;int s2=mid+1;//定义临时空间int[] temp =new int[right-left+1];int index=0;//定义游标遍历临时空间//判断s1和s2指向的数据大小，将其存入临时数组while(s1<=mid&&s2<=right) {if(arr[s1]<arr[s2]) {temp[index]=arr[s1];s1++;index++;}else {temp[index]=arr[s2];s2++;index++;}}//判断s1中是否有数据，如果有将其放入临时数组当中while(s1<=mid) {temp[index]=arr[s1];s1++;index++;}//判断s2中是否有数据，如果有将其放入临时数组当中while(s2<=right) {temp[index]=arr[s2];s2++;index++;}//将临时数组中的数据写回原数组for(int i=0;i<temp.length;i++) {arr[left+i] = temp[i];}}
}

八、基数排序（Radix Sort）

• 核心思想：基数排序是一种非比较型排序算法，它根据元素的位数（或字符）进行排序。通常从最低有效位（或字符）开始，依次对每一位（或字符）进行计数排序或桶排序，直到最高有效位（或字符）为止。
• 时间复杂度：O(d(n+r))，其中d是位数（或字符数），n是待排序元素的个数，r是基数（如对于十进制数，r=10）。
• 空间复杂度：O(n+r)，因为需要额外的空间来存储桶或计数数组。
• 稳定性：稳定，因为每一位（或字符）的排序过程中都保持相同元素的相对位置不变。

package 排序;import java.util.Arrays;public class Radix{//基数排序，注意，基数排序只能排整数。适用于数据位数不多，但数据量大的数据集public static void main(String[] args) {int[] arr= {50,17,41,20,101,11,26,35,47,63,214,63,88};sort(arr);System.out.println(Arrays.toString(arr));}public static void sort(int[] arr) {//取最大值，计算最大值的位数int max=arr[0];for(int j=0;j<arr.length;j++) {if(arr[j]>max) {max=arr[j];}}int maxLen=(max+"").length();//返回最大值的位数System.out.println("最大值的位数为"+maxLen);//定义桶（本质上定义二维数组）int[][] bucket=new int[10][arr.length];//定义桶记录工具（一维数组，长度为10）int[] elementCounts=new int[10];int n=1;//放入取出来来回回执行maxLen遍for(int m=0;m<maxLen;m++) {//遍历数组，将数组中的数据放入桶中for(int i=0;i<arr.length;i++) {//个位开始排序int element =arr[i]/n%10;  //element代表个位数值，也代表要被放在哪个桶//读取桶记录工具中的数值int count=elementCounts[element];//数据放入bucket[element][count]=arr[i];elementCounts[element]++;}//将桶中的数据取出int index=0;//定义index游标，遍历数组，将桶中数据存入数组里for(int k=0;k<elementCounts.length;k++) {if(elementCounts[k]!=0) {//不为0桶中有数据，将数据取出for(int l=0;l<elementCounts[k];l++) {arr[index]=bucket[k][l];index++;}}//清理桶记录elementCounts[k]=0;}n=n*10;}}	}

综上所述，这八大排序算法各有优缺点和适用场景。在实际应用中，需要根据待排序数据的特点和具体需求来选择合适的排序算法。