排序算法总结 今天药忘吃喽~ 2021-12-13 15:01 285阅读 0赞 ### 1.冒泡排序 ### > 冒泡算法思想: > 1.从左到右依次比较相邻的元素。如果第一个比第二个大,就交换他们两个,等全部执行完,最后的元素就是最大的数,这 时候完成了第一波冒泡。 > 2.继续从左到右比较相邻的元素,步骤和第一步相同,但是最后一个元素不参与比较,以此类推 > 冒泡排序是由两个for循环构成,第一个for循环表示总共需要多少轮比较,第二个for循环表示每轮参与比较的元素下标 > 冒泡排序性能分析: > 假设所有的数组元素个数为N,则第一轮需要比较N-1次,第二轮N-2次,以此类推,总需排序次数的公式为: > (N-1)+(N-2)+...+1 = N\*(N-1)/2 > 当 N 的值很大时,忽略幂数较小的加减法,比较次数约为N2/2次。 > 假设数据是随机的,那么每次比较可能要交换位置,可能不会交换,假设概率为50%,那么交换次数为 N2/4。但如 果初始数据是逆序的,那么每次比较都要交换位置。 > 交换和比较次数都和N2 成正比。由于常数不算大 O 表示法中,忽略 2 和 4,那么冒泡排序运行都需要 O(N2) 时间 级别。 public static String deploy(int[] numbers){ StringBuffer sb = new StringBuffer(); Ints.asList(numbers).forEach(i -> sb.append(i +",")); return sb.toString(); } static int[] numbers = {5,3,9,4,7,6,1,3,4,7,8,7}; // 经典冒泡排序 public static void main(String[] args) { // 增加saveLength,是末尾已经排好序的数字不再参与排序 int saveLength = 1; int count = 0; for (int i = 1; i < numbers.length; i++) { // 增加这个判断,是还未参与排序的数字,没必要再进行排序了, // 因为在进行该数字排序时,其整个数字顺序已经是排好的了 boolean jduge = true; for (int j = 0; j < numbers.length-saveLength; j++) { if (numbers[j] > numbers[j + 1]) { int tmp = numbers[j]; numbers[j] = numbers[j + 1]; numbers[j + 1] = tmp; jduge = false; } System.out.println(++count + " : "+deploy(numbers)); } if (jduge){ break; } saveLength++; } System.out.println(deploy(numbers)); } //末尾已经排好序的不再参与,仍可优化 public static void main(String[] args) { int saveLength = 1; int count = 0; for (int i = 1; i < numbers.length; i++) { for (int j = 0; j < numbers.length-saveLength; j++) { if (numbers[j] > numbers[j + 1]) { int tmp = numbers[j]; numbers[j] = numbers[j + 1]; numbers[j + 1] = tmp; } System.out.println(++count + " : "+deploy(numbers)); } saveLength++; } System.out.println(deploy(numbers)); } //基本比较算法,拥有可优化空间 public static void main(String[] args) { int count = 0; for (int i = 1; i < numbers.length; i++) { for (int j = 0; j < numbers.length-1; j++) { if (numbers[j] > numbers[j + 1]) { int tmp = numbers[j]; numbers[j] = numbers[j + 1]; numbers[j + 1] = tmp; } System.out.println(++count + " : "+deploy(numbers)); } } System.out.println(deploy(numbers)); } ### 2.选择排序 ### > 选择排序思想: > 1.从待排序元素中,找到最小的元素 > 2.如果最小元素不是待排序序列的第一个元素,将其和第一个元素互换,此后第一个元素不再参与对比,以此类推 > 选择排序次数:N\*(N-1)/2,和冒泡排序相同,但选择排序至多只进行了N次交换,而冒泡排序的交换次数是N2。 > 当N值很大时,比较次数是主要的,所以和冒泡排序一样,用大O表示是O(N2)时间级别。但是选择排序交换的次数少,所以 选择排序比冒泡排序快 public static String deploy(int[] numbers){ StringBuffer sb = new StringBuffer(); Ints.asList(numbers).forEach(i -> sb.append(i +",")); return sb.toString(); } static int[] numbers = {5,3,9,4,7,6,1,3,4,7,8,7}; // 减少交换的次数 public static void main(String[] args) { for (int i=0;i<numbers.length-1;i++){ int min = i; // 已参与排序的,不再进行对比 for (int j=i+1;j<numbers.length;j++){ if (numbers[min] > numbers[j]){ min = j; } } //每次排序只交换一次 if (min != i){ int tmp = numbers[i]; numbers[i] = numbers[min]; numbers[min] = tmp; } } System.out.println(deploy(numbers)); } ### 3.插入排序 ### > 每一步将一个待排序的元素,插入到前面已经排好序的有序元素中去,直到所有元素排序完毕 > 插入排序总共参与比较次数为 1+2+3+...+N-1 = N\*(N-1)/2。 > 当 N 的值很大时,忽略幂数较小的加减法,比较次数约为N2/2次,假设数据是随机的,那么每次比较可能要交换位置,可 能不会交换,假设概率为50%,那么交换次数为 N2/4 > 复制的次数大致等于比较的次数,但是一次复制与一次交换的时间耗时不同,所以相对于随机数据,插入排序比冒泡 快一倍,比选择排序略快。 > 但是如果要进行逆序排列,那么每次比较和移动都会进行,这时候并不会比冒泡排序快。 public static String deploy(int[] numbers){ StringBuffer sb = new StringBuffer(); Ints.asList(numbers).forEach(i -> sb.append(i +",")); return sb.toString(); } static int[] numbers = {5,3,9,4,7,6,1,3,4,7,8,7}; public static void main(String[] args) { for (int i=1;i<numbers.length;i++){ int tmp = numbers[i]; int count = i; for (int j = i;j>0;j--){ if (tmp < numbers[j-1]){ numbers[j] = numbers[j-1]; count--; } } numbers[count] = tmp; } System.out.println(deploy(numbers)); } public static void main(String[] args) { // 这里代表的已经不只是循环次数,还能指定当前需要比较的那个数字,对这个特定的数字进行对比 for (int i=1;i<numbers.length;i++){ int tmp = numbers[i]; // 从最右侧开始比较 int j = i; while(j>0 && tmp < numbers[j-1]){ numbers[j] = numbers[j-1]; j--; } numbers[j] = tmp; } System.out.println(deploy(numbers)); }
相关 排序算法总结 概述 排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。 我们这里说说八 ﹏ヽ暗。殇╰゛Y/ 2022年07月15日 22:38/ 0 赞/ 177 阅读
相关 算法-排序算法总结 冒泡排序 朴素冒泡排序 反复扫描待排序序列,在扫描的过程中顺次比较相邻的两个元素的大小,若逆序就交换位置。第一趟,从第一个数据开始,比较相邻的两个数据,(以升序为例 短命女/ 2022年06月09日 01:58/ 0 赞/ 288 阅读
相关 排序算法总结 冒泡排序 时间复杂度为O(n2),最好情况下为O(n),空间复杂度为O(1)。稳定的 冒泡排序总结: void swap(int &a,int 比眉伴天荒/ 2022年05月18日 09:36/ 0 赞/ 203 阅读
相关 排序算法总结 排序算法总结 <table> <thead> <tr> <th align="center">排序算法</th> <th align="cent ╰半橙微兮°/ 2022年04月12日 08:57/ 0 赞/ 197 阅读
相关 排序算法总结 1.插入排序算法(附伪代码和C源码) 插入排序原理:从第i=2位开始到数组长度|A|截至。将当前i的值key取出来,从i开始从后往前\[1, i-1\]寻找小于(大 淩亂°似流年/ 2022年01月06日 04:09/ 0 赞/ 281 阅读
相关 排序算法总结 最近在看左神的算法视频,随便记录下自己的学习心得,方便以后review,也让大家对基本的排序算法有个了解。 冒泡排序 > 冒泡排序(英语:Bubble Sort)是一种 红太狼/ 2022年01月06日 01:51/ 0 赞/ 314 阅读
相关 排序算法总结 O(n2)的冒泡,选择,插入,先不贴,先贴归并,快排,堆排, O(nlog(n)) 归并排序 二路归并递归写法:时间O(nlog(n)),稳定,总时间O(nlog),空间 分手后的思念是犯贱/ 2021年12月21日 01:21/ 0 赞/ 262 阅读
相关 排序算法总结 1.冒泡排序 > 冒泡算法思想: > 1.从左到右依次比较相邻的元素。如果第一个比第二个大,就交换他们两个,等全部执行完,最后的元素就是最大的数,这 今天药忘吃喽~/ 2021年12月13日 15:01/ 0 赞/ 286 阅读
相关 排序算法总结 常见排序算法评估 时间复杂度 O(n2):冒泡排序、选择排序、插入排序 O(nlogn):归并排序、快速排序、堆排序、希尔排序 O(n):计数排序、基数排序 ╰半橙微兮°/ 2021年12月13日 14:13/ 0 赞/ 302 阅读
相关 排序算法总结 2019-07-20 import java.net.Socket; import java.util.Arrays; import java.uti 超、凢脫俗/ 2021年11月19日 14:54/ 0 赞/ 335 阅读
还没有评论,来说两句吧...