设为首页收藏本站
开启辅助访问

在路上

 找回密码
 立即注册
在路上 › 站点首页 ›学习 › 查看内容

Java实现冒泡排序与双向冒泡排序算法的代码示例

2016-7-29 15:41| 发布者: zhangjf| 查看: 547| 评论: 0

摘要: 冒泡排序： 就是按索引逐次比较相邻的两个元素，如果大于/小于(取决于需要升序排还是降序排)，则置换，否则不做改变 这样一轮下来，比较了n-1次，n等于元素的个数；n-2, n-3 ... 一直到最后一轮，比较了1次 所以比 ...

冒泡排序：
就是按索引逐次比较相邻的两个元素，如果大于/小于(取决于需要升序排还是降序排)，则置换，否则不做改变
这样一轮下来，比较了n-1次，n等于元素的个数；n-2, n-3 ... 一直到最后一轮，比较了1次
所以比较次数为递减：从n-1 到 1
那么总的比较次数为：1+2+3+...+(n-1), 以等差公式计算：(1+n-1)/2*(n-1) ==> n/2*(n-1) ==> (n^2-n) * 0.5
用大O表示算法的时间复杂度：O(n^2) , 忽略了系数0.5和常数-n

  2. public class BubbleSort {
  3. public static void main(String[] args) {
  4. int len = 10;
  5. int[] ary = new int[len];
  6. Random random = new Random();
  7. for (int j = 0; j < len; j++) {
  8. ary[j] = random.nextInt(1000);
  9. }
  11. System.out.println("-------排序前------");
  12. for (int j = 0; j < ary.length; j++) {
  13. System.out.print(ary[j] + " ");
  14. }
  15. /*
  16. * 升序， Asc1和Asc2优化了内部循环的比较次数，比较好
  17. * 总的比较次数：
  18. * Asc1、Asc2：(1+n-1)/2*(n-1) ==> n/2*(n-1) ==> n*(n-1)/2 ==>(n^2-n)/2
  19. * Asc： n^2-n
  20. */
  21. // orderAsc(ary);
  22. // orderAsc2(ary);
  23. orderAsc1(ary);
  25. //降序，只需要把判断大小于 置换一下
  27. }
  29. static void orderAsc(int[] ary) {
  30. int count = 0;//比较次数
  31. int len = ary.length;
  32. for (int j = 0; j < len; j++) {//外层固定循环次数
  33. for (int k = 0; k < len - 1; k++) {//内层固定循环次数
  34. if (ary[k] > ary[k + 1]) {
  35. ary[k] = ary[k + 1] + (ary[k + 1] = ary[k]) * 0;//一步交换
  36. /* 交换两个变量值
  37. * a=a+b
  38. * b=a-b
  39. * a=a-b
  40. */
  41. }
  42. count++;
  43. }
  44. }
  45. System.out.println("n-----orderAsc升序排序后------次数：" + count);
  46. for (int j = 0; j < len; j++) {
  47. System.out.print(ary[j] + " ");
  48. }
  49. }
  51. static void orderAsc1(int[] ary) {
  52. int count = 0;//比较次数
  53. int len = ary.length;
  54. for (int j = 0; j < len; j++) {//外层固定循环次数
  55. for (int k = len - 1; k > j; k--) {//内层从多到少递减比较次数
  56. if (ary[k] < ary[k - 1]) {
  57. ary[k] = ary[k - 1] + (ary[k - 1] = ary[k]) * 0;//一步交换
  58. }
  59. count++;
  60. }
  61. }
  62. System.out.println("n-----orderAsc1升序排序后------次数：" + count);
  63. for (int j = 0; j < len; j++) {
  64. System.out.print(ary[j] + " ");
  65. }
  66. }
  68. static void orderAsc2(int[] ary) {
  69. int count = 0;//比较次数
  70. int len = ary.length;
  71. for (int j = len - 1; j > 0; j--) {//外层固定循环次数
  72. /*
  73. * k < j; 总的比较次数=(n^2-n)/2
  74. */
  75. for (int k = 0; k < j; k++) {//内层从多到少递减比较次数
  76. if (ary[k] > ary[k + 1]) {
  77. ary[k] = ary[k + 1] + (ary[k + 1] = ary[k]) * 0;//一步交换
  78. }
  79. count++;
  80. }
  81. }
  82. System.out.println("n-----orderAsc2升序排序后------次数：" + count);
  83. for (int j = 0; j < len; j++) {
  84. System.out.print(ary[j] + " ");
  85. }
  86. }
  87. }
复制代码

打印

  2. -------排序前------
  3. 898 7 862 286 879 660 433 724 316 737
  4. -----orderAsc1升序排序后------次数：45
  5. 7 286 316 433 660 724 737 862 879 898
复制代码

双向冒泡排序
冒泡排序_鸡尾酒排序、就是双向冒泡排序。
此算法与冒泡排序的不同处在于排序时是以双向在序列中进行排序,外层比较左右边界l 内层一个循环从左向右比，取高值置后；一个循环从右向左，取低值置前；
效率上，O(N^2), 不比普通的冒泡快

  2. public class Bubble_CocktailSort {
  3. public static void main(String[] args) {
  4. int len = 10;
  5. int[] ary = new int[len];
  6. Random random = new Random();
  7. for (int j = 0; j < len; j++) {
  8. ary[j] = random.nextInt(1000);
  9. }
  10. /*
  11. * 交换次数最小也是1次，最大也是(n^2-n)/2次
  12. */
  13. // ary=new int[]{10,9,8,7,6,5,4,3,2,1}; //测试交换次数
  14. // ary=new int[]{1,2,3,4,5,6,7,8,10,9}; //测试交换次数
  15. System.out.println("-------排序前------");
  16. for (int j = 0; j < ary.length; j++) {
  17. System.out.print(ary[j] + " ");
  18. }
  20. orderAsc1(ary);
  21. // orderAsc2(ary);
  23. //降序，只需要把判断大小于 置换一下
  25. }
  27. static void orderAsc1(int[] ary) {
  28. int compareCount = 0;//比较次数
  29. int changeCount = 0;//交换次数
  30. int len = ary.length;
  31. int left = 0, right = len -1, tl, tr;
  32. while (left < right) {//外层固定循环次数
  33. tl = left + 1;
  34. tr = right - 1;
  35. for (int k = left; k < right; k++) {//内层从多到少递减比较次数, 从左向右
  36. if (ary[k] > ary[k + 1]) {//前大于后， 置换
  37. ary[k] = ary[k + 1] + (ary[k + 1] = ary[k]) * 0;//一步交换
  38. changeCount++;
  39. tr = k; //一轮中最后一比较的时候，将k所在索引赋给tr, tr表示以后比较的结束索引值, 从左向右比后，k表示左边的索引
  40. }
  41. compareCount++;
  42. }
  43. right = tr;
  44. for (int k = right; k > left; k--) {//内层从多到少递减比较次数, 从右向左
  45. if (ary[k] < ary[k - 1]) {//后小于前 置换
  46. ary[k] = ary[k - 1] + (ary[k - 1] = ary[k]) * 0;//一步交换
  47. changeCount++;
  48. tl = k; //一轮中最后一比较的时候，将k所在索引赋给tl, tl表示以后比较的开始索引值, 从向右向左比后，k表示右边的索引
  49. }
  50. compareCount++;
  51. }
  52. left = tl;
  53. }
  54. System.out.println("n-----orderAsc1升序排序后------比较次数：" + compareCount + ", 交换次数：" + changeCount);
  55. for (int j = 0; j < len; j++) {
  56. System.out.print(ary[j] + " ");
  57. }
  58. }
  60. //跟orderAsc1的思路没有区别
  61. static void orderAsc2(int[] ary) {
  62. int compareCount = 0;//比较次数
  63. int changeCount = 0;//交换次数
  64. int len = ary.length;
  65. int l = 0, r = len -1, tl, tr;
  66. for (; l < r; ) {//外层固定循环次数
  67. tl = l + 1;
  68. tr = r - 1;
  69. /*
  70. * 从左向右比，将大的移到后面
  71. */
  72. for (int k = l; k < r; k++) {
  73. if (ary[k] > ary[k + 1]) {
  74. int temp = ary[k] + ary[k + 1];
  75. ary[k + 1] = temp - ary[k + 1];
  76. ary[k] = temp - ary[k + 1];
  77. changeCount++;
  78. tr = k;
  79. }
  80. compareCount++;
  81. }
  82. r = tr;
  83. /*
  84. * 从右向左比，将小的移到前面
  85. */
  86. for (int k = r; k > l; k--) {
  87. if (ary[k] < ary[k - 1]) {
  88. int temp = ary[k] + ary[k - 1];
  89. ary[k - 1] = temp - ary[k - 1];
  90. ary[k] = temp - ary[k - 1];
  91. changeCount++;
  92. tl = k;
  93. }
  94. compareCount++;
  95. }
  96. l = tl;
  97. }
  98. System.out.println("n-----orderAsc2升序排序后------比较次数：" + compareCount + ", 交换次数：" + changeCount);
  99. for (int j = 0; j < len; j++) {
  100. System.out.print(ary[j] + " ");
  101. }
  102. }
  103. }
复制代码

打印

  2. -------排序前------
  3. 783 173 53 955 697 839 201 899 680 677
  4. -----orderAsc1升序排序后------比较次数：34, 交换次数：22
  5. 53 173 201 677 680 697 783 839 899 955
复制代码

收藏 邀请
上一篇：浅谈Java方法的重载下一篇：Java模拟栈和队列数据结构的基本示例讲解

最新评论

相关分类

小黑屋|在路上 ( 蜀ICP备15035742号-1 )  

;

GMT+8, 2025-5-6 12:44

Copyright 2015-2025 djqfx

返回顶部