热门标签
热门文章
- 1Windows bat 批处理学习_windows管道符执行结果追加到文件
- 22024数学建模美赛C题详细代码思路手把手教学_美赛c2024
- 3mac连接easyconnnect显示“本地环境出现异常”。亲测已解决_easyconnect本地环境出现异常
- 4api-ms-win-core-path-l1-1-0.dll丢失？_api-ms-win-core-l1-1-0.dll 丢失
- 5【软考系统规划与管理师笔记】第7篇 IT服务运营管理_系统规划与管理师 运营管理
- 6python pandas库（自用，持续更新）
- 7如何安全的开放后端接口_接口开放出去
- 8Qt QFrame
- 9【SPIE独立出版，往届已检索|华中科技大学电气与电子工程学院主办|ei会议论文，EI核心，Scopus检索】 第八届能源系统、电气与电力国际学术会议（ESEP 2023）_esep 2023 模版
- 10C语言可变参数函数（printf/scanf）_c语言函数可选参数
当前位置: article > 正文
Java基本排序总结（Sort）_java sort
作者：我家自动化 | 2024-02-07 21:26:01
赞
踩
java sort
什么是排序
排序的定义
对一序列对象根据某个关键字进行排序（通俗点来说就是吧一堆数据按照从小到大（升序），或者从大到小排列（降序）），我们下面都基于升序来讲解。
排序的相关术语
- 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面
- 不稳定：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面
- 内排序：所有排序操作都在内存中完成
- 外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行
- 时间复杂度： 一个算法执行所耗费的时间
- 空间复杂度：运行完一个程序所需内存的大小
排序的分类
算法分析
冒泡排序
冒泡排序（bulleSort）这里就不在多说了，非常经典的一种排序，我们接触的第一种排序啦。
算法描述：
- 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
- 从头到尾两两元素进行比较交换 ，这时尾部元素为最大元素
- 针对所有的元素重复以上的步骤，除了最后一个
- 重复步骤1~3，直到排序完成
算法分析
时间复杂度：
- 当数据有序时 最好 O(n)
- 当数据无序时 最差 O(n2)
空间复杂度O(1)
不稳定
实现代码
public static void bullSort(int[] array){ for(int i=0;i<array.length;i++) { int flag=0; for(int j=0;j<array.length-1-i;j++) { if(array[j]>array[j+1]) { int tmp=array[j]; array[j]=array[j+1]; array[j+1]=tmp; flag=1; } } if(flag==0) { break; } } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
选择排序
选择排序(selectSort)是一种简单直观的排序算法。首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
算法描述
- 先将第一个元素开始，将第一个元素与后面的每一个元素进行比较，如果比其小，则进行交换，直到数组遍历完，第一个元素便是最小的元素
- 接着从第二个元素开始，与第二个元素之后的元素进行比较
- 重复上述过程
算法分析
时间复杂度：
- 当数据有序时 最好 O(n)
- 当数据无序时 最差 O(n2)
空间复杂度O(1)
稳定
实现代码
public static void selectSort(int[] array) {
for(int i=0;i<array.length-1;i++)
{
for(int j=i+1;j<array.length;j++)
{
if(array[j]<array[i])
{
int tmp=array[i];
array[i]=array[j];
array[j]=tmp;
}
}
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
希尔排序
希尔排序（shellSort）也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，它与插入排序的不同之处在于，它会优先比较距离较远的元素（将小的数据尽可能的放到前面）希尔排序是把数据按照增量数组中得值分成好多个组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的数据越来越多，当增量减至1时，整个数据恰被分成一组，其实此时也就是插入排序了。（增量数组当中的值为素数，但最后一个是1）
算法描述
- 选择一个增量序列drr[]
- 从增量序列中取出第一个k，对序列进行分组，并对进行每组进行插入排序
- 选择增量序列中的下一个，重复2步骤
算法分析
算法分析
时间复杂度：
- 最好 O（n1.5）
- 最坏 O（n2）
空间复杂度O（1）
不稳定
实现代码
public static void shellSort(int[] array) { int[] drr = {5,3,1};//增量数组 for (int i = 0; i < drr.length; i++) { shell(array,drr[i]); } } public static void shell(int[] array ,int gap) { int j,tmp; for(int i=gap;i<array.length;i++) { tmp=array[i]; j=i-gap; for(;j>=0;j-=gap) { if(array[j]>tmp) { array[j+gap]=array[j]; }else{ break; } } array[j+gap]=tmp; } }
- 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
举例数组为[12,5,9,16,6,8,27,58,80,0,7,4,33,55,77]
增量序列为[5,3,1]
- 分五组
- 每组进行插入排序
- 在分三组，在进行插入排序
归并排序
归并排序（mergeSort）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。（原理-合并两个有序数组）
算法描述
来分析一下吧，对于归并算法，有两个部分组成，分解和合并。首先讲讲分解，我们需要将待排序的序列不停地进行分解，通过两个索引变量控制，一个初始索引（low），一个结尾索引（high）。只有当两索引重合才结束分解。接下来是合并，合并操作也是最麻烦的，也是通过两个索引变量s1,s2。开始s1在左边序列的第一个位置，s2在右边序列的第一个位置，然后就是寻找左右两个序列中的最小值(合并两个数组)，放到新序列中，这时可能会出现一边的元素都放置完毕了，而另外一边还存在元素，此时只需将剩余的元素按顺序放进新序列即可，因为这时左右两边的序列已经是有序的了，最后将新序列复制到旧序列。这里也特别需要注意，因为合并的过程是分步的，而并非一次合并完成，所以数组的索引是在不断变化的。(所以需要加strat保证位置的正确性)
算法分析
时间复杂度：
- 最好：O(nlogn)
- 最坏：O(nlogn)
空间复杂度 O（n）
稳定
实现代码
- 递归实现
public static void mergeSort(int[] array){ mergeSortInternal(array,0,array.length-1); } public static void mergeSortInternal(int[] array,int low,int high){ if(low>=high) return ; int mid=(low+high)/2; //分解 mergeSortInternal(array,low,mid); mergeSortInternal(array,mid+1,high); //合并 merge(array,low,mid,high); } //核心：两数组进行合并 public static void merge(int[] array,int start,int mid,int end){ int s1=start; int s2=mid+1; int[] tmp=new int[end-start+1]; int k=0; while(s1<=mid&&s2<=end) { if(array[s1]<=array[s2]) { tmp[k++]=array[s1++]; }else{ tmp[k++]=array[s2++]; } } //有可能第一个段还有数据 有可能第2个段也有数据 while(s1<=mid) { tmp[k++]=array[s1++]; } while(s2<=end) { tmp[k++]=array[s2++]; } for(int i=0;i<end-start+1;i++) { //一定要加上start array[i+start]=tmp[i]; } } // 归并排序 private static void merge_sort(int[] arr, int low, int high) { if (low>=high) return; int mid = low+high>>1; merge_sort(arr, low, mid); merge_sort(arr, mid + 1, high); int[] tmp = new int[high - low + 1]; int i = low, j = mid + 1, k = 0; // 进行归并 while (i <= mid && j <= high) { if (arr[i] <= arr[j]) tmp[k++] = arr[i++]; else tmp[k++] = arr[j++]; } while (i <= mid) tmp[k++] = arr[i++]; while (j <= high) tmp[k++] = arr[j++]; // 进行赋值 for (i = low, j = 0; i <=high; i++, j++) arr[i] = tmp[j]; }
- 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
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 非递归实现
//非递归版本 public static void mergeSort2(int[] array) { for (int i = 1; i < array.length; i*=2) { merge(array,i); } } public static void merge(int[] array,int gap) { int s1 = 0; int e1 = s1+gap-1; int s2 = e1+1; int e2 = s2+gap-1 < array.length ? s2+gap-1 : array.length-1; int[] tmp = new int[array.length]; int k = 0;//下标 //当有两个归并段的时候 while (s2 < array.length) { //当当有两个归并段 且 这两个段内都要数据 while (s1 <= e1 && s2<= e2) { if(array[s1] <= array[s2]) { tmp[k++] = array[s1++]; }else{ tmp[k++] = array[s2++]; } } while (s1 <= e1) { tmp[k++] = array[s1++]; } while (s2 <= e2){ tmp[k++] = array[s2++]; } //从这里开始的时候，每个下标都可能越界 s1 = e2+1; e1 = s1+gap-1; s2 = e1+1; e2 = s2+gap-1 < array.length ? s2+gap-1 : array.length-1; } //退出上面循环后， // 那么把s1段内的数据给拷贝下来,因为 有可能e1已经越界了 while (s1 < array.length) { tmp[k++] = array[s1++]; } //拷贝tmp到原数组当中 for (int i = 0; i < tmp.length; i++) { array[i] = tmp[i]; } }
- 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
直接插入排序
直接插入排序（insertSort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
生活中打扑克牌就是插入排序的体现
算法描述
- 1.从第一个元素开始，该元素可以认为已经被排序；
- 2.取出下一个元素，在已经排序的元素序列中从后向前扫描；
- 3.如果该元素（已排序）大于新元素，将该元素移到下一位置；
- 4.重复步骤3，直到找到已排序的元素小于或者等于新元素的位置，然后将新元素插入到该位置后；
- 5.重复步骤2~4。
算法分析
时间复杂度：
- 当数据有序时 最好：O(n)
- 数据是无序的 最坏：O(n2)
空间复杂度 O（1）
稳定
实现代码
public class insertSort { public static void insertSort(int[] array) { for (int i = 1; i < array.length; i++) { int tmp = array[i]; int j = i-1; for (j; j >= 0 ; j--) { //如果这里是一个大于等于号 此时这个排序就不稳定了 if(array[j] > tmp) { array[j+1] = array[j]; }else { break; } } array[j+1] = tmp; } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
直接插入排序数据越有序，排序越快。当数据大部分有序时，使用直接插入排序最合适，直接插入排序也会用在其他一些排序的优化上。
快速排序（快排）
快速排序（quickSort）的基本思想：通过一趟排序将待排记录分成两部分，其中一部分数据比某一个值均大，另一部分比这个值均小，（称这个值为基准pivot）然后分别对这两部分记录继续进行排序，以达到整个序列有序。
算法描述
- 从数列中挑出一个元素，称为 “基准”（pivot）
- 在找的过程中，重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）
- 递归地（quick）把小于基准值元素和大于基准值元素在进行排列即可
算法分析
时间复杂度：
- 最好：O(nlogn)
- 数据是有序的 最坏：O(n2)
空间复杂度 O（nlogn）
不稳定
实现代码
- 递归实现
//递归写法及其优化 public static void quickSort1(int[] array){ quick(array,0,array.length-1); } //找基准 public static int pivot(int[] array,int low,int high) { int tmp = array[low]; while (low < high) { while (array[high]>=tmp&&low<high) { high--; } //把high数据赋值给low array[low]=array[high]; while (array[low]<=tmp&&low<high) { low++; } //把low下标的值给high array[high]=array[low]; } array[low] = tmp; return low; } public static void insertSort(int[] array,int low,int high) { int tmp,j; for(int i=low;i<=high;i++) { tmp=array[i]; j=i-1; for(;j>=low;j--) { if(array[j]>tmp) { array[j+1]=array[j]; }else{ break; } } array[j+1]=tmp; } } public static void quick(int[] array,int low,int high){ if(low>=high) return ; if(high-low + 1 <= 50) { //使用插入排序 insertSort(array,low,high); return;//记着这里一定要return 这里说明 这个区别范围有序了 直接结束 } //优化1 medianOfThree(array,low,high); int piv=pivot(array,low,high); quick(array,low,piv-1); quick(array,piv+1,high); } //三数取中法优化（找基准） public static void swap(int[] array,int i,int j) { int tmp = array[i]; array[i] = array[j]; array[j] = tmp; } public static void medianOfThree(int[] array,int low,int high) { int mid = (low+high)/2; //array[mid] <= array[low] <= array[high] if(array[low] < array[mid]) { swap(array,low,mid); }//array[mid] <= array[low] if(array[low] > array[high]) { swap(array,low,high); }//array[low] <= array[high] if(array[mid] > array[high]) { swap(array,mid,high); }//array[mid] <= array[high] } //2 递归实现 private static void quickSort(int[] arr, int low, int high) { if(low>=high) return ; int i=low,j=high; while (i< j) { while (i < j && arr[j] >= arr[low]) j--; while (i < j && arr[i] <= arr[low]) i++; swap(arr, i, j); } swap(arr, i, low); quickSort(arr, low, i - 1); quickSort(arr, i + 1, high); } private static void swap(int[] arr, int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; }
- 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
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 非递归代码
//非递归写法 //找基准 public static int pivot(int[] array,int low,int high) { int tmp = array[low]; while (low < high) { while (array[high]>=tmp&&low<high) { high--; } //把high数据赋值给low array[low]=array[high]; while (array[low]<=tmp&&low<high) { low++; } //把low下标的值给high array[high]=array[low]; } array[low] = tmp; return low; } public static void quickSort2(int[] array) { Stack<Integer> stack = new Stack<>(); int low = 0; int high = array.length-1; int piv = pivot(array,low,high);// if(piv > low + 1) { stack.push(low); stack.push(piv-1); } if(piv < high-1) { stack.push(piv+1); stack.push(high); } while (!stack.empty()) { high = stack.pop(); low = stack.pop(); piv = pivot(array,low,high); if(piv > low + 1) { stack.push(low); stack.push(piv-1); } if(piv < high-1) { stack.push(piv+1); stack.push(high); } } }
- 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
堆排序
堆排序（heapSort）在学堆排序之前我们需要了解大根堆、小根堆、如何构造堆等相关的一些知识（不了解的话，可以看看博主之前写的堆的文章）。
算法描述
我们默认是升序从小到大，我们分为三个步骤
- 我们需要建一个大堆（降序的话建小堆）
- 然后将第一个元素（最大的元素）与最后一个元素进行交换，然后再对第一个元素进行向下调整（保证剩余元素为大根堆，第一个元素为剩下元素的最大值）
- 然后再将倒数第二个元素与第一个元素进行2过程，重复进行，知道走到第一个元素结束
算法分析
时间复杂度：
- 最好的最坏都是O（n*log2n）
空间复杂度O（1）
稳定的
实现代码
代码
//向下调整 public static void adjustDown(int[] array,int parent,int len) { int child = 2*parent+1; while (child < len) { if(child+1 < len && array[child] < array[child+1]) { child++;// } if(array[child] > array[parent]) { int tmp = array[child]; array[child] = array[parent]; array[parent] = tmp; parent = child; child = 2*parent+1; }else { break; } } } //建大堆 public static void crateBigHeap(int[] array) { for(int i = (array.length-1-1) /2; i>= 0;i--) { adjustDown(array,i,array.length); } } //堆排序 public static void heapSort(int[] array) { crateBigHeap(array); int end=array.length-1; while(end>0) { int tmp=array[0]; array[0]=array[end]; array[end]=tmp; adjustDown(array,0,end); end--; } }
- 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
海量数据的排序问题
外部排序：排序过程需要在磁盘等外部存储进行的排序前提：内存只有 1G，需要排序的数据有 100G
因为内存中因为无法把所有数据全部放下，所以需要外部排序，而归并排序是最常用的外部排序
- 先把文件切分成 200 份，每个 512 M
- 分别对 512 M 排序，因为内存已经可以放的下，所以任意排序方式都可以
- 进行 200 路归并，同时对 200 份有序文件做归并过程，最终结果就有序了
总结
- 只有冒泡插入归并是稳定的，其余是不稳定的
- 归并、快排和堆比较难，一定要理解，他们三个也挺像的，时间复杂度都是O（nlogn），如果数据无序的话快排最快（不然为啥叫快排哈哈哈！）但空间的复杂度不同，归并最大是O（n）（因为开辟了数组），其次是快排为O（logn）（因为递归中开辟了栈帧），最小是堆排为O(1)。大家要理解。
- 只有归并是外排序，其余都是内排序
上面这些排序都是基于比较然后进行交换的思想，但也有不需要交换的方法，那便是计数排序、桶排序等等，大家感兴趣的话可以下去看看，这里就不做过多描述了。
好了，如果有错误和不懂的地方的话留言评论即可。
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家自动化/article/detail/67447
推荐阅读
相关标签
