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

news/2024/10/17 18:28:30/

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

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

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


http://www.ppmy.cn/news/1539770.html

相关文章

SparkSQL介绍及使用

SparkSQL介绍及使用

文章目录 1. SparkSQL介绍及使用1.1 SparkSQL介绍1.2 数据结构的形式1.3 Spark SQL 特点1.4 Spark SQL 和 Hive SQL关系 1. SparkSQL介绍及使用 1.1 SparkSQL介绍 Spark SQL是Apache Spark 用于处理结构化数据&#xff08;DataFrame和Datasets&#xff09;的模块。 在Spark1.0…
阅读更多...
二叉树最小深度（递归）

二叉树最小深度（递归）

111. 二叉树的最小深度 - 力扣&#xff08;LeetCode&#xff09; 给定一个二叉树&#xff0c;找出其最小深度。 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 说明&#xff1a;叶子节点是指没有子节点的节点。 示例 1&#xff1a; 输入&#xff1a;root [3,…
阅读更多...
微信小程序 - 供应链系统设计

微信小程序 - 供应链系统设计

文章目录 一、系统概述二、系统架构设计三、系统安全设计四、系统性能优化五、系统部署与维护 在当今数字化时代&#xff0c;供应链管理对于企业的高效运营至关重要。微信小程序作为一种便捷的移动应用形式&#xff0c;为供应链系统的开发提供了新的机遇。本文将从系统架构设计…
阅读更多...
Embedding实现GPT回答和知识库内容相关的内容

Embedding实现GPT回答和知识库内容相关的内容

现在的gpt应用基本都实现了这个场景的应用&#xff0c;比如&#xff1a; 联网搜索&#xff0c;根据网上找到的内容来回答你的内容&#xff0c;像bing和kimi或者其他AI搜索引擎智能客服&#xff0c;把网站里的内容或者相关的其他什么资料预置到系统中&#xff0c;提高回答的质量…
阅读更多...
扫雷（C 语言）

扫雷（C 语言）

目录 一、游戏设计分析二、各个步骤的代码实现1. 游戏菜单界面的实现2. 游戏初始化3. 开始扫雷 三、完整代码四、总结 一、游戏设计分析 本次设计的扫雷游戏是展示一个 9 * 9 的棋盘&#xff0c;然后输入坐标进行判断&#xff0c;若是雷&#xff0c;则游戏结束&#xff0c;否则…
阅读更多...
MySQL-11.DQL-基本查询

MySQL-11.DQL-基本查询

一.DQL语句 -- DQL:基本查询 -- 1.查询指定字段 name&#xff0c;entrydate并返回 select name , entrydate from tb_emp;-- 2.查询返回所有字段 select id, username, password, name, gender, image, job, entrydate, create_time, update_time from tb_emp;select * from tb…
阅读更多...
农合生活平台用户量已突破5万人大关。

农合生活平台用户量已突破5万人大关。

回顾走来的这一路&#xff0c;农合生活一直在成长的路上&#xff0c;从未停歇。 2024年1月&#xff0c;农合生活小程序1.0推出&#xff0c;上线1个月GMV破百万&#xff1b; 2024年4月&#xff0c;农合生活APP上线&#xff0c;注册用户破万&#xff1b; 2024年4月&#xff0c;…
阅读更多...
Excelize 开源基础库 2.9.0 版本正式发布

Excelize 开源基础库 2.9.0 版本正式发布

Excelize 是 Go 语言编写的用于操作 Office Excel 文档基础库&#xff0c;基于 ECMA-376&#xff0c;ISO/IEC 29500 国际标准。可以使用它来读取、写入由 Excel、WPS、OpenOffice 等办公软件创建的电子表格文档。支持 XLAM / XLSM / XLSX / XLTM / XLTX 等多种文档格式&#xf…
阅读更多...
最新文章

Copyright @ 2022~2023