排序算法(Sort Algorithm),排序是将一组数据,依指定的顺序进行排序的过程
排序的分类:
常见的排序算法分类
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-thpn5xWQ-1618541456962)(C:\Users\dongwei\AppData\Roaming\Typora\typora-user-images\image-20210325084358307.png)]
度量一个程序(算法)执行时间的两种方法
这种方法可行,但是有两个问题:一是要想对设计的算法的运行能力进行评价,需要实际运行该程序;二是所得时间的统计量依赖于计算机的硬件,软件等环境因素,这种方式,要在同一台计算机的相同状态下运行,才能比较哪个算法速度更快
通过分析某个算法的时间复杂度来判断哪个算法更优。
时间频度
时间频度:一个算法花费的时间与算法中语句的执行次数成正比,哪个算法在语句执行的次数多,它花费的时间就多,**一个算法中的语句执行次数称为语句频度或时间频度。**计为T(n)。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Mhgat7rL-1618541456966)(C:\Users\dongwei\AppData\Roaming\Typora\typora-user-images\image-20210325084440288.png)]
结论
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-hANpvmK2-1618541456970)(C:\Users\dongwei\AppData\Roaming\Typora\typora-user-images\image-20210325084551920.png)]
结论
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-O5RUvlvy-1618541456974)(C:\Users\dongwei\AppData\Roaming\Typora\typora-user-images\image-20210325084622475.png)]
结论
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-YrfMhmPq-1618541456976)(C:\Users\dongwei\AppData\Roaming\Typora\typora-user-images\image-20210325090021138.png)]
常数阶O(1)
int i = 1; int j = 2; ++i; j++; int m = i + j;
无论代码执行了多少行,只要没有循环体等复杂结构,那么这个代码的时间复杂度就是O(1),上述代码在执行的时候,它消耗的时间不随着某个变量的增长而增长,那么无论这类代码有多长。即使几十万都可以用O(1)来表示它的时间复杂度。
对数阶
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-SFmTLaMG-1618541456978)(C:\Users\dongwei\AppData\Roaming\Typora\typora-user-images\image-20210325090949315.png)]
线性阶O(n)
for (i = 1;i <= n; ++i){ j = i; j++; }
这段代码,for循环里面的代码块会执行n遍,因此它消耗的时间是随着n的变化而变化的,因此这类代码都可以用O(n)来表示它的时间复杂度。
线性对数阶
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-EK3D4zKJ-1618541456980)(C:\Users\dongwei\AppData\Roaming\Typora\typora-user-images\image-20210325092301879.png)]
平方阶O(n^2)
for (x = 1;i <= n;x++){ for (i = 1;i <= n;i++){ j = i; j++; } }
平方阶O(n2)就更容易理解了,如果把O(n)的代码再嵌套循环一遍,它的时间复杂度就是O(n2),这段代码其实就是嵌套了2层n循环,如果将其中的一层循环由n改为m,那么它的时间复杂度就变成了O(m*n)。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-CsqynZtf-1618541456982)(C:\Users\dongwei\AppData\Roaming\Typora\typora-user-images\image-20210325093406839.png)]
冒泡排序(Bubble Sorting)的基本思想是:通过对待排序序列从前向后(从小标较小的元素开始),依次比较相邻元素的值,若发现逆序则交换,使值较大的元素逐渐从前向移向后部,就象水底下的气泡一样逐渐向上冒。
因为排序的过程中,各个元素不断接近自己的位置,如果一趟比较下来没有进行过交换,就说明序列有序,因此需要在排序的过程中设置一个标志flag判断元素是否进行过交换。
思路
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-SpohdlX0-1618541456984)(C:\Users\dongwei\AppData\Roaming\Typora\typora-user-images\image-20210325101055268.png)]
我们举例一个具体的案例来说明冒泡法,将五个无序的数:3 9 -1 10 -2,使用冒泡排序法将其排成一个从小到大的有序数列
基础代码
public class BubbleSort { public static void main(String[] args) { int arr[] = {3, 9, -1, 10, -2}; //第一趟排序,就是将最大的数排在最后 int temp = 0;//临时变量 for (int i = 0; i < arr.length - 1; i++) { for (int j = 0; j < arr.length - 1 - i; j++) { //如果前面的数比后面的数大就交换 if (arr[j] > arr[j + 1]) { temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } System.out.println("第"+(i+1)+"趟排序后的数组~~~"); System.out.println(Arrays.toString(arr)); } /* //第二趟排序,就是将第二大的数排在倒数第二位 for (int j = 0; j < arr.length - 2; j++) { //如果前面的数比后面的数大就交换 if (arr[j] > arr[j + 1]) { temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } System.out.println("第二趟排序后的数组~~~"); System.out.println(Arrays.toString(arr)); //第三趟排序,就是将第二大的数排在倒数第三位 for (int j = 0; j < arr.length - 3; j++) { //如果前面的数比后面的数大就交换 if (arr[j] > arr[j + 1]) { temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } System.out.println("第三趟排序后的数组~~~"); System.out.println(Arrays.toString(arr)); //第四趟排序,就是将第二大的数排在倒数第三位 for (int j = 0; j < arr.length - 4; j++) { //如果前面的数比后面的数大就交换 if (arr[j] > arr[j + 1]) { temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } System.out.println("第四趟排序后的数组~~~"); System.out.println(Arrays.toString(arr)); */ } }
结果
第1趟排序后的数组~~~ [3, -1, 9, -2, 10] 第2趟排序后的数组~~~ [-1, 3, -2, 9, 10] 第3趟排序后的数组~~~ [-1, -2, 3, 9, 10] 第4趟排序后的数组~~~ [-2, -1, 3, 9, 10]
优化:如果我们发现在某趟排序中,没有发生一次交换,可以提前结束冒泡排序,这个就是优化。
public class BubbleSort { public static void main(String[] args) { // int arr[] = {3, 9, -1, 10, 20}; // System.out.println("排序前~~~"); // System.out.println(Arrays.toString(arr)); //测试一下冒泡排序的速度O(n^2),给80000个数据,测试 //创建要给80000个随机的数组 int[] arr = new int[80000]; for (int i = 0;i < 80000;i++){ arr[i] = (int)(Math.random() * 800000); //生成一个【0,800000)数 } Date date1 = new Date(); SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss"); String date1Str = simpleDateFormat.format(date1); System.out.println("排序前的时间:"+date1Str); //测试冒泡排序 bubbleSort(arr); Date date2 = new Date(); String date2Str = simpleDateFormat.format(date2); System.out.println("排序后的时间:"+date2Str); // System.out.println("测试后~~~"); // System.out.println(Arrays.toString(arr)); /* //第二趟排序,就是将第二大的数排在倒数第二位 for (int j = 0; j < arr.length - 2; j++) { //如果前面的数比后面的数大就交换 if (arr[j] > arr[j + 1]) { temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } System.out.println("第二趟排序后的数组~~~"); System.out.println(Arrays.toString(arr)); //第三趟排序,就是将第二大的数排在倒数第三位 for (int j = 0; j < arr.length - 3; j++) { //如果前面的数比后面的数大就交换 if (arr[j] > arr[j + 1]) { temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } System.out.println("第三趟排序后的数组~~~"); System.out.println(Arrays.toString(arr)); //第四趟排序,就是将第二大的数排在倒数第三位 for (int j = 0; j < arr.length - 4; j++) { //如果前面的数比后面的数大就交换 if (arr[j] > arr[j + 1]) { temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } System.out.println("第四趟排序后的数组~~~"); System.out.println(Arrays.toString(arr)); */ } public static void bubbleSort(int[] arr) { //第一趟排序,就是将最大的数排在最后 int temp = 0;//临时变量 boolean flag = false; for (int i = 0; i < arr.length - 1; i++) { for (int j = 0; j < arr.length - 1 - i; j++) { //如果前面的数比后面的数大就交换 if (arr[j] > arr[j + 1]) { flag = true; temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } // System.out.println("第" + (i + 1) + "趟排序后的数组~~~"); // System.out.println(Arrays.toString(arr)); if (!flag) { //在一趟排序中,一次交换没有发生过 break; } else { flag = false;//重置flag!!!进行下次判断 } } } }
结果
排序前的时间:2021-03-25 12:56:23 排序后的时间:2021-03-25 12:56:36
选择排序也属于内部排序法,是从欲排序的数据中,按指定的规则选出某一元素,再次依规定交换位置后达到排序的目的。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-7tMutooi-1618541456986)(C:\Users\dongwei\AppData\Roaming\Typora\typora-user-images\image-20210325130810350.png)]
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-d8di3ZK1-1618541456988)(C:\Users\dongwei\AppData\Roaming\Typora\typora-user-images\image-20210325131357981.png)]
代码实现
public class SelectSort { public static void main(String[] args) { int[] arr = {101, 34, 119, 1,-1,90,123}; System.out.println("排序前~~~"); System.out.println(Arrays.toString(arr)); System.out.println("排序后~~~"); selectSort(arr); System.out.println(Arrays.toString(arr)); } //选择排序 public static void selectSort(int[] arr) { //在推导的过程中,我们找到了规律,因此我们可以使用for来解决 for (int i = 0; i < arr.length - 1; i++) { int minIndex = i; int min = arr[i]; for (int j = i + 1; j < arr.length; j++) { if (min > arr[j]) { //说明假定的最小值,并不是最小值 min = arr[j]; //重置min minIndex = j; //重置minIndex } } //将最小值,放在arr[0],即交换 if (minIndex != i) { arr[minIndex] = arr[i]; arr[i] = min; } // System.out.println("第"+ (i+1) + "一轮后"); // System.out.println(Arrays.toString(arr)); } /* //第一轮 int minIndex = 0; int min = arr[0]; for (int j = 0 + 1; j < arr.length; j++) { if (min > arr[j]) { //说明假定的最小值,并不是最小值 min = arr[j]; //重置min minIndex = j; //重置minIndex } } //将最小值,放在arr[0],即交换 if (minIndex != 0) { arr[minIndex] = arr[0]; arr[0] = min; } System.out.println("第一轮后"); System.out.println(Arrays.toString(arr)); //第二轮 minIndex = 1; min = arr[1]; for (int j = 1 + 1; j < arr.length; j++) { if (min > arr[j]) { //说明假定的最小值,并不是最小值 min = arr[j]; //重置min minIndex = j; //重置minIndex } } //将最小值,放在arr[0],即交换 if (minIndex != 1) { arr[minIndex] = arr[1]; arr[1] = min; } System.out.println("第二轮后"); System.out.println(Arrays.toString(arr)); //第三轮 minIndex = 2; min = arr[2]; for (int j = 2 + 1; j < arr.length; j++) { if (min > arr[j]) { //说明假定的最小值,并不是最小值 min = arr[j]; //重置min minIndex = j; //重置minIndex } } //将最小值,放在arr[0],即交换 if (minIndex != 2) { arr[minIndex] = arr[2]; arr[2] = min; } System.out.println("第二轮后"); System.out.println(Arrays.toString(arr)); */ } }
结果
排序前~~~ [101, 34, 119, 1, -1, 90, 123] 排序后~~~ [-1, 1, 34, 90, 101, 119, 123]
运行时间代码测试
// int[] arr = {101, 34, 119, 1,-1,90,123}; int[] arr = new int[80000]; for (int i = 0; i < 80000; i++) { arr[i] = (int) (Math.random() * 800000); //生成一个【0,800000)数 } System.out.println("排序前~~~"); // System.out.println(Arrays.toString(arr)); Date date1 = new Date(); SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss"); String date1Str = simpleDateFormat.format(date1); System.out.println("排序前的时间:"+date1Str); System.out.println("排序后~~~"); selectSort(arr); Date date2 = new Date(); String date2Str = simpleDateFormat.format(date2); System.out.println("排序后的时间:"+date2Str);
结果
排序前~~~ 排序前的时间:2021-03-25 14:56:24 排序后~~~ 排序后的时间:2021-03-25 14:56:28
插入式排序属于内部排序法,是对于欲排序的元素以插入的方式寻求该元素的适当位置,以达到排序的目的。
插入排序(Inserting Sorting)的基本思想是:把n个待排序的元素看成为一个有序表和一个无序表,开始时有序表中只含有一个元素,无需表中包含有n-1个元素,排序过程中每次从无序表中取出第一个元素,把它的排序码依次与有序表元素的排序码进行比较,将它插入到有序表中的适当位置,使之成为新的有序表。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-B0TjIwjs-1618541456990)(C:\Users\dongwei\AppData\Roaming\Typora\typora-user-images\image-20210325151652653.png)]
代码实现
public class InsertSort { public static void main(String[] args) { // int[] arr = {101, 34, 119, 1}; int[] arr = new int[80000]; for (int i = 0; i < 80000; i++) { arr[i] = (int) (Math.random() * 800000); //生成一个【0,800000)数 } Date date1 = new Date(); SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss"); String date1Str = simpleDateFormat.format(date1); System.out.println("排序前的时间:" + date1Str); //测试插入排序 insertSort(arr); Date date2 = new Date(); String date2Str = simpleDateFormat.format(date2); System.out.println("排序后的时间:" + date2Str); } //插入排序 public static void insertSort(int[] arr) { for (int i = 1; i < arr.length; i++) { int insertVal = arr[i]; int insertIndex = i - 1; //即arr[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; } // System.out.println("第" + i + "轮插入"); // System.out.println(Arrays.toString(arr)); } /* //使用逐步推导的方式来讲解 //第一轮 //定义待插入的数 int insertVal = arr[1]; int insertIndex = 1 -1; //即arr[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; arr[insertIndex +1] = insertVal; System.out.println("第1轮插入"); System.out.println(Arrays.toString(arr)); //第二轮 //定义待插入的数 insertVal = arr[2]; insertIndex = 2 -1; //即arr[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; arr[insertIndex +1] = insertVal; System.out.println("第2轮插入"); System.out.println(Arrays.toString(arr)); //第三轮 //定义待插入的数 insertVal = arr[3]; insertIndex = 3 - 1; //即arr[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; arr[insertIndex +1] = insertVal; System.out.println("第3轮插入"); System.out.println(Arrays.toString(arr)); */ } }
运行结果
排序前的时间:2021-03-29 11:08:21 排序后的时间:2021-03-29 11:08:23
针对插入排序中存在的问题有:
当需要插入的数是较小的数时,后移的次数明显增多,对效率有影响
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-90ONTyHD-1618541456993)(C:\Users\dongwei\AppData\Roaming\Typora\typora-user-images\image-20210329111648973.png)]
希尔排序算法的介绍
希尔排序是1959年提出的一种排序算法,希尔排序也是插入排序,它是简单的排序经过改进之后的一个更高效的版本,也称为缩小增量排序。
希尔排序的基本思想:
希尔排序是把记录按小标的一定增量分组,对每组使用直接插入排序算法排序,随着增量的减少,每组包含的关键词越来越多,当增量减少至1时,整个文件被分成一组,算法终止。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-3k0jJogO-1618541456996)(C:\Users\dongwei\AppData\Roaming\Typora\typora-user-images\image-20210329112211305.png)]
经过上面的宏观调控,整个数组的有序化程度成果惊人,此时仅仅需要对以上数列简单微调,无需大量移动就可以完成整个数组的排序。
交换法实现
public class ShellSort { public static void main(String[] args) { int[] arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0}; shellSort(arr); } //使用逐步推导的方式来编写希尔排序 public static void shellSort(int[] arr) { int temp = 0; int count = 0; //根据前面的逐步分析,使用循环处理 //希尔排序时,对有序序列在插入时采用交换法 for (int gap = arr.length / 2; gap > 0; gap /= 2) { for (int i = gap; i < arr.length; i++) { //遍历各组中所有的元素(共gap组) for (int j = i - gap; j >= 0; j -= gap) { //如果当前元素大于加上步长后的那个元素,说明交换 if (arr[j] > arr[j + gap]) { temp = arr[j]; arr[j] = arr[j + gap]; arr[j + gap] = temp; } } } System.out.println("希尔排序" + (++count) + "轮=" + Arrays.toString(arr)); } /* int temp = 0; //希尔排序的第一轮排序 //因为是第一轮排序,是将十个数据分成五组 for (int i = 5; i < arr.length; i++) { //遍历各组中所有的元素(共5组,每组有2个元素),步长为5 for (int j = i - 5; j >= 0; j -= 5) { //如果当前元素大于加上步长后的那个元素,说明交换 if (arr[j] > arr[j + 5]) { temp = arr[j]; arr[j] = arr[j + 5]; arr[j + 5] = temp; } } } System.out.println("希尔排序的1轮后=" + Arrays.toString(arr)); //因为是第二轮排序,是将十个数据分成五组 for (int i = 2; i < arr.length; i++) { //遍历各组中所有的元素(共2组,每组有5个元素),步长为 2 for (int j = i - 2; j >= 0; j -= 2) { //如果当前元素大于加上步长后的那个元素,说明交换 if (arr[j] > arr[j + 2]) { temp = arr[j]; arr[j] = arr[j + 2]; arr[j + 2] = temp; } } } System.out.println("希尔排序的2轮后=" + Arrays.toString(arr)); //因为是第三轮排序,是将十个数据分成五组 for (int i = 1; i < arr.length; i++) { //遍历各组中所有的元素(共2组,每组有5个元素),步长为 2 for (int j = i - 1; j >= 0; j -= 1) { //如果当前元素大于加上步长后的那个元素,说明交换 if (arr[j] > arr[j + 1]) { temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } System.out.println("希尔排序的3轮后=" + Arrays.toString(arr)); */ } }
运行的结果显示
希尔排序1轮=[3, 5, 1, 6, 0, 8, 9, 4, 7, 2] 希尔排序2轮=[0, 2, 1, 4, 3, 5, 7, 6, 9, 8] 希尔排序3轮=[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
效率的显示
排序前的时间:2021-03-29 14:00:10 排序后的时间:2021-03-29 14:00:17
移位式的算法实现
public static void shellSort2(int[] arr) { //增量gap,并逐步的缩小增量 for (int gap = arr.length / 2; gap > 0; gap /= 2) { //从第gap个元素,逐步对其所在的组进行直接插入排序 for (int i = gap; i < arr.length; i++) { int j = i; int temp = arr[j]; if (arr[j] < arr[j - gap]) { while (j - gap >= 0 && temp < arr[j - gap]) { //移动 arr[j] = arr[j - gap]; j -= gap; } //当退出while之后,就给temp找到插入的位置 arr[j] = temp; } } } }
算法效率的计算
排序前的时间:2021-03-29 14:31:00 排序后的时间:2021-03-29 14:31:00
*这也太牛逼了吧~~~~~*~
快速排序算法(Quicksort)是对冒泡排序的一种改进,基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另一部分的所有数据要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序国恒可以递归,以此达到整个数据都变成有序序列。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-0F2mm65h-1618541456998)(C:\Users\dongwei\AppData\Roaming\Typora\typora-user-images\image-20210329144131037.png)]
代码的实现
public class QuickSort { public static void main(String[] args) { // int[] arr = {-9, 78, 0, 23, -567, 70}; // quickSort(arr,0,arr.length - 1); // System.out.println(Arrays.toString(arr)); int[] arr = new int[80000]; for (int i = 0;i < 80000;i++){ arr[i] = (int)(Math.random() * 800000); //生成一个【0,800000)数 } Date date1 = new Date(); SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss"); String date1Str = simpleDateFormat.format(date1); System.out.println("排序前的时间:"+date1Str); quickSort(arr,0,arr.length - 1); Date date2 = new Date(); String date2Str = simpleDateFormat.format(date2); System.out.println("排序后的时间:"+date2Str); } /* public static void quickSort(int[] arr, int left, int right) { int l = left; int r = right; int temp = 0;//作为交换时使用 //pivot 中轴值 int pivot = arr[(left + right) / 2]; //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) { l -= 1; } //如果交换完毕,发现这个arr[l] == pivot值相等,l++,后移 if (arr[r] == pivot) { r += 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); } } */ private static void quickSort(int[] arr, int left, int right) { if (left < right) { int partitionIndex = partition(arr, left, right); quickSort(arr, left, partitionIndex - 1); quickSort(arr, partitionIndex + 1, right); } } private static int partition(int[] arr, int left, int right) { int pivot = arr[left]; //终止while循环以后left和right一定相等的 while (left < right) { while (left < right && arr[right] >= pivot) { --right; } arr[left] = arr[right]; while (left < right && arr[left] <= pivot) { ++left; } arr[right] = arr[left]; } arr[left] = pivot; //right可以改为left return left; } }
上面是有两种实现代码
归并排序(MERGE-SORT)是利用归并的思想实现的排序方法,该算法采用经典的分治(devide-and-conquer)策略(分治法将问题分(devide)成一些小的问题,然后再递归求解,而治(conquer)的阶段则将分的阶段得到各答案修补在一起,即分而治之。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-DHo26srn-1618541457000)(C:\Users\dongwei\AppData\Roaming\Typora\typora-user-images\image-20210330090336661.png)]
**说明:**可以看到这种结构很像一棵完全二叉树,本文的归并排序我们采用递归去实现,(也可以使用迭代的方式去实现)。分阶段可以理解为就是递归拆分子序列的过程。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-SBe6fs6w-1618541457002)(C:\Users\dongwei\AppData\Roaming\Typora\typora-user-images\image-20210330091200075.png)]
public class MergeSort { public static void main(String[] args) { int[] arr = {8, 4, 5, 7, 1, 3, 6, 2}; int[] temp = new int[arr.length]; mergedSort(arr, 0, arr.length - 1, temp); System.out.println(Arrays.toString(arr)); } //分加合并的算法 public static void mergedSort(int[] arr, int left, int right, int[] temp) { if (left < right) { int mid = (left + right) / 2; //向左递归进行分解 mergedSort(arr, left, mid, temp); //向右递归进行分解 mergedSort(arr, mid + 1, right, temp); //合并 merge(arr, left, mid, right, temp); } } //合并的方法 public static void merge(int[] arr, int left, int mid, int right, int[] temp) { System.out.println("~~~~"); int i = left; //初始化i,左边有序序列的初始索引 int j = mid + 1; //初始化j,右边有序序列的初始索引 int t = 0; //指向temp数组的当前索引 //(一) //先把左右两边(有序)的数组按照规则填充到temp数组 //直到左右两边的有序序列,有一边处理完毕 while (i <= mid && j <= right) { if (arr[i] <= arr[j]) { temp[t] = arr[i]; t += 1; i += 1; } else { temp[t] = arr[j]; t += 1; j += 1; } } //(二) //把有剩余数据的一边的数据依次全部填充到temp while (i <= mid) { //左边的有序序列还有剩余的元素,就全部填充到temp temp[t] = arr[i]; t += 1; i += 1; } while (j <= right) { //右边的有序序列还有剩余的元素,就全部填充到temp temp[t] = arr[j]; t += 1; j += 1; } //(三) //将temp数组的元素拷贝到arr //注意,并不是每次都拷贝所有 t = 0; int tempLeft = left; while (tempLeft <= right) { arr[tempLeft] = temp[t]; t += 1; tempLeft += 1; } } }
运行的结果
~~~~ ~~~~ ~~~~ ~~~~ ~~~~ ~~~~ ~~~~ [1, 2, 3, 4, 5, 6, 7, 8]
合并的次数就是n-1
基数排序的基本思想
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-kKvcVXON-1618541457004)(C:\Users\dongwei\AppData\Roaming\Typora\typora-user-images\image-20210330110131298.png)]
第二轮之后是十位
第三轮是百位
轮数是按照最高位数来判断的
public class RadixSort { public static void main(String[] args) { int[] arr = {53, 3, 542, 748, 14, 214}; radixSort(arr); } //基数排序的方法 public static void radixSort(int[] arr) { //根据前面的推导过程,我们可以得到最终的基数排序代码 //得到数组中最大的数的位数 int max = arr[0]; for (int i = 0; i < arr.length; i++) { if (arr[i] > max) { max = arr[i]; } } //得到最大的数是几位数 int maxLength = (max + "").length(); //定义一个二维数组,表示10个桶就是一个一维数组 //说明 //1. 二维数组包含十个一维数组 //2. 为了防止在放入数的时候,数据溢出,则每一个一位数组(桶),大小定义为arr.length //3. 这是一种典型的空间换时间的算法 int[][] bucket = new int[10][arr.length]; //为了记录每个桶中,实际存放了多少个数据,定义一个一维数组来记录各个桶的每次放入的数据个数 int[] bucketElementCounts = new int[10]; //使用循环处理代码 for (int i = 0, n = 1; i < maxLength; i++, n *= 10) { for (int j = 0; j < arr.length; j++) { int digitOfElement = arr[j] /n % 10; //放入到对用的桶中 bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j]; bucketElementCounts[digitOfElement]++; } //按照这个桶的顺序(一维数组的下标依次取出数据,放入原来的数组) int index = 0; //遍历每一个桶,并将桶中的数据放入到原数组 for (int k = 0; k < bucketElementCounts.length; k++) { //如果桶中有数据才放入到原数组 if (bucketElementCounts[k] != 0) { for (int l = 0; l < bucketElementCounts[k]; l++) { arr[index] = bucket[k][l]; index++; } } //第一轮处理结束后,需要将各个bucketElemtCounts[k] = 0; bucketElementCounts[k] = 0; } System.out.println("第"+(i+1)+"轮,对个位数的排序处理 arr = " + Arrays.toString(arr)); } /* //第一轮 for (int j = 0;j < arr.length;j++){ //取出每个元素个位数的值 int digitOfElement = arr[j] % 10; //放入到对用的桶中 bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j]; bucketElementCounts[digitOfElement]++; } //按照这个桶的顺序(一维数组的下标依次取出数据,放入原来的数组) int index = 0; //遍历每一个桶,并将桶中的数据放入到原数组 for (int k = 0;k < bucketElementCounts.length; k++){ //如果桶中有数据才放入到原数组 if (bucketElementCounts[k] != 0){ for (int l =0;l < bucketElementCounts[k];l++){ arr[index] = bucket[k][l]; index++; } } //第一轮处理结束后,需要将各个bucketElemtCounts[k] = 0; bucketElementCounts[k] = 0; } System.out.println("第1轮,对个位数的排序处理 arr = "+ Arrays.toString(arr)); //=============================================================================== //第二轮 for (int j = 0;j < arr.length;j++){ //取出每个元素个位数的值 int digitOfElement = arr[j] /10 % 10; //放入到对用的桶中 bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j]; bucketElementCounts[digitOfElement]++; } //按照这个桶的顺序(一维数组的下标依次取出数据,放入原来的数组) index = 0; //遍历每一个桶,并将桶中的数据放入到原数组 for (int k = 0;k < bucketElementCounts.length; k++){ //如果桶中有数据才放入到原数组 if (bucketElementCounts[k] != 0){ for (int l =0;l < bucketElementCounts[k];l++){ arr[index] = bucket[k][l]; index++; } } bucketElementCounts[k] = 0; } System.out.println("第2轮,对十位数的排序处理 arr = "+ Arrays.toString(arr)); //===================================================================================== //第二轮 for (int j = 0;j < arr.length;j++){ //取出每个元素个位数的值 int digitOfElement = arr[j] /100 % 10; //放入到对用的桶中 bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j]; bucketElementCounts[digitOfElement]++; } //按照这个桶的顺序(一维数组的下标依次取出数据,放入原来的数组) index = 0; //遍历每一个桶,并将桶中的数据放入到原数组 for (int k = 0;k < bucketElementCounts.length; k++){ //如果桶中有数据才放入到原数组 if (bucketElementCounts[k] != 0){ for (int l =0;l < bucketElementCounts[k];l++){ arr[index] = bucket[k][l]; index++; } } bucketElementCounts[k] = 0; } System.out.println("第3轮,对百位数的排序处理 arr = "+ Arrays.toString(arr)); */ } }
结果
第1轮,对个位数的排序处理 arr = [542, 53, 3, 14, 214, 748] 第2轮,对个位数的排序处理 arr = [3, 14, 214, 542, 748, 53] 第3轮,对个位数的排序处理 arr = [3, 14, 53, 214, 542, 748]
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-yyw50cud-1618541457006)(C:\Users\dongwei\AppData\Roaming\Typora\typora-user-images\image-20210330145705820.png)]