• 冒泡排序详细详解


    因为在面试时  经常手写冒泡排序   可是冒泡排序看起来容易  理解起来也是有点问题   所以今天把冒泡排序的知识点详细的从头整理一下

    如果下面的文字不理解   可以参考B站【Java基础入门 冒泡排序】https://www.bilibili.com/video/BV1td4y1g7Fy?vd_source=581d732b20cb23e01428068f153a99ed

    我也是用的这个例子

    我们以下面的例子为例

    题目:

    使用冒泡排序,实现整型数组元素的排序操作
    
    比如:int[] arr = {9, 7, 8, 5, 6, 4, 3, 2, 1};
    分析

    我们先比较内层  就是第一轮  每相邻二个元素  交换位置 交换的规则 默认大的放后面 小的放前面

    我们如果想实现数组的两两交换的话  我们这里面   我们应该让arr[0]与arr[1]进行比较  大的放在前面  小的放在后面

    arr[0]=9

    arr[1]=7

    如果arr[0]>arr[1]   那么就要进行比较   要进行交换就要引入第三方变量 temp  

    所以我们应该写的代码如下 

    1. if(arr[0]>arr[1]){
    2. int temp =arr[0];
    3. arr[0] =arr[1];
    4. arr[1]=temp;
    5. }

    这时我们的数据就变成

    int[] arr = {7,9, 8, 5, 6, 4, 3, 2, 1};

    接下去在这个数据的基础上  我们的arr[1]和arr[2]进行比较

    arr[1] =9

    arr[2] =8

    如果arr[1]>arr[1]   那么就要进行比较   要进行交换就要引入第三方变量 temp  

    所以我们应该写的代码如下 

    1. if(arr[1]>arr[2]){
    2. int temp = arr[1];
    3. arr[1] = arr[2];
    4. arr[2] = temp;
    5. }

    这时我们的数据就变成

    int[] arr = {7,8, 9, 5, 6, 4, 3, 2, 1};

    一直相邻比较后  我们就可以求得最大值

    由我们的分析  我们每次的代码都是重复  主要是重复的代码 我们就要用到循环  所以我们就可以书写代码如下   完成每轮交换  完成第一轮交换后  9就在最右边   取得最大值

    1. public class BubbleSortTest3 {
    2. public static void main(String[] args) {
    3. /*1.相邻的数据交换位置 交换的规则 默认大的放后面 小的放前面 */
    4. int[] arr = {9, 7, 8, 5, 6, 4, 3, 2, 1};
    5. for (int j = 0; j < arr.length; j++) {
    6. if (arr[j] > arr[j + 1]) {
    7. int temp = arr[j];
    8. arr[j] = arr[j + 1];
    9. arr[j + 1] = temp;
    10. }
    11. }
    12. }
    13. }

    但是我们上面的代码是有错的  

    当i取得最大索引的时候  这里我们i的最大索引是8  也就是arr[8]   arr[8]>arr[9]  可是我们并没有9的索引  如果这样写的话  会报如下错误

    所以应该写成下面这个样子

    1. public class BubbleSortTest3 {
    2. public static void main(String[] args) {
    3. /*1.相邻的数据交换位置 交换的规则 默认大的放后面 小的放前面 */
    4. int[] arr = {9, 7, 8, 5, 6, 4, 3, 2, 1};
    5. for (int j = 0; j < arr.length-1; j++) {
    6. if (arr[j] > arr[j + 1]) {
    7. int temp = arr[j];
    8. arr[j] = arr[j + 1];
    9. arr[j + 1] = temp;
    10. }
    11. }
    12. }
    13. }

    这样第一轮交换就已经拿到最大值

    接下去我们进行第二轮交换

    因为第一轮时  最大值已经确定下来了 所以我们不用在比较最大值    所以arr.length-1-1

    这样子数组中的元素我们就可以少比较一个

    第二轮比较的代码如下 

    1. package com.atguigu4.search_sort.exer3;
    2. import java.util.Arrays;
    3. public class BubbleSortTest3 {
    4. public static void main(String[] args) {
    5. /*1.相邻的数据交换位置 交换的规则 默认大的放后面 小的放前面 */
    6. int[] arr = {9, 7, 8, 5, 6, 4, 3, 2, 1};
    7. //排序前 对数组进行遍历
    8. System.out.println("排序前");
    9. for (int i = 0; i < arr.length; i++) {
    10. }
    11. System.out.println(Arrays.toString(arr));
    12. //排序后
    13. System.out.println("排序后");
    14. //第一轮
    15. System.out.println("第一轮");
    16. for (int j = 0; j < arr.length-1; j++) {
    17. if (arr[j] > arr[j + 1]) {
    18. int temp = arr[j];
    19. arr[j] = arr[j + 1];
    20. arr[j + 1] = temp;
    21. }
    22. }
    23. System.out.println(Arrays.toString(arr));
    24. //第二轮
    25. System.out.println("第二轮");
    26. for (int j = 0; j < arr.length-1-1; j++) {
    27. if (arr[j] > arr[j + 1]) {
    28. int temp = arr[j];
    29. arr[j] = arr[j + 1];
    30. arr[j + 1] = temp;
    31. }
    32. }
    33. System.out.println(Arrays.toString(arr));
    34. }
    35. }

    以此类推  我们比较8轮

    1. package com.atguigu4.search_sort.exer3;
    2. import java.util.Arrays;
    3. public class BubbleSortTest3 {
    4. public static void main(String[] args) {
    5. /*1.相邻的数据交换位置 交换的规则 默认大的放后面 小的放前面 */
    6. int[] arr = {9, 7, 8, 5, 6, 4, 3, 2, 1};
    7. //排序前 对数组进行遍历
    8. System.out.println("排序前");
    9. for (int i = 0; i < arr.length; i++) {
    10. }
    11. System.out.println(Arrays.toString(arr));
    12. //排序后
    13. System.out.println("排序后");
    14. //第一轮
    15. System.out.println("第一轮");
    16. for (int j = 0; j < arr.length-1-0; j++) {
    17. if (arr[j] > arr[j + 1]) {
    18. int temp = arr[j];
    19. arr[j] = arr[j + 1];
    20. arr[j + 1] = temp;
    21. }
    22. }
    23. System.out.println(Arrays.toString(arr));
    24. //第二轮
    25. System.out.println("第二轮");
    26. for (int j = 0; j < arr.length-1-1; j++) {
    27. if (arr[j] > arr[j + 1]) {
    28. int temp = arr[j];
    29. arr[j] = arr[j + 1];
    30. arr[j + 1] = temp;
    31. }
    32. }
    33. System.out.println(Arrays.toString(arr));
    34. //第三轮
    35. System.out.println("第三轮");
    36. for (int j = 0; j < arr.length-1-2; j++) {
    37. if (arr[j] > arr[j + 1]) {
    38. int temp = arr[j];
    39. arr[j] = arr[j + 1];
    40. arr[j + 1] = temp;
    41. }
    42. }
    43. System.out.println(Arrays.toString(arr));
    44. //第四轮
    45. System.out.println("第二轮");
    46. for (int j = 0; j < arr.length-1-3; j++) {
    47. if (arr[j] > arr[j + 1]) {
    48. int temp = arr[j];
    49. arr[j] = arr[j + 1];
    50. arr[j + 1] = temp;
    51. }
    52. }
    53. System.out.println(Arrays.toString(arr));
    54. //第五轮
    55. System.out.println("第四轮");
    56. for (int j = 0; j < arr.length-1-4; j++) {
    57. if (arr[j] > arr[j + 1]) {
    58. int temp = arr[j];
    59. arr[j] = arr[j + 1];
    60. arr[j + 1] = temp;
    61. }
    62. }
    63. System.out.println(Arrays.toString(arr));
    64. //第六轮
    65. System.out.println("第六轮");
    66. for (int j = 0; j < arr.length-1-5; j++) {
    67. if (arr[j] > arr[j + 1]) {
    68. int temp = arr[j];
    69. arr[j] = arr[j + 1];
    70. arr[j + 1] = temp;
    71. }
    72. }
    73. System.out.println(Arrays.toString(arr));
    74. //第七轮
    75. System.out.println("第七轮");
    76. for (int j = 0; j < arr.length-1-6; j++) {
    77. if (arr[j] > arr[j + 1]) {
    78. int temp = arr[j];
    79. arr[j] = arr[j + 1];
    80. arr[j + 1] = temp;
    81. }
    82. }
    83. System.out.println(Arrays.toString(arr));
    84. //第八轮
    85. System.out.println("第八轮");
    86. for (int j = 0; j < arr.length-1-7; j++) {
    87. if (arr[j] > arr[j + 1]) {
    88. int temp = arr[j];
    89. arr[j] = arr[j + 1];
    90. arr[j + 1] = temp;
    91. }
    92. }
    93. System.out.println(Arrays.toString(arr));
    94. }
    95. }

    每一轮比较的代码都是重复的   所以我们可以把循环的代码用for循环循环包起来

    循环

    1. package com.atguigu4.search_sort.exer3;
    2. import java.util.Arrays;
    3. /**
    4. * ClassName: BubbleSortTest3
    5. * Package: com.atguigu4.search_sort.exer3
    6. * Description:
    7. *
    8. * @Author 小白
    9. * @Create 2023/10/20 1:49
    10. * @Version 1.0
    11. */
    12. public class BubbleSortTest3 {
    13. public static void main(String[] args) {
    14. /*1.相邻的数据交换位置 交换的规则 默认大的放后面 小的放前面 */
    15. int[] arr = {9, 7, 8, 5, 6, 4, 3, 2, 1};
    16. //排序前 对数组进行遍历
    17. System.out.println("排序前");
    18. for (int i = 0; i < arr.length; i++) {
    19. }
    20. System.out.println(Arrays.toString(arr));
    21. //排序后
    22. System.out.println("排序后");
    23. for (int i = 0; i < arr.length; i++) {
    24. for (int j = 0; j < arr.length - 1 - i; j++) {
    25. if (arr[j] > arr[j + 1]) {
    26. int temp = arr[j];
    27. arr[j] = arr[j + 1];
    28. arr[j + 1] = temp;
    29. }
    30. }
    31. System.out.println(Arrays.toString(arr));
    32. }
    33. // //第一轮
    34. // System.out.println("第一轮");
    35. // for (int j = 0; j < arr.length-1-0; j++) {
    36. //
    37. // if (arr[j] > arr[j + 1]) {
    38. // int temp = arr[j];
    39. // arr[j] = arr[j + 1];
    40. // arr[j + 1] = temp;
    41. // }
    42. // }
    43. //
    44. // System.out.println(Arrays.toString(arr));
    45. //
    46. //
    47. //
    48. //
    49. //
    50. // //第二轮
    51. // System.out.println("第二轮");
    52. // for (int j = 0; j < arr.length-1-1; j++) {
    53. //
    54. // if (arr[j] > arr[j + 1]) {
    55. // int temp = arr[j];
    56. // arr[j] = arr[j + 1];
    57. // arr[j + 1] = temp;
    58. // }
    59. // }
    60. //
    61. // System.out.println(Arrays.toString(arr));
    62. //
    63. //
    64. // //第三轮
    65. // System.out.println("第三轮");
    66. // for (int j = 0; j < arr.length-1-2; j++) {
    67. //
    68. // if (arr[j] > arr[j + 1]) {
    69. // int temp = arr[j];
    70. // arr[j] = arr[j + 1];
    71. // arr[j + 1] = temp;
    72. // }
    73. // }
    74. //
    75. // System.out.println(Arrays.toString(arr));
    76. //
    77. //
    78. //
    79. // //第四轮
    80. // System.out.println("第二轮");
    81. // for (int j = 0; j < arr.length-1-3; j++) {
    82. //
    83. // if (arr[j] > arr[j + 1]) {
    84. // int temp = arr[j];
    85. // arr[j] = arr[j + 1];
    86. // arr[j + 1] = temp;
    87. // }
    88. // }
    89. //
    90. // System.out.println(Arrays.toString(arr));
    91. //
    92. //
    93. //
    94. // //第五轮
    95. // System.out.println("第四轮");
    96. // for (int j = 0; j < arr.length-1-4; j++) {
    97. //
    98. // if (arr[j] > arr[j + 1]) {
    99. // int temp = arr[j];
    100. // arr[j] = arr[j + 1];
    101. // arr[j + 1] = temp;
    102. // }
    103. // }
    104. //
    105. // System.out.println(Arrays.toString(arr));
    106. //
    107. //
    108. // //第六轮
    109. // System.out.println("第六轮");
    110. // for (int j = 0; j < arr.length-1-5; j++) {
    111. //
    112. // if (arr[j] > arr[j + 1]) {
    113. // int temp = arr[j];
    114. // arr[j] = arr[j + 1];
    115. // arr[j + 1] = temp;
    116. // }
    117. // }
    118. //
    119. // System.out.println(Arrays.toString(arr));
    120. //
    121. //
    122. //
    123. // //第七轮
    124. // System.out.println("第七轮");
    125. // for (int j = 0; j < arr.length-1-6; j++) {
    126. //
    127. // if (arr[j] > arr[j + 1]) {
    128. // int temp = arr[j];
    129. // arr[j] = arr[j + 1];
    130. // arr[j + 1] = temp;
    131. // }
    132. // }
    133. //
    134. // System.out.println(Arrays.toString(arr));
    135. //
    136. //
    137. //
    138. // //第八轮
    139. // System.out.println("第八轮");
    140. // for (int j = 0; j < arr.length-1-7; j++) {
    141. //
    142. // if (arr[j] > arr[j + 1]) {
    143. // int temp = arr[j];
    144. // arr[j] = arr[j + 1];
    145. // arr[j + 1] = temp;
    146. // }
    147. // }
    148. //
    149. // System.out.println(Arrays.toString(arr));
    150. //
    151. }
    152. }

    当第一轮比较的时候  arr.length-1-0   因为谁都不确定  所以都要比较

    当第二轮比较的时候  arr.length-1-1  因为最大值已经出来了

    当第三轮比较的时候  arr.length-1-2  因为最大值和次大值已经出来了

    轮数=元素的总个数-1

    因为我们数组的无数有9个 所以我们要比较8轮

    因为我们有9个数据(有9个元素)  所以我们要进行8轮交换 所以我们的代码变成如下
    1. package com.atguigu4.search_sort.exer3;
    2. import java.util.Arrays;
    3. /**
    4. * ClassName: BubbleSortTest3
    5. * Package: com.atguigu4.search_sort.exer3
    6. * Description:
    7. *
    8. * @Author 小白
    9. * @Create 2023/10/20 1:49
    10. * @Version 1.0
    11. */
    12. public class BubbleSortTest3 {
    13. public static void main(String[] args) {
    14. /*1.相邻的数据交换位置 交换的规则 默认大的放后面 小的放前面 */
    15. int[] arr = {9, 7, 8, 5, 6, 4, 3, 2, 1};
    16. //排序前 对数组进行遍历
    17. System.out.println("排序前");
    18. for (int i = 0; i < arr.length; i++) {
    19. }
    20. System.out.println(Arrays.toString(arr));
    21. //排序后
    22. System.out.println("排序后");
    23. for (int i = 0; i < arr.length - 1; i++) {
    24. for (int j = 0; j < arr.length - 1 - i; j++) {
    25. if (arr[j] > arr[j + 1]) {
    26. int temp = arr[j];
    27. arr[j] = arr[j + 1];
    28. arr[j + 1] = temp;
    29. }
    30. }
    31. System.out.println(Arrays.toString(arr));
    32. }
    33. // //第一轮
    34. // System.out.println("第一轮");
    35. // for (int j = 0; j < arr.length-1-0; j++) {
    36. //
    37. // if (arr[j] > arr[j + 1]) {
    38. // int temp = arr[j];
    39. // arr[j] = arr[j + 1];
    40. // arr[j + 1] = temp;
    41. // }
    42. // }
    43. //
    44. // System.out.println(Arrays.toString(arr));
    45. //
    46. //
    47. //
    48. //
    49. //
    50. // //第二轮
    51. // System.out.println("第二轮");
    52. // for (int j = 0; j < arr.length-1-1; j++) {
    53. //
    54. // if (arr[j] > arr[j + 1]) {
    55. // int temp = arr[j];
    56. // arr[j] = arr[j + 1];
    57. // arr[j + 1] = temp;
    58. // }
    59. // }
    60. //
    61. // System.out.println(Arrays.toString(arr));
    62. //
    63. //
    64. // //第三轮
    65. // System.out.println("第三轮");
    66. // for (int j = 0; j < arr.length-1-2; j++) {
    67. //
    68. // if (arr[j] > arr[j + 1]) {
    69. // int temp = arr[j];
    70. // arr[j] = arr[j + 1];
    71. // arr[j + 1] = temp;
    72. // }
    73. // }
    74. //
    75. // System.out.println(Arrays.toString(arr));
    76. //
    77. //
    78. //
    79. // //第四轮
    80. // System.out.println("第二轮");
    81. // for (int j = 0; j < arr.length-1-3; j++) {
    82. //
    83. // if (arr[j] > arr[j + 1]) {
    84. // int temp = arr[j];
    85. // arr[j] = arr[j + 1];
    86. // arr[j + 1] = temp;
    87. // }
    88. // }
    89. //
    90. // System.out.println(Arrays.toString(arr));
    91. //
    92. //
    93. //
    94. // //第五轮
    95. // System.out.println("第四轮");
    96. // for (int j = 0; j < arr.length-1-4; j++) {
    97. //
    98. // if (arr[j] > arr[j + 1]) {
    99. // int temp = arr[j];
    100. // arr[j] = arr[j + 1];
    101. // arr[j + 1] = temp;
    102. // }
    103. // }
    104. //
    105. // System.out.println(Arrays.toString(arr));
    106. //
    107. //
    108. // //第六轮
    109. // System.out.println("第六轮");
    110. // for (int j = 0; j < arr.length-1-5; j++) {
    111. //
    112. // if (arr[j] > arr[j + 1]) {
    113. // int temp = arr[j];
    114. // arr[j] = arr[j + 1];
    115. // arr[j + 1] = temp;
    116. // }
    117. // }
    118. //
    119. // System.out.println(Arrays.toString(arr));
    120. //
    121. //
    122. //
    123. // //第七轮
    124. // System.out.println("第七轮");
    125. // for (int j = 0; j < arr.length-1-6; j++) {
    126. //
    127. // if (arr[j] > arr[j + 1]) {
    128. // int temp = arr[j];
    129. // arr[j] = arr[j + 1];
    130. // arr[j + 1] = temp;
    131. // }
    132. // }
    133. //
    134. // System.out.println(Arrays.toString(arr));
    135. //
    136. //
    137. //
    138. // //第八轮
    139. // System.out.println("第八轮");
    140. // for (int j = 0; j < arr.length-1-7; j++) {
    141. //
    142. // if (arr[j] > arr[j + 1]) {
    143. // int temp = arr[j];
    144. // arr[j] = arr[j + 1];
    145. // arr[j + 1] = temp;
    146. // }
    147. // }
    148. //
    149. // System.out.println(Arrays.toString(arr));
    150. //
    151. }
    152. }

    所以综合以上分析  我们冒泡排序代码如下:

    1. package com.atguigu4.search_sort.exer3;
    2. import java.util.Arrays;
    3. /**
    4. * ClassName: BubbleSortTest3
    5. * Package: com.atguigu4.search_sort.exer3
    6. * Description:
    7. *
    8. * @Author 小白
    9. * @Create 2023/10/20 1:49
    10. * @Version 1.0
    11. */
    12. public class BubbleSortTest3 {
    13. public static void main(String[] args) {
    14. /*1.相邻的数据交换位置 交换的规则 默认大的放后面 小的放前面 */
    15. int[] arr = {9, 7, 8, 5, 6, 4, 3, 2, 1};
    16. //排序前 对数组进行遍历
    17. System.out.println("排序前");
    18. for (int i = 0; i < arr.length; i++) {
    19. }
    20. System.out.println(Arrays.toString(arr));
    21. //排序后
    22. System.out.println("排序后");
    23. for (int i = 0; i < arr.length - 1; i++) {
    24. for (int j = 0; j < arr.length - 1 - i; j++) {
    25. if (arr[j] > arr[j + 1]) {
    26. int temp = arr[j];
    27. arr[j] = arr[j + 1];
    28. arr[j + 1] = temp;
    29. }
    30. }
    31. System.out.println(Arrays.toString(arr));
    32. }
    33. }
    34. }

     输出结果如下 :

     
    

    也可以把代码封装成一个方法  Ctrl+Alt+M

    1. package com.atguigu4.search_sort.exer3;
    2. import java.util.Arrays;
    3. /**
    4. * ClassName: BubbleSortTest3
    5. * Package: com.atguigu4.search_sort.exer3
    6. * Description:
    7. *
    8. * @Author 小白
    9. * @Create 2023/10/20 1:49
    10. * @Version 1.0
    11. */
    12. public class BubbleSortTest3 {
    13. public static void main(String[] args) {
    14. /*1.相邻的数据交换位置 交换的规则 默认大的放后面 小的放前面 */
    15. int[] arr = {9, 7, 8, 5, 6, 4, 3, 2, 1};
    16. //排序前 对数组进行遍历
    17. System.out.println("排序前");
    18. for (int i = 0; i < arr.length; i++) {
    19. }
    20. System.out.println(Arrays.toString(arr));
    21. //排序后
    22. System.out.println("排序后");
    23. sort(arr);
    24. }
    25. private static void sort(int[] arr) {
    26. for (int i = 0; i < arr.length - 1; i++) {
    27. for (int j = 0; j < arr.length - 1 - i; j++) {
    28. if (arr[j] > arr[j + 1]) {
    29. int temp = arr[j];
    30. arr[j] = arr[j + 1];
    31. arr[j + 1] = temp;
    32. }
    33. }
    34. // System.out.println(Arrays.toString(arr));
    35. }
    36. }
    37. }

  • 相关阅读:
    【网络安全 --- Burp Suite抓包工具】学网安必不可少的Burp Suite工具的安装及配置
    【5GC】5G网络切片与5G QoS的区别?
    java开发四年之旅
    Leetcode.337 打家劫舍 III
    基础复习——数据库SQLite——SQL的基本语法——数据库管理器SQLiteDatabase——数据库帮助器SQLiteOpenHelper...
    2022年第十四届蓝桥杯Python选拔赛11月27日中高级组
    HTML如何制作音乐网站(如何搭建个人音乐网页)
    ORA-12514:TNS:监听程序当前无法识别链接描述符中请求的服务
    Vue2+ThreeJS工程无痛搭建指南
    2021长安杯
  • 原文地址:https://blog.csdn.net/m0_59281987/article/details/133937994