二维码网站建设源码,奉化网站关键词优化费用,wordpress 主题字号,湛江专业建站公司排序算法(二) 前面介绍了排序算法的时间复杂度和空间复杂数据结构与算法—排序算法#xff08;一#xff09;时间复杂度和空间复杂度介绍-CSDN博客#xff0c;这次介绍各种排序算法——冒泡排序、选择排序、插入排序、希尔排序、快速排序、归并排序、基数排序。 文章目录 排…排序算法(二) 前面介绍了排序算法的时间复杂度和空间复杂数据结构与算法—排序算法一时间复杂度和空间复杂度介绍-CSDN博客这次介绍各种排序算法——冒泡排序、选择排序、插入排序、希尔排序、快速排序、归并排序、基数排序。 文章目录 排序算法(二)1.冒泡排序1.1 基本介绍1.2 冒泡排序应用实例1.3 冒泡排序时间复杂度测试 2.选择排序2.1 基本介绍2.2 排序思想2.3 选择排序应用实例2.4 选择排序时间复杂度测试 3. 插入排序3.1 基本介绍3.2 排序思想3.3 插入排序应用实例3.4 插入排序时间复杂度测试 4. 希尔排序4.1 简单的插入排序存在的问题4.2 希尔排序法介绍4.3 基本思想4.4 希尔排序法应用实例4.4.1 交换法4.4.2 移位法 4.5 希尔排序时间复杂度测试4.5.1 交换法4.5.2 移位法 5. 快速排序5.1 基本介绍5.2 应用实例5.3 快速排序时间复杂度测试 6. 归并排序6.1 基本介绍6.2 基本思想6.3 应用实例6.3.1 归并排序—自顶向下6.3.2 归并排序—自下而上6.3.3 归并排序插入排序 6.4 归并排序时间复杂度测试 7 基数排序7.1 基本介绍7.2 基本思想7.3 应用实例7.4 时间复杂度测试 8.常用排序算法总结和对比 1.冒泡排序
1.1 基本介绍 **冒泡排序Bubble Sorting)**的基本思想是:通过对待排序序列从前向后从下标较小的元素开始,依次比较相邻元素的值若发现逆序则交换使值较大 的元素逐渐从前移向后部就像水底下的气泡一样逐渐向上冒。 因为排序的过程中各元素不断接近自己的位置如果一趟比较下来没有进行过交换就说明序列有序因此要在排序过程中设置 一个标志flag判断元素是否进行过交换。从而减少不必要的比较。(这里说的优化可以在冒泡排序写好后再进行)
1.2 冒泡排序应用实例 将五个无序的数:3,9,-1,10,20使用冒泡排序法将其排成一个从小到大的有序数列。 图1 排序过程图 小结冒泡排序规则
一共进行数组大小-1次大循环每一趟排序的次数在逐渐减少如果在某躺排序中没有发生过一次交换可以提前结束冒泡排序。这就是优化。
代码如下
package com.atguigu.sort;/*** author 小小低头哥* version 1.0* 冒泡排序*/
public class BubbleSort {public static void main(String[] args) {int arr[] {3, 9, -1, 10, -2};bubble(arr);System.out.println(排序后的数组);for (int i 0; i arr.length; i) {System.out.print(arr[i] );}}//将前面的冒泡排序 封装成一个方法public static void bubble(int[] arr){boolean flag false; //标识变量 表示是否进行过交换for (int i 0; i arr.length - 1; i) {flag false; //重新置false 看这一轮是否进行过交换for (int j 0; j arr.length - i - 1; j) {if (arr[j 1] arr[j]) { //如果后面的小于前面的 则交换flag true; //表示进行过交换int t arr[j 1];arr[j 1] arr[j];arr[j] t;}}if(!flag){ //说明此次排序中 一次交换都没有发生过 说明已经排序完毕break; //结束继续排序}}}
}1.3 冒泡排序时间复杂度测试
代码如下 public static void main(String[] args) {
// int arr[] {3, 9, -1, 10, -2};//测试一下冒泡排序的速度O(n^2)给80000个数据进行测试//创建80000个随机的数组//处理80000个数据所花的时间为:9360//处理160000个数据所花的时间为:37083int[] arr new int[160000];for (int i 0; i arr.length; i) {//Math.random() [0 1)的小数//(Math.random() * 8000000) [0 8000000)小数//(int) (Math.random() * 8000000) [0-8000000)的整数arr[i] (int) (Math.random() * 8000000);}long start System.currentTimeMillis();bubble(arr);long end System.currentTimeMillis();System.out.println(处理 arr.length 个数据所花的时间为: (end - start));}结果为
处理80000个数据所花的时间为:9360处理160000个数据所花的时间为:37083
可以看出当数据量翻倍的时候由冒泡排序时间复杂度 O ( n 2 ) O(n^2) O(n2)知当变成2n时时间复杂度为 O ( 4 n 2 ) O(4n^2) O(4n2)。时间复杂度变成了四倍正好和测试结果对的上太神奇了!
2.选择排序
2.1 基本介绍 选择排序也属于内部排序法是从欲排序的数据中按指定的规则选出某一元素再依规定交换位置后达到排序的目的。
2.2 排序思想 选择排序(select sorting)也是一种简单的排序方法。它的基本思想是:第一次从arr[o]~arr[n-1]中选取最小值与arr[0]交换第二次从arr[1] arr[n-1]中选取最小值与arr[1]交换第三次从arr[2]~arr[n-1]中选取最小值 与arr[2]交换…第i次从arr[i-1]~arr[n-1]中选取最小值与arr[i-1]交换…第n-1次从arr[n-2] ~arr[n-1]中选取最小值与arr[n-2]交换总共通过n-1次得到一个按排序码从小到大排列的有序序列。 图2 选择排序思路图 2.3 选择排序应用实例
有一群牛颜值分别是101,34,119,1请使用选择排序从低到高进行排序[101,34,119,1]。
代码如下
package com.atguigu.sort;/*** author 小小低头哥* version 1.0* 选择排序*/
public class SelectSort {public static void main(String[] args) {int[] arr {101, 34, 119, 1,3,2342,532,5};//选择排序selectSort(arr);System.out.println(排序后的数据为:);for (int i 0; i arr.length; i) {System.out.print(arr[i] );}}private static void selectSort(int[] arr) {int index; //记录每次大循环中最小数的位置for (int i 0; i arr.length; i) {index i; //每次大循环初始化为第i个 没被排序的第一个for (int j i 1; j arr.length; j) {if (arr[j] arr[index]) {//如果小于指定位置的数//则重新指向更小位置的数index j;}}//一次大循环结束后 Index就记录下了最小数的位置if(index ! i){ //说明最小数确实不是第i个位置的数 index发生了变换//将其与第i个位置的数进行交换int temp arr[i];arr[i] arr[index];arr[index] temp;}}}
}2.4 选择排序时间复杂度测试
测试代码和1.3中几乎相同不过是bubble()排序函数换成了selectSort函数。
结果为:
处理80000个数据所花的时间为:3350处理160000个数据所花的时间为:13237
可以看出当数据量翻倍的时候由选择排序时间复杂度 O ( n 2 ) O(n^2) O(n2)知当变成2n时时间复杂度为 O ( 4 n 2 ) O(4n^2) O(4n2)。时间复杂度变成了四倍正好和测试结果对的上。与冒泡排序相同。
**进一步分析**选择排序法相对于冒泡排序速度更快主要是减少了交换的次数。冒泡排序每次大循环中符合条件就进行值交换而选择排序每次大循环中只进行一次。
3. 插入排序
3.1 基本介绍 插入式排序属于内部排序法是对于欲排序的元素以插入的方式找寻该元素的适当位置以达到排序的目的。
3.2 排序思想 插入排序 (Insertion Sorting) 的基本思想是把n个待排序的元素看成一个有序表和一个无序表开始时有序表中只包含一个元素无序表中包含有n-1个元素排序过程中每次从无序表中取出第一个元素把它的排序码依次与有序表元素的排序码进行比较将它插入到有序表中的适当位置使之成为新的有序表 图3 插入排序思路图 3.3 插入排序应用实例
自己写的如下
package com.atguigu.sort;/*** author 小小低头哥* version 1.0* 插入排序*/
public class InsertSort {public static void main(String[] args) {int[] arr1 {17, 3, 25, 60, 4, 15,34,23,45,53,2}; //无序数组arr1 insertSort(arr1);System.out.println(插入排序后的数组为:);for (int i 0; i arr1.length; i) {System.out.print(arr1[i] );}}public static int[] insertSort(int[] arr1){int[] arr2 new int[arr1.length]; //有序数组arr2[0] arr1[0]; //先将第一个值直接移入有序数组for (int i 1; i arr1.length; i) { //总共比较arr2.length - 1次for (int j 0; j i; j) { //每次比较i次if (arr1[i] arr2[j]) { //说明可以插入了for (int k i; k j; k--) {arr2[k] arr2[k - 1]; //从第j个元素开始将arr2的元素往后移}arr2[j] arr1[i]; //将元素插入break; //结束本次小循环}if (j i - 1) { //如果执行到这一步 则说明arr1[i] 在arr2中最大 直接放在最后arr2[i] arr1[i];}}}return arr2; //返回新的有序数组}
}弹幕很多人推荐使用链表的形式确实会简单直接插入进去就好了不需要像数组一样还要后移操作。但是目前只是为了熟悉这个算法就还是使用的是大家普遍了解的引用数据类型一维数组的形式。没想到后面韩老师使用数组的方法更加方便
韩老师代码如下
public static void main(String[] args) {int[] arr1 {17, 3, 25, 60, 4, 15,34,23,45,53,2}; //无序数组insertSort(arr1);System.out.println(插入排序后的数组为:);for (int i 0; i arr1.length; i) {System.out.print(arr1[i] );}
}public static void insertSort(int[] arr){for (int i 0; i arr.length; i) {//定义待插入的数int insertVal arr[i];int insertIndex i - 1; //即arr[i]前面这个数的下标//给insertVal找到插入的位置//1. insertIndex 0 保证在给insertVal 找插入位置 不越界//2. insertVal arr[insertIndex] 待插入的数 还没有找到插入位置while (insertIndex 0 insertVal arr[insertIndex]){arr[insertIndex 1] arr[insertIndex];insertIndex--;}//退出循环是 说明插入的位置找到了 insertIndex 1arr[insertIndex 1] insertVal;}
}**太强了**韩老师就用一个数组两个循环就解决了。相比于我写的少用了一个数组和一个循环。
**一个数组**其实对比无序和有序数组一个在减一个在加无序的头前面一个正好对应有序的尾。两个数组完全可以用一个数组替代。
两个循环我的代码中是通过从前完后比较大小然后多的一个循环是k变量的循环主要是为了后移。但韩老师的代码中是从后往前比较大小在比较大小的过程中就已经实现后移了相当于把我代码中两个for循环合并成一个while循环了。如果我要把我代码中两个for循环化成一个for循环也需要改变一下比较的顺序从后往前比较。
我改进后的代码 public static void insertSort(int[] arr1) {int j;for (int i 1; i arr1.length; i) { //总共比较arr2.length - 1次int temp arr1[i]; //取出无序的第1个 并暂时将其作为有序的第i个位置的数据for ( j i - 1; j 0; j--) { //对i个数据的有效序列进行排序 每次比较i次if (temp arr1[j]) { //说明第i个大于第j个位置的arr1[j 1] arr1[j]; //将arr1[j]后移 那么下次arr1[j1]则是无效位置}else { //说明temp小于第j个位置的数 那么temp直接用temp去填入arr[j1]的地方arr1[j 1] temp; //此时将此无序数据插入成功break; //因为是有序数组 所以后面的无须再比较 本次排序结束}}//这个判断语句一定要写出来 从语法上来说可以写在里面//但是为了让执行时间少一点不用每次小循环都判断 一定要写出来if(j 0){ //如果执行到这一步 说明一直在后移 那么则此无序数据最小arr1[0] temp; //直接将其插入到首位}}}3.4 插入排序时间复杂度测试
测试代码和1.3中几乎相同只是将bubble()排序函数换成了InsertSort函数。
我的代码结果为
处理80000个数据所花的时间为:908处理160000个数据所花的时间为:4185
韩老师代码结果为
处理80000个数据所花的时间为:692处理160000个数据所花的时间为:2634
几乎是韩老师代码的三倍不过其实最坏时间复杂度是相同的。导致相差这个的原因可能是我的代码中的小循环多了点判断语句。
4. 希尔排序
4.1 简单的插入排序存在的问题
简单的插入排序可能存在的问题:
数组 arr {2,3,4, 5,6,1} 这时需要插入的数 1(最小)这样的过程是: {2,3,4,5,6,6}{2,3,4,5,5,6}{2,3,4, 4,5,6}{2,3,3,4,5,6}{2,2,3,4,5,6}{1,2,3,4,5,6}
结论: 当需要插入的数是较小的数时后移的次数明显增多对效率有影响。
4.2 希尔排序法介绍 希尔排序是希尔(Donaldshell) 于1959年提出的一种排序算法。希尔排序也是一种插入排序它是简单插入排序经过改进之后的一个更高效的版本也称为 缩小增量排序。
4.3 基本思想 希尔排序是把记录按下标的一定增量分组对每组使用直接插入排序算法排序随着增量逐渐减少每组包含的关键词越来越多当增量减至1时整个文件恰被分成一组算法便终止 图4 希尔排序示意图 经过上面的“宏观调控”整个数组的有序化程度成果喜人此时仅仅需要对以上数列简单微调无需大量移动操作即可完成整个数组的排序。 我的理解就是将一次很大的插入排序变成了几次小的插入排序。但是这几次小的插入排序的运算量(移动次数)很少比如最后一组再使用插入排序时只要判断前一个元素是否满足条件即可顶多每次就后移一位。大大减小了后移量。则时间复杂度也减少了。
4.4 希尔排序法应用实例 希尔排序法在对有序序列进行插入时有两种方式交换法移动法。
4.4.1 交换法 此方法旨在希尔排序时对有序序列插入时采用交换法
韩老师代码如下(不过注释都是我按我自己理解写的)
package com.atguigu.sort;/*** author 小小低头哥* version 1.0* 希尔排序*/
public class ShellSort {public static void main(String[] args) {int[] arr {5, 6, 1, 7, 61, 3, 41, 46, 3, 1, 55};shellSort(arr);for (int i 0; i arr.length; i) {System.out.print(arr[i] );}}private static void shellSort(int[] arr) {int len arr.length; //就算是奇数也无所谓while (len ! 1) { //当len不等于1时可以继续分组进行排序len len / 2; //分组 相当于每组的步长//之所以从len开始 是从每一组中第二个元素开始与本组中前一个元素进行比较//大循环就是控制每次每组中参与排序的元素的个数//比如ilen8 那么就是将arr[len8]所在组进行排序 且只进行排序arr[len8]及其之前的数据for (int i len; i arr.length; i) {//第二个循环之所以i-len 是用来比较本组前一个元素//j-len 是确保比较的元素都是本组中的元素 len是步长//类似于进行了一次从后往前遍历的冒泡排序的大循环//但由于除arr[i]个元素外 前面本组的元素都是有序的//所以一次从后往前遍历的冒泡排序大循环对于将arr[i]排好序足矣for (int j i - len; j 0; j - len) {//此时相当于将arr2[1,2,3,4,5,arr[i]] 进行排序if (arr[j] arr[j len]) { //如果此元素比本组中后一个元素要小//交换元素 将大的元素换到后面去int temp arr[j];arr[j] arr[j len];arr[j len] temp;} else { //说明此时本元素最大 就该放在后面//而由于前面本组元素都是有序的 所以不需要再进行判断了//本次判断结束break;}}}}}
}为啥希尔排序法也属于插入法呢需要从它第一个for循环来理解。每次进行此for循环其实就是将arr[i]这个无序的数据插入到本组中已经排好序的有序数组中(即arr[i-len],arr[i-2*len]…)。而完成此过程就是第二个for循环来完成的。第二个for循环类似于冒泡排序不过是从后面开始一个个比较(也想过能不能从前往后比较其实不行。首先就是本组的头元素不好确定其次最重要的原因就是由于交换法逐个比较类似于冒泡排序一次冒泡排序的大循环难以把一个从小到大排序的数组(外加最后一个待排序的元素)排好序)。
4.4.2 移位法
理解了交换法再理解移位法其实挺好理解的
韩老师代码如下
private static void shellSort2(int[] arr) {int len arr.length; //就算是奇数也无所谓while (len ! 1) { //当len不等于1时可以继续分组进行排序len len / 2;for (int i len; i arr.length; i) { //仍然是从每一组的第二个元素开始进行插入//接下来就是复现简单插入排序法int j i;int temp arr[i]; //保存需要插入的数据值while (j len arr[j - len] arr[j]) { //如果还没比较完最开头的元素以及不满足插入条件arr[j] arr[j - len]; //则后移j j - len;}//当退出循环后 则说明找到了插入的位置arr[j] temp;}}
}4.5 希尔排序时间复杂度测试
4.5.1 交换法
结果为:
处理80000个数据所花的时间为:14处理160000个数据所花的时间为:30
4.5.2 移位法
结果为:
处理80000个数据所花的时间为:10处理160000个数据所花的时间为:13
是的你没有看错两种方法都是这么快太他喵猛了
5. 快速排序
5.1 基本介绍 快速排序 (Quicksort)是对冒泡排序的一种改进基本思想是:通过一趟排序将要排序的数据分割成独立的两部分其中一部分的所有数据都比另外一部分的所有数据都要小然后再按此方法对这两部分数据分别进行快速排序整个排序过程可以递归进行以此达到整个数据变成有序序列。 图5 快速排序示意图 5.2 应用实例
韩老师代码如下
public static void quickSort3(int[] arr, int left, int right) {int l left; //左指针int r right; //右指针int pivot arr[(left right) / 2];int temp 0;//while循环的目的是让比pivot 值小的放到左边//比pivot值大的放到右边while (l r) {//再pivot的左边一直找 找到大于等于pivot值 才退出while (arr[l] pivot) {l;}//找出右边小于等于pivot的数while (arr[r] pivot) { //当右边的数小于等于pivot时才跳出循环r--; //没找到就找下一个}//如果 l r 说明pivot的左右两边的值 已经按照左边全部是//小于等于pivot值 右边全部是大于等于pivot值if (l r) {break;}//交换位置 将左边找到的大于等于pivot的数放在右边//将右边找到的小于等于pivot的数放在左边temp arr[r];arr[r] arr[l];arr[l] temp;//如果交换完后 发现这个arr[l] pivot值 r-- 前移if (arr[l] pivot) {r - 1;}//如果交换完后 发现arr[r] pivot值 l 后移if (arr[r] pivot) {l;}}//如果l r 必须l r-- 否则可能出现栈溢出if (l r) {l;r--;}//左递归if (left r) {quickSort3(arr, left, r);}//右递归if (right l) {quickSort3(arr, l, right);}}在尽可能理解老师代码的基础上 自己也写了一份代码 测试过不同种数据 感觉没啥毛病 public static void quickSort(int[] arr, int left, int right) {int l left; //左指针int r right; //右指针int pivot arr[(left right) / 2];
// System.out.println(pivot);int temp 0;//一下操作就为了将小于pivot的数放在其左边 大于pivot的数放在其右边while (l r) { //当l r的时候才循环//找出左边大于等于pivot的数while (arr[l] pivot) { //当左边的数大于等于pivot时才跳出循环//没找到就找下一个 最差的情况就是//l此时刚好指向arr[l] pivot的值//此时说明此位置下的pivot左边的数都小于pivotl;}//找出右边小于等于pivot的数while (arr[r] pivot) { //当右边的数小于等于pivot时才跳出循环r--; //没找到就找下一个}//两个循环结束后 l 和 r 都找到了不满足位置条件的数 的位置 对应分别为arr[l] 和 arr[r]的值//不可能出现l r的情况 因为最后总会有r或l指向privot 顶多出现l和r同时指向privotif (l r) { //说明所有数都遍历了 结束了break;}//交换位置 将左边找到的大于等于pivot的数放在右边//将右边找到的小于等于pivot的数放在左边temp arr[r];arr[r] arr[l];arr[l] temp;//此时l左边的数肯定都小于pivot//r右边的数肯定都大于pivot//但是 存在一种情况 就是都刚好等于 pivot//这个时候如果直接继续下一次循环 那么直接死循环了//为了防止这种情况while (arr[l] arr[r] arr[r] pivot) { //如果执行了这个循环 那么已r为基准 arr[r]指向pivot//那么我令左边的arr[l]是排在pivot左边的数l; //l左边的都是小于pivot的数if (l r) {break;}}/*或者while (arr[l] arr[r] arr[l] pivot) {//那么我令arr[r]是排在pivot右边的数r--; //r右边的都是大于pivot的数}*/}if (l ! r) {System.out.println(意料之外);}//从上面可以看出 退出循环的条件就是lr; 且此时指向数组中最后边的等于privot的数的位置
// System.out.println(L l r r);//除非左边只有一个数或者没数了才不左递归if (r left 1) { //说明左边起码还有两个数quickSort(arr, left, r - 1); //左递归}//除非右边只有一个数或者没数了才不右递归if (l right - 1) { //说明左边起码还有两个数quickSort(arr, l 1, right); //左递归}}5.3 快速排序时间复杂度测试
结果如下
处理80000个数据所花的时间为:19处理160000个数据所花的时间为:38
6. 归并排序
6.1 基本介绍 归并排序(MERGE-SORT 是利用归并的思想实现的排序方法该算法采用经典的分治 (divide-and-conquer) 策略 (分治法将问题分(divide)成一些小的问题然后递归求解而治(conquer)的阶段则将分的阶段得到的各答案“修补“在起即分而治之)
6.2 基本思想 图6 归并排序思想示意图 可以看到这种结构很像一棵完全二叉树本节的归并排序我们采用递归去实现(也可采用迭代的方式去实现)分阶段可以理解为就是递归拆分子序列的过程。 图7 归并排序思想示意图(二) 治阶段是将两个有序地子序列合并成一个有序序列。图7是治阶段的最后一次合并实现步骤如图7所示。
6.3 应用实例
原谅我去看了黑马的数据机构与算法才看懂的
6.3.1 归并排序—自顶向下
由于使用了递归 称之为自顶向下。
黑马程序如下
package com.atguigu.sort;import java.util.Arrays;/*** author 小小低头哥* version 1.0* 归并排序*/
public class MergeSort2 {public static void main(String[] args) {int[] a {9, 3, 7, 2, 8, 5, 1, 4};sort(a);System.out.println(Arrays.toString(a));}public static void sort(int[] a1) {int[] a2 new int[a1.length];split(a1, 0, a1.length - 1, a2);}public static void split(int[] a1, int left, int right, int[] a2) {int[] array Arrays.copyOfRange(a1, left, right 1);
// System.out.print(Arrays.toString(array));//2. 治if (left right) { //此时只有一个数了return; //递归结束}//1.分// 无符号右移 逻辑右移// 算数右移int m (left right) 1;split(a1, left, m, a2);split(a1, m 1, right, a2);//左右递归结束//3.合 走到这一步 其实就说明其中有一项左右递归结束了//从后往前 从左往右 按顺序写出来应该是array [9 3] m 0 [7 2] m 0 [9 3 7 2] m 1// [8 5] m 0 [1 4] m 0 [8 5 1 4] m 1merge(a1, left, m, m 1, right, a2);System.arraycopy(a2, left, a1, left, right - left 1);//则返回后a1依次为[3 9 ...] [3 9 2 7...] [2 3 7 9...] [2 3 7 9 5 8...]//[2 3 7 9 5 8 1 4...] [2 3 7 9 1 4 5 8] [1, 2, 3, 4, 5, 7, 8, 9]}/*** 将a1有序的两部分 进行排序后合并* 从小到大按顺序将数放在a2数组的i到(ijEnd-jiEnd-i)位置** param a1 原始数组* param i 第一个有序数组的开头* param iEnd 第一个有序数组的结尾* param j 第二个有序数组的开头* param jEnd 第二个有序数组的结尾* param a2 临时数组*/public static void merge(int[] a1, int i, int iEnd, int j, int jEnd, int[] a2) {int k i;while (i iEnd j jEnd) { //每一次循环都将最小数放在a2[k]位置 直到某一个数组全部放置完毕if (a1[i] a1[j]) {a2[k] a1[i];i;} else {a2[k] a1[j];j;}k;}if (i iEnd) { //如果第一个有序数组放置完毕 那肯定第二个有序数组没有放置完毕//从a1第j个开始起数jEnd - j 1个数 将这些数依次放在放在a2第k个数的后面System.arraycopy(a1, j, a2, k, jEnd - j 1); //因为是顺序的数组 所以直接把剩下的数接在a2的后面}if (j jEnd) { //如果第二个有序数组放置完毕 那肯定第一个有序数组没有放置完毕System.arraycopy(a1, i, a2, k, iEnd - i 1);}}
}6.3.2 归并排序—自下而上
黑马程序如下 public static void sort(int[] a1) {int n a1.length;int[] a2 new int[n];//i 代表半个区间的宽度 不同大循环对应的宽度区间不同 每次宽度都会变大两倍for (int i 1; i n; i * 2) {//[left,right] 分别代表待合并区间的左右边界//分别合并宽度为2*i的不同区间中数for (int left 0; left n; left 2 * i) {//如果合并的数据长度不等 比如a1长度为9 当合并最后两个时 左边为8 右边为1 则会出现left 2 * i - 1 大于 n-1的情况//但是实际此时就是右边界就是n - 1int right Math.min(left 2 * i - 1, n - 1);//不可以写成m (left right) / 2//如果合并的数据长度不等 比如a1长度为9 当合并最后两个时 左边为8 右边为1//此时left0 right8 则m (left right) / 24//但实际上应该是m08-17 即左边界指向第一个有序数组的边界 m1指向第二有序数组的开头//m在merge中的本质就是第一个有序数组的边界 m1指向第二有序数组的开头//且m可能会超过数组长度 比如当a1长度为9 i4 即区间宽度为8时此时有两个有序数组//一个是左边的八个 一个是右边的一个//如果在判断第二个有序数组m的时候还是这样判断 那么由于此时只有一个数字 且排序好的//此时m n-1int m Math.min(left i - 1, n - 1);
// System.out.printf(宽度为 %d [%d,%d]\n,2*i,left,right);merge(a1, left, m, m 1, right, a2);System.arraycopy(a2, left, a1, left, right - left 1);}}} 图8 自下而上示意图 自下而上方式比如图8中所示则
第一个大循环中每个区间有2个元素宽度为2半区间长为1共4个区间将每个区间的前后半空间进行顺序合并第二个大循环中每个区间有4个元素宽度为4半区间长为2共个2区间[0 3] [4 7]将每个区间的前后半空间进行顺序合并第三个大循环中每个区间有8个元素宽度为8半区间长为4共1个区间[0 7]将每个区间前后半空间进行顺序合并
6.3.3 归并排序插入排序 此方法可以在前面两种方法的基础上提高运行速度。经验表明归并排序适合数据量比较大的排序运算插入排序适合数据量比较小的排序算法且越有序越好
黑马程序如下
public static void split(int[] a1, int left, int right, int[] a2) {int[] array Arrays.copyOfRange(a1, left, right 1);//2. 治if(right - left 32){ //当数据量小于32时就认为分结束了 此时采用插入排序将数据治起来insertion(a1,left,right); //插入排序return;}//1.分// 无符号右移 逻辑右移// 算数右移int m (left right) 1;split(a1, left, m, a2);split(a1, m 1, right, a2);// [8 5] m 0 [1 4] m 0 [8 5 1 4] m 1merge(a1, left, m, m 1, right, a2);System.arraycopy(a2, left, a1, left, right - left 1);}private static void insertion(int[] a1, int left, int right) {for (int low left 1; low right; low) {int t a1[low] ;int i low - 1;//自右向左插入位置 如果比待插入元素大 则不断右移 空出出入位置while (i left t a1[i]){a1[i 1] a1[i];i--;}//找到插入位置if(i ! low -1){a1[i 1] t;}}
}相比于自顶向下的归并排序而言在治的时候不是到1才返回而是直接数据量小于32的时候使用插入排序进行排序后再返回。妙哉
6.4 归并排序时间复杂度测试
三种结果分别如下
自顶向下: 处理80000个数据所花的时间为:23处理160000个数据所花的时间为:36 自下而上 处理80000个数据所花的时间为:24处理160000个数据所花的时间为:37 归并插入 处理80000个数据所花的时间为:15处理160000个数据所花的时间为:32
由结果可知确实加入插入后速度快了许多
7 基数排序
7.1 基本介绍
基数排序(radix sort属于“分配式排序”(distribution sort)又称“桶子法”(bucket sort或bin sort顾名思义它是通过键值的各个位的值将要排序的元素分配至某些“桶”中达到排序的作用基数排序法是属于稳定性的排序基数排序法的是效率高的稳定性排序法基数排序(Radix Sort)是桶排序的扩展基数排序是1887年赫尔曼·何乐礼发明的。它是这样实现的:将整数按位数切割成不同的数字然后按每个位数分别比较。
7.2 基本思想
将所有待比较数值统一为同样的数位长度数位较短的数前面补零。然后从最低位开始依次进行一次排序。这样从最低位排序一直到最高位排序成以后,数列就变成一个有序序列。这样说明比较难理解下面我们看一个图文解释理解基数排序的步骤。 图9 第一轮排序示意图 图10 第二轮排序示意图 图11 第三轮排序示意图 最后第三轮取出来的数据就是顺序排序的 我的理解:
其实还挺好理解的。从底位起排序其实就是先将位数底的数先排好序因为位数相同数越小的会排在越前面。比如53,14。因为14的十位数小于53的十位数所以14会放在53的前面。就算把53假设为13虽然十位相同但是由于低位早已做过判断13的3是小于14的4所以13早已排在14前面。如果十位不比14大那么就一直在前面和实际判断相同。注意此时个位数都会放在第0个桶中按照个位数排序的顺序再次被出去。并且此时百位数(千位数…)都已经按照十位大小又重新排好序了(之前按个位排好序现在用十位排序覆盖了。也符合正常判断)等待百位(千位)判断的逆袭。也就是每一次排序(第n次)会把n位数及小于n位数的数都排好序n1位数以上的就按照n位数的大小去判断等待n1位的逆袭。
至于能不能按照从高位到地位的判断感觉可行。但是确定最大数的位数有点麻烦过程也麻烦一点对于相同高位但次高位不同的数不友好需要额外判断没从小到大方便。
7.3 应用实例
韩老师代码如下
package com.atguigu.sort;import java.util.Arrays;/*** author 小小低头哥* version 1.0* 基数排序*/
public class RadixSort {public static void main(String[] args) {int[] arr {53, 3, 542, 748, 14, 214,46,13,46,1,34,13,46,1,3};radixSort(arr);System.out.println(arr Arrays.toString(arr));}//基数排序方法public static void radixSort(int[] arr) {//1. 得到数组中最大的数的位数int max arr[0]; //假设第一个数就是最大数for (int i 1; i arr.length; i) {if (max arr[i]) {max arr[i];}}//得到最大数是几位数int maxLength (max ).length();//定义一个二维数组 表示10个桶 每个桶都是一个一维数组//说明//1. 二维数组包含10个一维数组//2. 为了防止在放入数的时候 数据溢出则每个一维数组(桶) 大小定为arr.length//3. 明确基数排序是使用空间换时间的经典算法int[][] bucket new int[10][arr.length];//为了记录每个桶中 实际存放了多少个数据 定义一个一维数组记录各个桶每次放入的数据个数int[] bucketElementCounts new int[10];for (int i 0; i maxLength; i) { //从低位循环到最高位//放置元素for (int j 0; j arr.length; j) {int digitOfElement arr[j] / (int) Math.pow(10, i) % 10; //得到每个为的数//由digitOfElement将arr[j]放入到对应数组位置bucket[digitOfElement][bucketElementCounts[digitOfElement]] arr[j];}int index 0; //索引//按顺序取出函数for (int j 0; j 10; j) {//循环遍历每一个桶//循环遍历每个桶中的元素for (int k 0; k bucketElementCounts[j]; k) {arr[index] bucket[j][k];}bucketElementCounts[j] 0; //取完元素后置零 为下一次循环做准备}}}
}这份代码不能判断负数会报错。可以听弹幕的先将所有数加上最小值的模排完序后再减去最小值的模。
7.4 时间复杂度测试
结果如下:
处理80000个数据所花的时间为:49处理160000个数据所花的时间为:80
对比一下前两次排序速度还是算慢的原因是基数排序适合大数据排序。思路和实现确实比较简单。
8.常用排序算法总结和对比 图12 常用排序算法对比 图13 相关术语解释
