-
3-1常用排序练习
1.题目来源
2.排序讲解（有动态图解）
3.冒泡排序
分析
每次进行都把前后两个数值进行比较，这样一轮比较下来，数组最后面的数值就是数组中最大的，下一轮比较该数则不参与比较，一直比较直到最后只剩一个数的时候就得到了一个升序排列的数组。
代码实现
public int[] MySort (int[] arr) { // write code here int length = arr.length,temp = 0; for (int i = 0; i < length; i++) { for (int j = 0; j < length-i-1; j++) { // 如果前一个数比后一个数大，就交换 if (arr[j] > arr[j+1]){ temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } } return arr; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
4.选择排序
分析
每次选择一个最小（或者最大）的数放在数组前面，一直到最后，就得到了一个有序数组
代码
public int[] MySort (int[] arr) { // write code here int length = arr.length,temp = 0; for (int i = 0; i < length-1; i++) { for (int j = i+1; j < length; j++) { // 如果有一个数比待比较数小就交换 if (arr[i] > arr[j]){ temp = arr[j]; arr[j] = arr[i]; arr[i] = temp; } } } return arr; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
像这样又会更加减少排序次数
public int[] MySort (int[] arr) { // write code here int length = arr.length,temp = 0,min = 0; for (int i = 0; i < length-1; i++) { min = i; for (int j = i+1; j < length; j++) { // 找出最小的数 if (arr[min] > arr[j]){ min = j; } } // 将最小的数换到未比较子数列的最前面 temp = arr[min]; arr[min] = arr[i]; arr[i] = temp; } return arr; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
5.插入排序
分析
已当前值为基准，向后找，一但找到一个比当前值小的数就将该数插入到基准值之前（数组中插入一个数就是将插入位之后的值依次向后移动一位，再将插入位赋值为想要插入的数）
代码
public int[] MySort (int[] arr) { // write code here int length = arr.length,temp = 0,min = 0; for (int i = 0; i < length-1; i++) { for (int j = i+1; j < length; j++) { // 找出比当前值小的数，将该数插入到当前值前面 if (arr[i] > arr[j]){ temp = arr[j]; // 这一段整体向后移一位 for (int k = j; k > i ; k--) { arr[k] = arr[k-1]; } arr[i] = temp; } } } return arr; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
6.快速排序
分析
代码
public int[] MySort(int[] arr) { // write code here int length = arr.length; quickSort(arr, 0, length - 1); return arr; } public void quickSort(int arr[], int l, int r) { if (l >= r){ return; } int x = l; int y = r; // 将最左边的值作为基准值 int value = arr[l]; while (l<r){ // 右边的数大于基准值，不做处理，指针左移 while(l < r && arr[r] >= value){ r--; } // 右边的数小于于基准值，交换,注意，第一次交换时左边的值为基准值 if (l<r){ arr[l] = arr[r]; l++; } // 左边的数小于基准值，不做处理，指针右移 while(l < r && arr[l] <= value){ l++; } // 左边的数大于基准值，交换 if (l < r){ arr[r] = arr[l]; r--; } } // System.out.println(l+"----"+r); // 将中间值赋值为基准值 arr[l] = value; print(arr,arr.length,++count); // 左边序列排序 // quickSort(arr,l,r); quickSort(arr,x,l); // 右边序列排序 // quickSort(arr,l+1,r); quickSort(arr,l+1,y); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
总结
- 交换值的时候不需要将两个值交换，因为交换后一定有一个值为基准值，那个基准值最终是要在中间的，所以直接覆盖就好了，如下图
- 由于我们是按照1这样处理的，所以呢必须从右开始比较，如果从左开始比较则会产生错误，至于是什么错误可以自己尝试一下。
- 由于我们的l，r是要随着每一次比较变化的，所以要将l，r的初始值保存下来，以备后面递归调用时使用。
//不保存初始值时这样直接调用，l和r经过一轮比较他们的值相等了，所以调用自身是不能够进入循环的 //左边序列排序 quickSort(arr,l,r); // 右边序列排序 quickSort(arr,l+1,r);- 1
- 2
- 3
- 4
- 5
7.调用函数
正经人谁手写排序代码啊
public int[] MySort (int[] arr) { // write code here Arrays.sort(arr); return arr; }- 1
- 2
- 3
- 4
- 5
- 6
8.堆排序
分析
代码
public int[] MySort(int[] arr) { // write code here heapSort(arr, 0, arr.length - 1); return arr; } public void heapSort(int[] arr, int root, int lastIndex) { if (lastIndex < 1){ return; } // 初始化最大堆，从最后一个子堆开始,如果lastIndex(最后一个下标)为奇数则最后一个子堆有左孩子，反之有右孩子 // 已知左孩子i求父节点：(i-1)/2;已知右孩子i求父节点：(i-2)/2 for (int i = (lastIndex / 2 == 0 ? (lastIndex - 2) / 2 : (lastIndex - 1) / 2); i >= 0; i--) { createMaxHeap(arr, i,lastIndex); } // 对大根堆开始排序 // print(arr, arr.length); int temp = arr[lastIndex]; arr[lastIndex] = arr[root]; arr[root] = temp; // 最后一个值是数组的最大值，已经进入有序序列 heapSort(arr,root,lastIndex-1); } //创建最大子堆 public void createMaxHeap(int[] arr, int root,int lastIndex) { int leftChild = root * 2 + 1; int rightChild = leftChild + 1; int maxIndex = leftChild; // 如果有剩下的无序堆有右孩子就进行左右孩子比较 if (rightChild<=lastIndex && arr[rightChild] > arr[leftChild]) { maxIndex = rightChild; } // 父节点值最大，直接退出 if (arr[maxIndex] < arr[root]) { return; } // 父节点值小于子节点，交换值，使父节点值最大 int temp = arr[maxIndex]; arr[maxIndex] = arr[root]; arr[root] = temp; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
9.归并排序
分析
代码
public int[] MySort(int[] arr) { // write code here mergeSort(arr, 0, arr.length - 1); return arr; } /** * 拆分数组 * * @param arr * @param l * @param r * @return */ public void mergeSort(int[] arr, int l, int r) { if (l >= r) { return; } // 对数组进行拆分 int mid = (l + r) / 2; mergeSort(arr, l, mid); mergeSort(arr, mid + 1, r); // 合并 merge(arr, l, mid, r); } /** * 合并同一数组的两部分（l,mid）(mid+1,r) * @param arr * @param l * @param mid * @param r * @return */ public void merge(int[] arr, int l, int mid, int r) { int length1 = mid, i = l; int length2 = r, j = mid+1; int[] newArr = new int[r-l+1]; int k = 0; while (i <= length1 && j <= length2) { while (i <= length1 && arr[i] <= arr[j]) { newArr[k++] = arr[i++]; } while (j <= length2 && arr[i] >= arr[j]) { newArr[k++] = arr[j++]; } } while (i <= length1) { newArr[k++] = arr[i++]; } while (j <= length2) { newArr[k++] = arr[j++]; } // 改变原数组,改变了前l-r之间的排序 for (int m = 0; m < r-l+1; m++) { arr[l+m] = newArr[m]; } // print(arr,arr.length); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
总结
- 我觉得这个代码实现中最重要的就是辅助数组newArr的使用，最后要将合并得到的子数组的值赋给原数组的那一部分，注意改变哪一段就赋值给哪一段
10.希尔排序（递减增量排序）
分析
希尔排序就是对指定的子序列进行插入排序，子序列由指定间距的元素构成。
这里需要说明一点：为什么对子序列进行插入排序却是交换两个元素呢？因为是对子序列进行插入排序，而比较的又是子序列中两个相邻的元素，所以直接交换元素即可。代码
public int[] MySort(int[] arr) { // write code here int length = arr.length; int h = 1; // 先使间隔最大且h指向子序列的最后一位，值为数组长度 if (h < length/3){ h = length * 3 + 1; } // h>=1时对间隔为h的子序列进行插入排序 while(h>=1){ for (int i = h; i <length ; i++) { for (int j = i; j >=h && arr[j] < arr[j-h]; j-=h) { int temp = arr[j]; arr[j] = arr[j -h]; arr[j-h] = temp; } } h = h/3; } return arr; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
11.计数排序
分析
就是使用一个中间数组，将原数组中的值作为中间数组的下标，值出现的次数作为中间数组的值，赋值完后再将中间数组按照下标顺序将值赋值给原数组，说起来可能有点绕，直接看动图
代码
public int[] MySort(int[] arr) { // write code here // 找出数组中的最大值 int max = -0xfff; for (int i = 0; i < arr.length; i++) { if (max < arr[i]){ max = arr[i]; } } // 初始化计数数组 int[] count = new int[max+1]; for (int i = 0; i < arr.length; i++) { count[arr[i]]++; } // 将数组的值重新按大小顺序赋值回去 int i =0,j=0; while (i<arr.length && j<max){ if (count[j] > 0){ arr[i] = j; count[j] --; i++; } if (count[j] <= 0){ count[j] --; j++; } } return arr; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
总结
这个排序算法有一个缺点就是只适合较小的数值排序，如果数组中的数值较大则会报错！
桶排序
分析
改bug人麻了，不想总结分析过程了
代码
public int[] MySort(int[] arr) { // write code here if (arr.length <= 0 || arr == null) { return null; } int length = arr.length; // 定义桶的大小 int buketSize = 100; // 桶的数量 int bucketCount = length % buketSize == 0 ? length / buketSize : length / buketSize + 1; // 定义一个桶 int[][] bucket = new int[bucketCount][]; // 计算每个桶的数值范围 int min = arr[0],max = arr[0]; for (int i = 0; i < length; i++) { if (arr[i]<min){ min = arr[i]; } if (arr[i] > max){ max = arr[i]; } } // 求每个桶的数值范围，这里一定要这样写！！！看到这里的时候自己去验算，人麻了 int bucketRange = (max-min)/bucketCount+1; // 将数组里面的数放在桶里,桶下标的计算方法：(arr[i]-min)/bucketRange int index = 0,j =0; for (int i = 0; i < length; i++) { index = (arr[i] - min)/bucketRange; // 先拷贝桶 if (bucket[index] == null || bucket[index].length <=0){ // 桶中还没有数据时为nulll，加入数据即可 bucket[index] = new int[]{arr[i]}; continue; } int[] newBucket = Arrays.copyOf(bucket[index], bucket[index].length + 1); // 将数据按大小顺序插入桶里，也就是对桶里的数据使用插入排序 for (j = newBucket.length-2; j >=0; j--) { if (newBucket[j] > arr[i] ){ newBucket[j+1] = newBucket[j]; }else { break; } } newBucket[j+1] = arr[i]; bucket[index] = Arrays.copyOf(newBucket,newBucket.length); } // 将桶里的数据倒回原数组 int k =0; for (int[] a : bucket) { for (int i = 0; i < a.length; i++) { arr[k++] = a[i]; } } return arr; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
基数排序
这个暂时不想写了，下次一定！
-
相关阅读:
hudi更新失败
Java学习笔记4.3.1 数学计算 - Math类
结构型模式-组合模式
springboot---任务---整合quartz与task----定时任务（详细）
rest-apiV2.0.0升级为simplest-api开源框架生态之simplest-jpa发布
CMake 与 VSCode 搭建 ARM 构建环境
CVE-2023-34040 Kafka 反序列化RCE
如何清除运行 Docker 容器的日志
设计模式——装饰器模式
Android Studio 实现登录注册-源代码 （连接MySql数据库）
- 原文地址：https://blog.csdn.net/m0_51405867/article/details/126115743
