【数据结构与算法 11】常见的7种排序算法 | 您所在的位置:网站首页 › 7种排序 › 【数据结构与算法 11】常见的7种排序算法 |
(三)插入排序
1、基本思想 把n个待排序的元素第一位看成有序表,其它的看成无序表,排序过程中,每次从无序表中取出一个数,依次与有序表中的数进行比较,插入到合适的位置。 2、动态效果图 3、代码实现 //插入排序 public static void insertSort(int[] arr ){ int insertVal = 0; int insertIndex = 0; for (int i = 1; i < arr.length; i++) { //定义待插入的数 insertVal = arr[i]; // 即arr[i]的前面这个数的下标 insertIndex = i - 1; // 给insertVal 找到插入的位置 // 说明 // 1. insertIndex >= 0 保证在给insertVal 找插入位置,不越界 // 2. insertVal < arr[insertIndex] 待插入的数,还没有找到插入位置 // 3. 就需要将 arr[insertIndex] 后移 while(insertIndex >= 0 && insertVal < arr[insertIndex]){ arr[insertIndex+1] = arr[insertIndex]; insertIndex–; } // 当退出while循环时,说明插入的位置找到, insertIndex + 1 if(insertIndex + 1 != i){ arr[insertIndex+1] = insertVal; } } } 4、速度测试 插入排序:120000数据,1秒 (四)希尔排序1、基本思想 希尔排序也是一种插入排序,它是简单插入排序经过改进之后的一个更高效的版本,也称为缩小增量排序,同时该算法也是冲破O(n²)的第一批算法之一。它与插入排序的不同之处在于,它会优先比较较远的元素。 2、效果图 3、代码实例 希尔排序有两种方式。 ①希尔排序(冒泡排序) //希尔排序 // 使用逐步推导的方式来编写希尔排序 // 希尔排序时, 对有序序列在插入时采用交换法, // 思路(算法) ===> 代码 public static void shellSort(int[] arr){ // 根据前面的逐步分析,使用循环处理 for(int step = arr.length/2;step>0;step /= 2 ){ for (int i = step; i < arr.length; i++) { // 遍历各组中所有的元素(共step组,每组有个元素), 步长step for (int j = i - step; j >= 0; j -= step) { // 如果当前元素大于加上步长后的那个元素,说明交换 if (arr[j] > arr[j + step]) { int temp = arr[j]; arr[j] = arr[j + step]; arr[j + step] = temp; } } } } } 速度测试: 冒泡法希尔排序:120000数据,11秒 ②希尔排序(插入排序) //对交换式的希尔排序进行优化->插入法 public static void shellSort2(int[] arr) { // 增量step, 并逐步的缩小增量 for (int step = arr.length / 2; step > 0; step /= 2) { // 从第step个元素,逐个对其所在的组进行直接插入排序 for (int i = step; i < arr.length; i++) { int j = i; int temp = arr[j]; if(arr[j] arr[j] = arr[j-step]; j -= step; } arr[j] = temp; } } } 速度测试: 插入法希尔排序:12000000数据,4秒,叹为观止 (五)快速排序1、基本思想 通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录进行排序,以达到整个排序的过程。 2、效果图 3、算法描述 快速排序使用分治法把一个串分为两个子串; 找一个基准点,暂时选中间点为基准点; 重新排序数列,比基准值小的放在基准点前面,大的放在后面; 递归的把小于基准值的子数列和大于基准值的子数列排序; 4、代码实例 //快速排序 public static void quickSort(int[] arr,int left, int right) { int l = left; //左下标 int r = right; //右下标 //pivot 中轴值 int pivot = arr[(left + right) / 2]; int temp = 0; //临时变量,作为交换时使用 //while循环的目的是让比pivot 值小放到左边 //比pivot 值大放到右边 while( l < r) { //在pivot的左边一直找,找到大于等于pivot值,才退出 while( arr[l] < pivot) { l += 1; } //在pivot的右边一直找,找到小于等于pivot值,才退出 while(arr[r] > pivot) { r -= 1; } //如果l >= r说明pivot 的左右两的值,已经按照左边全部是 //小于等于pivot值,右边全部是大于等于pivot值 if( l >= r) { break; } //交换 temp = arr[l]; arr[l] = arr[r]; arr[r] = temp; //如果交换完后,发现这个arr[l] == pivot值 相等 r–, 前移 if(arr[l] == pivot) { r -= 1; } //如果交换完后,发现这个arr[r] == pivot值 相等 l++, 后移 if(arr[r] == pivot) { l += 1; } } // 如果 l == r, 必须l++, r–, 否则为出现栈溢出 if (l == r) { l += 1; r -= 1; } //向左递归 if(left < r) { quickSort(arr, left, r); } //向右递归 if(right > l) { quickSort(arr, l, right); } } 5、速度测试 快速排序:12000000数据,1秒,逆天而行 (六)归并排序1、基本思想 归并排序采用经典的分治策略,分治法将问题分成一些小的问题然后递归解决,则治的阶段就是将分的阶段得到的答案修补在一起,即分而治之。 2、效果图 3、代码实现 //归并排序 public static void mergerSort(int[] arr,int left,int right,int[] temp){ if(left int i = left; // 初始化i, 左边有序序列的初始索引 int j = middle + 1; //初始化j, 右边有序序列的初始索引 int t = 0; // 指向temp数组的当前索引 //先把左右两边(有序)的数据按照规则填充到temp数组 //直到左右两边的有序序列,有一边处理完毕为止 while (i temp[t] = arr[i]; t++; i++; } //右边的有序序列还有剩余的元素,就全部填充到temp while (j arr[tempLeft] = temp[t]; t++; tempLeft++; } } 4、速度测试 归并排序:12000000数据,1秒,惊为天人 (七)基数排序1、基本思想 将所有带比较数值统一为同样的数位长度,数据较短的数前面补0,然后从最低位开始依次进行依次排序,这样从最低位排序一直到最高位排序完成之后,数列就变成了一个有序序列。 2、动态效果图 3、代码实例 //基数排序 public static void radixSort(int arr[]){ System.out.println(“基数排序,arr长度:”+arr.length); //1. 得到数组中最大的数的位数 int max = arr[0]; //假设第一数就是最大数 for(int i = 1; i < arr.length; i++) { if (arr[i] > max) { max = arr[i]; } 自我介绍一下,小编13年上海交大毕业,曾经在小公司待过,也去过华为、OPPO等大厂,18年进入阿里一直到现在。 深知大多数Java工程师,想要提升技能,往往是自己摸索成长或者是报班学习,但对于培训机构动则几千的学费,着实压力不小。自己不成体系的自学效果低效又漫长,而且极易碰到天花板技术停滞不前! 因此收集整理了一份《2024年Java开发全套学习资料》,初衷也很简单,就是希望能够帮助到想自学提升又不知道该从何学起的朋友,同时减轻大家的负担。 既有适合小白学习的零基础资料,也有适合3年以上经验的小伙伴深入学习提升的进阶课程,基本涵盖了95%以上Java开发知识点,真正体系化! 由于文件比较大,这里只是将部分目录截图出来,每个节点里面都包含大厂面经、学习笔记、源码讲义、实战项目、讲解视频,并且会持续更新! 如果你觉得这些内容对你有帮助,可以扫码获取!!(备注Java获取) 最后手绘了下图所示的kafka知识大纲流程图(xmind文件不能上传,导出图片展现),但都可提供源文件给每位爱学习的朋友 《互联网大厂面试真题解析、进阶开发核心学习笔记、全套讲解视频、实战项目源码讲义》点击传送门即可获取! [外链图片转存中…(img-Cn42SXV1-1713420866584)] [外链图片转存中…(img-z1XseXdb-1713420866584)] 既有适合小白学习的零基础资料,也有适合3年以上经验的小伙伴深入学习提升的进阶课程,基本涵盖了95%以上Java开发知识点,真正体系化! 由于文件比较大,这里只是将部分目录截图出来,每个节点里面都包含大厂面经、学习笔记、源码讲义、实战项目、讲解视频,并且会持续更新! 如果你觉得这些内容对你有帮助,可以扫码获取!!(备注Java获取) 最后手绘了下图所示的kafka知识大纲流程图(xmind文件不能上传,导出图片展现),但都可提供源文件给每位爱学习的朋友 [外链图片转存中…(img-B8XkHZzk-1713420866585)] 《互联网大厂面试真题解析、进阶开发核心学习笔记、全套讲解视频、实战项目源码讲义》点击传送门即可获取! |
今日新闻 |
推荐新闻 |
专题文章 |
CopyRight 2018-2019 实验室设备网 版权所有 |