常见排序算法 偏执的太偏执、 2022-05-16 07:28 224阅读 0赞 ### 常见排序算法 ### 排序问题作为算法基础的重要组成部分,代码实现方式多种多样,但其原理是基本一致的。常见的排序算法有: ①. 冒泡排序 ②. 选择排序 ③. 插入排序 ④. 归并排序 ⑥. 快速排序 ⑦. 堆排序 ⑧. 桶排序 ⑨. 基数排序 具体代码实现如下,均测试通过,如有错误,希指出。 ### 冒泡排序 ### 基本思想: \* 设置外层循环次数 \* 设置内层每一轮要比较的次数 \* 两两比较,把小的数放到前面去 public void bubbleSort(int[] a){ int len = a.length; //外层循环次数 for(int i=0;i<len;i++){ for(int j=0;j<len-i-1;j++){ //内层每一轮比较的次数 if(a[j]>a[j+1]){ //如果前一位数比后一位数大,则交换(即向上冒泡) int temp = a[j]; a[j] = a[j+1]; a[j+1] = temp; } } } } 优化: 设置标志位swapFlag = true,默认为全部已排好序。若在循环过程中,出现(排序)交换动作,则swapFlag = true,说明循环还得继续;若无交换动作,说明已经排好序的了,不满足循环条件直接跳出,减少不必要的循环次数,提高效率。 public void bubbleSort(int[] a){ int len = a.length; boolean swapFlag = true; //标志位:交换标志位,true为无交换,false为有交换 for(int i=0;i<len && swapFlag;i++){ swapFlag = false; //默认不存在交换,若无交换动作干扰,可以直接跳出循环,减少不必要的循环次数 for(int j=0;j<len-i-1;j++){ if(a[j]>a[j+1]){ int temp = a[j]; a[j] = a[j+1]; a[j+1] = temp; swapFlag = true;//若存在交换情况 } } } } ## ## ### 选择排序 ### 基本思想: \* 设定循环次数,和当前数字和当前位置 \* 将当前位置的数和后面所有的数进行对比,小的数赋值给min,并记住小数的位置 \* 对比完成后,将当前位置的数与最小的值位置交换,位置加一 \* 重复第二三步直到循环到最后一次结束 public void selectSort(int[] a){ int len = a.length; for(int i=0;i<len;i++){ //循环比较的次数 int min = a[i]; //设置当前位置的值为最小值 int position = i; //要交换的值的位置 for(int j = i;j<len;j++){ //与后面的值进行比较 if(min>a[j]){ //如果存在比min更小的值,则赋值给min min = a[j]; position = j; } } a[position] = a[i]; //对比完成后,将当前位置的数与最小的值位置交换 a[i] = min; } } ### 插入排序 ### 基本思想: \* 设定插入次数,即循环的次数,第一个数不用插入,即length-1次,总共 \* 设定要插入数的位数和有序序列最后一位的位数 \* 从最后一位向前循环,如果插入数小于当前数,就将当前数向后移动一位 \* 如果大于当前数,将当前数放到该位置 public void insertSort(int[] a){ int len = a.length; for(int i=1;i<len;i++){ //因为第一次不用,所以从1开始 int insertNum = a[i]; //要插入的数 int j = i-1; //有序序列的最后一位索引 while(j>=0 && insertNum<a[j]){ a[j+1] = a[j]; //元素向后移动 j--; //向前比较元素 } a[j+1] = insertNum; //找到位置,插入当前元素 } } ### 归并排序 ### 基本思想: \* 递归分组,将每个分组送入merge方法进行排序 \* 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列 \* 设定两个指针(变量),最初位置分别为两个已经排序序列的起始位置 \* 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置 \* 重复步骤3直到某一指针达到序列尾 \* 将另一序列剩下的所有元素直接复制到合并序列尾 public void merge(int[] a,int low,int mid,int high){ int[] temp = new int[high-low+1]; //新创建的临时数组 int i = low; //左指针 int j = mid+1; //右指针 int k = 0; //新数组索引 //把较小的数先移到新数组中 while(i<=mid && j<=high){ if(a[i]<a[j]){ temp[k++] = a[i++]; }else{ temp[k++] = a[j++]; } } //把左边剩余的数移入数组 while(i<=mid){ temp[k++] = a[i++]; } //把右边剩余的数移入数组 while(j<=high){ temp[k++] = a[j++]; } //把新数组中的数覆盖nums数组 for(int k2 = 0;k2<temp.length;k2++){ a[k2+low] = temp[k2]; } } //主函数调用归并排序方法 public void mergeSort(int[] a,int low,int high){ int mid = (low+high)/2; if(low<high){ //通过递归将数组进行分组 //左边 mergeSort(a,low,mid); //右边 mergeSort(a,mid+1,high); //左右归并,将各个分组进行排序后合并 merge(a,low,mid,high); } } ### 快速排序 ### 基本思想: \* 选定第一个为基准值,定义交换临时值 \* 当基准值左边的值小于基准值,基准值右边的值大于基准值时,i++,j--(前提条件:i<=j) \* 当基准值左边的值大于基准值,基准值右边的值小于基准值时,借用临时值进行交换 \* 当一趟快速排序结束时,即i>j \* 当满足j>start,i<end时,递归该方法,分别将i值和j值作为end值和start值参数 public void quickSort(int[] a,int start,int end){ if(start<end){ int baseNum = a[start]; //选定基准值 int temp; //交换临时值 int i = start; int j = end; do{ while(a[i]<baseNum && i<end){ //左边的数小于基准值时(合法) i++; } while(a[j]>baseNum && j>start){ //右边的数大于基准值时(合法) j--; } if(i<=j){ //当出现不满足上述条件的值时,将左右两个不符合条件的值交换 temp = a[i]; a[i] = a[j]; a[j] = temp; i++; //继续处理下一个索引值 j--; } }while(i<=j); if(start<j){ //当第一轮查找结束时,进行递归,处理基准值左边部分数组 quickSort(a,start,j); } if(end>i){ //处理基准值右边部分数组 quickSort(a,i,end); } } } ### 堆排序 ### 基本思想: \* 选定第一个为基准值,定义交换临时值 \* 对简单选择排序的优化。 \* 将序列构建成大顶堆。 \* 将根节点与最后一个节点交换,然后断开最后一个节点。 \* 重复第一、二步,直到所有节点断开。 public void heapSort(int[] a){ //循环建堆 int len = a.length; for(int i=0;i<len-1;i++){ //建堆 buildMaxHeap(a,len-1-i); //交换堆顶和最后一个元素 swap(a,0,len-1-i); } } //交换方法 private void swap(int[] data,int i,int j){ int tmp = data[i]; data[i] = data[j]; data[j] = tmp; } //对data数组从0到lastIndex建大顶堆 private void buildMaxHeap(int[] data,int lastIndex){ //从lastIndex结点(最后一个结点的父节点开始) for(int i = (lastIndex-1)/2;i>=0;i--){ //k保存正在判断的点 int k =i; //如果当前k结点的子结点存在 while(k*2+1 <= lastIndex){ //k结点的左子结点的索引 int biggerIndex = 2*k+1; //如果biggerIndex小于lastIndex,即biggerIndex+1代表的k结点的右子结点存在 if(biggerIndex < lastIndex){ //如果右子结点的值较大 if(data[biggerIndex]<data[biggerIndex+1]){ //biggerIndex总是记录较大子结点的索引 biggerIndex++; } } //如果k结点的值小于其较大的子结点的值 if(data[k]<data[biggerIndex]){ //交换它们 swap(data,k,biggerIndex); //将biggerIndex赋予k,开始while循环的下一次循环,重新保证k结点的值大于其左右子结点的值 k = biggerIndex; }else{ break; } } } } ### 时间因素,后续补充~ ### 资料参考:[https://www.cnblogs.com/10158wsj/p/6782124.html?utm\_source=tuicool&utm\_medium=referral][https_www.cnblogs.com_10158wsj_p_6782124.html_utm_source_tuicool_utm_medium_referral] 桶排序 基数排序 # **总结:** # 一、稳定性: 稳定:冒泡排序、插入排序、归并排序和基数排序 不稳定:选择排序、快速排序、希尔排序、堆排序 二、平均时间复杂度 O(n^2):直接插入排序,简单选择排序,冒泡排序。 在数据规模较小时(9W内),直接插入排序,简单选择排序差不多。当数据较大时,冒泡排序算法的时间代价最高。性能为O(n^2)的算法基本上是相邻元素进行比较,基本上都是稳定的。 O(nlogn):快速排序,归并排序,希尔排序,堆排序。 其中,快排是最好的, 其次是归并和希尔,堆排序在数据量很大时效果明显。 三、排序算法的选择 1.数据规模较小 (1)待排序列基本有序的情况下,可以选择**直接插入排序**; (2)对稳定性不作要求宜用简单选择排序,对稳定性有要求宜用插入或冒泡 2.数据规模不是很大 (1)完全可以用内存空间,序列杂乱无序,对稳定性没有要求,**快速排序**,此时要付出log(N)的额外空间。 (2)序列本身可能有序,对稳定性有要求,空间允许下,宜用归并排序 3.数据规模很大 (1)对稳定性有求,则可考虑归并排序。 (2)对稳定性没要求,宜用堆排序 4.序列初始基本有序(正序),宜用直接插入,冒泡 各算法复杂度如下: ![1153367-20170428162241834-892470604.png][] [https_www.cnblogs.com_10158wsj_p_6782124.html_utm_source_tuicool_utm_medium_referral]: https://www.cnblogs.com/10158wsj/p/6782124.html?utm_source=tuicool&utm_medium=referral [1153367-20170428162241834-892470604.png]: /images/20220516/4d427f8f723c4467b3206fb912dbe121.png
相关 [排序算法] 常见的排序算法 前言 1.冒泡排序 2.选择排序 3.插入排序 4希尔排序 5.归并排序 6.快速排序 前言 在实际需求中,我们可能要 雨点打透心脏的1/2处/ 2023年09月29日 14:29/ 0 赞/ 184 阅读
相关 算法(一)常见排序 算法-常见排序 这里写目录标题 算法-常见排序 一. 常见排序列表 二. 参考下马老师的快速排序记忆法 三. 排序 àì夳堔傛蜴生んèń/ 2022年11月14日 13:14/ 0 赞/ 103 阅读
相关 常见排序算法总结 排序算法经过了很长时间的演变,产生了很多种不同的方法。对于初学者来说,对它们进行整理便于理解记忆显得很重要。每种算法都有它特定的使用场合,很难通用。因此,我们很有必要对所有常 我会带着你远行/ 2022年08月23日 14:58/ 0 赞/ 143 阅读
相关 常见排序算法 注:点进链接查看算法具体实现!!! -------------------- 插入排序 [直接插入排序][Link 1] [希尔排序][Link 2] - 怼烎@/ 2022年06月16日 09:10/ 0 赞/ 155 阅读
相关 常见排序算法 常见排序: ![这里写图片描述][SouthEast] 1、直接插入排序 在给定数组中,拿出一个数M,与前面的数相比较,如果M大于前面的数,位置不变,如果小于前面的 迷南。/ 2022年06月05日 05:51/ 0 赞/ 195 阅读
相关 常见排序算法 常见排序算法 排序问题作为算法基础的重要组成部分,代码实现方式多种多样,但其原理是基本一致的。常见的排序算法有: ①. 冒泡排序 ②. 选择排序 ③. 插入排序 偏执的太偏执、/ 2022年05月16日 07:28/ 0 赞/ 225 阅读
相关 常见排序算法 今天实在不想刷笔试题就把常见的排序手敲了一遍 -------------------- 1.选择排序 class ChoiceSort<T extends 约定不等于承诺〃/ 2022年01月15日 13:35/ 0 赞/ 225 阅读
相关 常见排序算法 稳定排序:假设在待排序的文件中,存在两个或两个以上的记录具有相同的关键字,在用某种排序法排序后,若这些相同关键字的元素的相对次序仍然不变,则这种排序方法是稳定的。(即原本a在b 墨蓝/ 2022年01月06日 03:01/ 0 赞/ 243 阅读
还没有评论,来说两句吧...