鱼C论坛

 找回密码
 立即注册
查看: 1976|回复: 0

[学习笔记] 冒泡排序算法及其优化

[复制链接]
发表于 2018-10-12 21:28:15 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
本帖最后由 影-死神 于 2018-10-12 22:39 编辑

一. 冒泡排序算法基本思路
        1. 从第一位开始,每次比较相邻元素,根据大小来交换元素的位置,序号增加一后循环执行此步骤
        2. 一轮循环完后,无序区中最大的元素被交换到末尾,作为有序区,最大元素之前作为无序区
        3. 将无序区按照上述步骤循环执行,直到无序区的元素个数为1
        算法的时间复杂度:
                由于需要执行两个for循环,所以时间复杂度为 n**2
        Java代码实现:

  1. public class BubbleSort {
  2.     private static void sort1(int[] list) {
  3.         int temp;
  4.         for (int i=0;i<list.length;i++) {
  5.             for (int j=0;j<list.length-i-1;j++) {
  6.                 if (list[j] > list[j+1]) {
  7.                     temp = list[j];
  8.                     list[j] = list[j+1];
  9.                     list[j+1] = temp;
  10.                 }
  11.             }
  12.         }
  13.     }  
  14.     public static void main(String[] args) {
  15.         int[] list = {5, 8, 6, 3, 9, 2, 1, 7};
  16.         
  17.         sort1(list);
  18.         
  19.         for (int i=0;i<list.length;i++) {
  20.             System.out.print(list[i] + " ");
  21.         }
  22.     }
  23. }
复制代码


二. 优化冒泡算法
        发现问题1:如果数列经过几轮排序后,已经是有序的了,此时,循环仍然继续执行
        优化思路1:每轮循环执行后,判断数列是否有序,如果有序,直接结束循环
        实现方法1:
                1. 设置一个标记,每轮执行前标记为有序
                2. 如果执行过程中有元素交换,说明数列不是有序的,标记为无序
                3. 执行完成后,如果标记为仍为有序,则跳出循环
       Java代码实现:
  1. public class BubbleSort {
  2.     private static void sort2(int[] list) {
  3.             int temp;
  4.             for (int i=0;i<list.length;i++) {
  5.                     boolean isSorted = true;
  6.                     for (int j=0;j<list.length-i-1;j++) {
  7.                             if (list[j] > list[j+1]) {
  8.                                     temp = list[j];
  9.                                     list[j] = list[j+1];
  10.                                     list[j+1] = temp;
  11.                                     isSorted = false;
  12.                             }
  13.                     }
  14.                   
  15.                     if (isSorted) {
  16.                             break;
  17.                     }
  18.             }
  19.     }
  20.    
  21.     public static void main(String[] args) {
  22.             int[] list = {5, 8, 6, 3, 9, 2, 1, 7};
  23.            
  24.             sort2(list);
  25.            
  26.             for (int i=0;i<list.length;i++) {
  27.                     System.out.print(list + " ");
  28.             }
  29.     }
  30. }
复制代码


        
        发现问题2:在执行某轮排序前,无序区中,最后几位已经是无序区中最大值的有序排列
        优化思路2:若某轮执行后,发现上述情况,直接将最大值的有序排列并入有序区
        优化方法2:
                1. 在每轮排序的最后记录最后一次元素交换的位置,将此位置作为边界,之后的为有序区
                2. 将每轮排序的判断条件改为:从0到边界
        Java代码实现:
  1. public class BubbleSort {
  2.         private static void sort3(int[] list) {
  3.                 int temp;
  4.                 //最后交换元素的位置
  5.                 int index = 0;
  6.                 //无序和有序的边界
  7.                 int sortBorder = list.length -1;
  8.                 for (int i=0;i<list.length;i++) {
  9.                         boolean isSorted = true;
  10.                         for (int j=0;j<sortBorder;j++) {
  11.                                 if (list[j] > list[j+1]) {
  12.                                         temp = list[j];
  13.                                         list[j] = list[j+1];
  14.                                         list[j+1] = temp;
  15.                                        
  16.                                         isSorted = false;
  17.                                         //不要在for循环内改变for循环判断的条件,即不能直接使用sortBorder = j
  18.                                         index = j;
  19.                                 }
  20.                         }
  21.                         sortBorder = index;
  22.                        
  23.                         if (isSorted) {
  24.                                 break;
  25.                         }
  26.                 }
  27.         }
  28.       
  29.         public static void main(String[] args) {
  30.                 int[] list = {5, 8, 6, 3, 9, 2, 1, 7};
  31.                
  32.                 sort3(list);
  33.                
  34.                 for (int i=0;i<list.length;i++) {
  35.                         System.out.print(list + " ");
  36.                 }
  37.         }
  38. }  
复制代码

   

三. 所有代码
  1. public class BubbleSort {
  2.         private static void sort1(int[] list) {
  3.                 int temp;
  4.                 for (int i=0;i<list.length;i++) {
  5.                         for (int j=0;j<list.length-i-1;j++) {
  6.                                 if (list[j] > list[j+1]) {
  7.                                         temp = list[j];
  8.                                         list[j] = list[j+1];
  9.                                         list[j+1] = temp;
  10.                                 }
  11.                         }
  12.                 }
  13.         }
  14.       
  15.         private static void sort2(int[] list) {
  16.                 int temp;
  17.                 for (int i=0;i<list.length;i++) {
  18.                         boolean isSorted = true;
  19.                         for (int j=0;j<list.length-i-1;j++) {
  20.                                 if (list[j] > list[j+1]) {
  21.                                         temp = list[j];
  22.                                         list[j] = list[j+1];
  23.                                         list[j+1] = temp;
  24.                                         isSorted = false;
  25.                                 }
  26.                         }
  27.                        
  28.                         if (isSorted) {
  29.                                 break;
  30.                         }
  31.                 }
  32.         }
  33.       
  34.         private static void sort3(int[] list) {
  35.                 int temp;
  36.                 //最后交换元素的位置
  37.                 int index = 0;
  38.                 //无序和有序的边界
  39.                 int sortBorder = list.length -1;
  40.                 for (int i=0;i<list.length;i++) {
  41.                         boolean isSorted = true;
  42.                         for (int j=0;j<sortBorder;j++) {
  43.                                 if (list[j] > list[j+1]) {
  44.                                         temp = list[j];
  45.                                         list[j] = list[j+1];
  46.                                         list[j+1] = temp;
  47.                                        
  48.                                         isSorted = false;
  49.                                         //不要在for循环内改变for循环判断的条件,即不能直接使用sortBorder = j
  50.                                         index = j;
  51.                                 }
  52.                         }
  53.                         sortBorder = index;
  54.                        
  55.                         if (isSorted) {
  56.                                 break;
  57.                         }
  58.                 }
  59.         }
  60.       
  61.         public static void main(String[] args) {
  62.                 int[] list = {5, 8, 6, 3, 9, 2, 1, 7};
  63.                
  64.                 //sort1(list);
  65.                 //sort2(list);
  66.                 sort3(list);
  67.                
  68.                
  69.                 for (int i=0;i<list.length;i++) {
  70.                         System.out.print(list + " ");
  71.                 }
  72.         }
  73. }
复制代码

另外,排序算法在java中可直接使用java.util.Arrays.sort(list);

本帖被以下淘专辑推荐:

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 20:21

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表