自学内容网 自学内容网
自学内容网 > 正文

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

🕗 发布于 2024-10-17 05:09 数据结构  

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

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

}

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


原文地址：https://blog.csdn.net/2301_78566776/article/details/142993133

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

相关文章

自学内容网
Copyright © 2015-2024