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

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

五、选择排序（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;
		}
	}	
	
}

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