JS 冒泡排序从学到优化

目的:理解算法深化算法

冒泡排序:

直接上动图好于文字

一个冒泡实例

45,67,23,88,21,6,99
// 第一轮 6次
// 45 67 23 88 21 6 99
// 45 23 67 88 21 6 99
// 45 23 67 88 21 6 99
// 45 23 67 21 88 6 99
// 45 23 67 21 6 88 99
// 45 23 67 21 6 88 99

// 第二轮 6次
// 23 45 67 21 6 88 99
// 23 45 67 21 6 88 99
// 23 45 21 67 6 88 99
// 23 45 21 6 67 88 99
// 23 45 21 6 67 88 99
// 23 45 21 6 67 88 99

// 第三轮 6次
// 23 45 21 6 67 88 99
// 23 21 45 6 67 88 99
// 23 21 6 45 67 88 99
// 23 21 6 45 67 88 99
// 23 21 6 45 67 88 99
// 23 21 6 45 67 88 99

// 第四轮 6次
// 21 23 6 45 67 88 99
// 21 6 23 45 67 88 99
// 21 6 23 45 67 88 99
// 21 6 23 45 67 88 99
// 21 6 23 45 67 88 99
// 21 6 23 45 67 88 99

// 第五轮 6次
// 6 21 23 45 67 88 99
// 6 21 23 45 67 88 99
// 6 21 23 45 67 88 99
// 6 21 23 45 67 88 99
// 6 21 23 45 67 88 99
// 6 21 23 45 67 88 99
// 第六轮 6次(这个第6轮即使后面已经成型了它还是按照程序走一遍)
// 6 21 23 45 67 88 99
// 6 21 23 45 67 88 99
// 6 21 23 45 67 88 99
// 6 21 23 45 67 88 99
// 6 21 23 45 67 88 99
// 6 21 23 45 67 88 99

上代码(基础型)

 1 冒泡排序:
 2 <!DOCTYPE html>
 3 <html lang="en">
 4 <head>
 5     <meta charset="UTF-8">
 6     <title>Document</title>
 7     <script>
 8     //(双重for循环 第一个for控制轮数 第二个for控制次数 比较的轮数为数据个数-1 一轮比较的次数为数据个数-1 总个数为比较轮数*1轮比较次数)
 9         var a=[45,67,23,88,21,6,99];
10         var temp=[];
11         var m=0;//轮数
12         var n=0;//一共次数
13         for(var i=0;i<a.length-1;i++){//这里不减1 后面轮数就+1 这是不对的 因为数组下标0开始
14             for(var j=0;j<a.length-1;j++){
15                 if(a[j]>a[j+1]){//后面的大于前面的 后面再前  前面在后 从小到大
16                     temp=a[j];//a[j]=temp;
17                     a[j]=a[j+1];//a[j+1]=a[j];
18                     a[j+1]=temp;//a[j+1]=temp
19                 //顺序不能调换 因为a[]里面有个下标是一定从小到大的
20                 }
21                 n++
22             }
23             m++;
24         }
25         //document.write(a.length);
26         document.write(a+"<br>");
27         document.write("轮数"+m+"<br>");
28         document.write("总次数"+n+"<br>");
29         // a1  a2
30         // 3    2
31         // temp 
32 
33         // 2     3
34         //      temp
35 
36         //  2    3   
37         // temp
38 
39 
40 // 第一轮 6次
41 // 45 67 23 88 21 6 99
42 // 45 23 67 88 21 6 99
43 // 45 23 67 88 21 6 99
44 // 45 23 67 21 88 6 99
45 // 45 23 67 21 6 88 99
46 // 45 23 67 21 6 88 99
47 
48 // 第二轮 6次
49 // 23 45 67 21 6 88 99
50 // 23 45 67 21 6 88 99
51 // 23 45 21 67 6 88 99
52 // 23 45 21 6 67 88 99
53 // 23 45 21 6 67 88 99
54 // 23 45 21 6 67 88 99
55 
56 // 第三轮 6次
57 // 23 45 21 6 67 88 99
58 // 23 21 45 6 67 88 99
59 // 23 21 6 45 67 88 99
60 // 23 21 6 45 67 88 99
61 // 23 21 6 45 67 88 99
62 // 23 21 6 45 67 88 99
63 
64 // 第四轮 6次
65 // 21 23 6 45 67 88 99
66 // 21 6 23 45 67 88 99
67 // 21 6 23 45 67 88 99
68 // 21 6 23 45 67 88 99
69 // 21 6 23 45 67 88 99
70 // 21 6 23 45 67 88 99
71 
72 // 第五轮 6次
73 // 6 21 23 45 67 88 99
74 // 6 21 23 45 67 88 99
75 // 6 21 23 45 67 88 99
76 // 6 21 23 45 67 88 99
77 // 6 21 23 45 67 88 99
78 // 6 21 23 45 67 88 99
79 // 第六轮 6次(这个第6轮即使后面已经成型了 它还是按照程序走一遍)
80 // 6 21 23 45 67 88 99
81 // 6 21 23 45 67 88 99
82 // 6 21 23 45 67 88 99
83 // 6 21 23 45 67 88 99
84 // 6 21 23 45 67 88 99
85 // 6 21 23 45 67 88 99
86 
87 
88     </script>
89 </head>
90 <body>
91     
92 </body>
93 </html>

上代码(优化1):

  1 冒泡排序优化://每轮比较少比较一次。（每一轮都会比较出一个最大值，然后后一轮没有必要再比较了，所以没比较一轮，就少比较一次。。。） j<a.length-1-i
  2 <!DOCTYPE html>
  3 <html lang="en">
  4 <head>
  5     <meta charset="UTF-8">
  6     <title>Document</title>
  7     <script>
  8         var a=[45,67,23,88,21,6,99];
  9         var temp=[];
 10         var m=0;//轮数
 11         var n=0;//一共次数
 12         for(var i=0;i<a.length-1;i++){//这里不减1 后面轮数就+1 这是不对的 因为数组下标0开始
 13             for(var j=0;j<a.length-1-i;j++){  //每轮比较少比较一次。（每一轮都会比较出一个最大值，然后后一轮没有必要再比较了，所以没比较一轮，就少比较一次。。。）
 14                 if(a[j]>a[j+1]){//后面的大于前面的 后面再前  前面在后 从小到大
 15                     temp=a[j];//a[j]=temp;
 16                     a[j]=a[j+1];//a[j+1]=a[j];
 17                     a[j+1]=temp;//a[j+1]=temp
 18                 //顺序不能调换 因为a[]里面有个下标是一定从小到大的
 19                 }
 20                 n++
 21             }
 22             m++;
 23         }
 24         //document.write(a.length);
 25         document.write(a+"<br>");
 26         document.write("轮数"+m+"<br>");
 27         document.write("总次数"+n+"<br>");
 28         // a1  a2
 29         // 3    2
 30         // temp 
 31 
 32         // 2     3
 33         //      temp
 34 
 35         //  2    3   
 36         // temp
 37 
 38 
 39 // 第一轮 6次
 40 // 45 67 23 88 21 6 99
 41 // 45 23 67 88 21 6 99
 42 // 45 23 67 88 21 6 99
 43 // 45 23 67 21 88 6 99
 44 // 45 23 67 21 6 88 99
 45 // 45 23 67 21 6 88 99
 46 
 47 // 第二轮 6次
 48 // 23 45 67 21 6 88 99
 49 // 23 45 67 21 6 88 99
 50 // 23 45 21 67 6 88 99
 51 // 23 45 21 6 67 88 99
 52 // 23 45 21 6 67 88 99
 53 // 23 45 21 6 67 88 99
 54 
 55 // 第三轮 6次
 56 // 23 45 21 6 67 88 99
 57 // 23 21 45 6 67 88 99
 58 // 23 21 6 45 67 88 99
 59 // 23 21 6 45 67 88 99
 60 // 23 21 6 45 67 88 99
 61 // 23 21 6 45 67 88 99
 62 
 63 // 第四轮 6次
 64 // 21 23 6 45 67 88 99
 65 // 21 6 23 45 67 88 99
 66 // 21 6 23 45 67 88 99
 67 // 21 6 23 45 67 88 99
 68 // 21 6 23 45 67 88 99
 69 // 21 6 23 45 67 88 99
 70 
 71 // 第五轮 6次
 72 // 6 21 23 45 67 88 99
 73 // 6 21 23 45 67 88 99
 74 // 6 21 23 45 67 88 99
 75 // 6 21 23 45 67 88 99
 76 // 6 21 23 45 67 88 99
 77 // 6 21 23 45 67 88 99
 78 // 第六轮 6次(这个第6轮即使后面已经成型了 它还是按照程序走一遍)
 79 // 6 21 23 45 67 88 99
 80 // 6 21 23 45 67 88 99
 81 // 6 21 23 45 67 88 99
 82 // 6 21 23 45 67 88 99
 83 // 6 21 23 45 67 88 99
 84 // 6 21 23 45 67 88 99
 85 
 86 
 87 
 88 // 第一轮 6次
 89 // 45 67 23 88 21 6 99
 90 // 45 23 67 88 21 6 99
 91 // 45 23 67 88 21 6 99
 92 // 45 23 67 21 88 6 99
 93 // 45 23 67 21 6 88 99
 94 // 45 23 67 21 6 88 99
 95 
 96 // 第二轮 5次
 97 // 23 45 67 21 6 88 99
 98 // 23 45 67 21 6 88 99
 99 // 23 45 21 67 6 88 99
100 // 23 45 21 6 67 88 99
101 // 23 45 21 6 67 88 99
102 
103 // 第三轮 4次
104 // 23 45 21 6 67 88 99
105 // 23 21 45 6 67 88 99
106 // 23 21 6 45 67 88 99
107 // 23 21 6 45 67 88 99
108 
109 // 第四轮 3次
110 // 21 23 6 45 67 88 99
111 // 21 6 23 45 67 88 99
112 // 21 6 23 45 67 88 99
113 
114 
115 // 第五轮 2次
116 // 6 21 23 45 67 88 99
117 // 6 21 23 45 67 88 99
118 
119 // 第六轮 1次
120 // 6 21 23 45 67 88 99
121 
122     </script>
123 </head>
124 <body>
125     
126 </body>
127 </html>

这里的i就是为了减少比较次数的,通过红色数字可以看出,每一轮下来,其实红色部分是不会再进行比较的,因为他已经从大到小排了,如果是基础版,必须得走,优化后,红色的那部分无需再进行比较.

次数=n(n-1)/2

上代码(优化2):

  1 冒泡排序优化2
  2 做一个判断
  3 如果在比较的时候 两两不发生比较了 就退出循环 
  4 <!DOCTYPE html>
  5 <html lang="en">
  6 <head>
  7     <meta charset="UTF-8">
  8     <title>Document</title>
  9     <script>
 10         var a=[45,67,23,88,21,6,99];
 11         //var a=[3,2,1,0,6];
 12         //var a=[1,2,4,3,5,6,7,8,9];
 13         var temp=[];
 14         var m=0;//轮数
 15         var n=0;//一共次数
 16         //如果比较完备提前结束比较。（判断，如果本次比较没有移动任何元素，那么说明已经比较完成）
 17         for(var i=0;i<a.length-1;i++){//这里不减1 后面轮数就+1 这是不对的 因为数组下标0开始
 18              //开闭原则。（写在第一个for循环里，是为了，每轮比较初始化bool变量变为true。）
 19             var bool=true;
 20             for(var j=0;j<a.length-1-i;j++){  //每轮比较少比较一次。（每一轮都会比较出一个最大值，然后后一轮没有必要再比较了，所以没比较一轮，就少比较一次。。。）
 21                 if(a[j]>a[j+1]){//后面的大于前面的 后面再前  前面在后 从小到大
 22                     temp=a[j];//a[j]=temp;
 23                     a[j]=a[j+1];//a[j+1]=a[j];
 24                     a[j+1]=temp;//a[j+1]=temp
 25                 //顺序不能调换 因为a[]里面有个下标是一定从小到大的
 26                     bool=false;
 27                          
 28                 }
 29                 n++;
 30             }
 31             
 32             //bool这个变量默认值为true;如果本轮比较有一对元素相互交换位置，那么也不能跳出循环。
 33         //但是，如果本轮比较没有任何元素相互交换位置，那么说明已经比较完成，可以跳出循环。
 34             m++;
 35             if(bool){
 36                 break;
 37             }
 38             
 39         }
 40         //document.write(a.length);
 41         document.write(a+"<br>");
 42         
 43         document.write("总次数"+n+"<br>");
 44         document.write("轮数"+m+"<br>");
 45         // a1  a2
 46         // 3    2
 47         // temp 
 48 
 49         // 2     3
 50         //      temp
 51 
 52         //  2    3   
 53         // temp
 54 
 55 
 56 // 第一轮 6次
 57 // 45 67 23 88 21 6 99
 58 // 45 23 67 88 21 6 99
 59 // 45 23 67 88 21 6 99
 60 // 45 23 67 21 88 6 99
 61 // 45 23 67 21 6 88 99
 62 // 45 23 67 21 6 88 99
 63 
 64 // 第二轮 6次
 65 // 23 45 67 21 6 88 99
 66 // 23 45 67 21 6 88 99
 67 // 23 45 21 67 6 88 99
 68 // 23 45 21 6 67 88 99
 69 // 23 45 21 6 67 88 99
 70 // 23 45 21 6 67 88 99
 71 
 72 // 第三轮 6次
 73 // 23 45 21 6 67 88 99
 74 // 23 21 45 6 67 88 99
 75 // 23 21 6 45 67 88 99
 76 // 23 21 6 45 67 88 99
 77 // 23 21 6 45 67 88 99
 78 // 23 21 6 45 67 88 99
 79 
 80 // 第四轮 6次
 81 // 21 23 6 45 67 88 99
 82 // 21 6 23 45 67 88 99
 83 // 21 6 23 45 67 88 99
 84 // 21 6 23 45 67 88 99
 85 // 21 6 23 45 67 88 99
 86 // 21 6 23 45 67 88 99
 87 
 88 // 第五轮 6次
 89 // 6 21 23 45 67 88 99
 90 // 6 21 23 45 67 88 99
 91 // 6 21 23 45 67 88 99
 92 // 6 21 23 45 67 88 99
 93 // 6 21 23 45 67 88 99
 94 // 6 21 23 45 67 88 99
 95 // 第六轮 6次(这个第6轮即使后面已经成型了 它还是按照程序走一遍)
 96 // 6 21 23 45 67 88 99
 97 // 6 21 23 45 67 88 99
 98 // 6 21 23 45 67 88 99
 99 // 6 21 23 45 67 88 99
100 // 6 21 23 45 67 88 99
101 // 6 21 23 45 67 88 99
102 
103 
104 
105 // 第一轮 6次
106 // 45 67 23 88 21 6 99
107 // 45 23 67 88 21 6 99
108 // 45 23 67 88 21 6 99
109 // 45 23 67 21 88 6 99
110 // 45 23 67 21 6 88 99
111 // 45 23 67 21 6 88 99
112 
113 // 第二轮 5次
114 // 23 45 67 21 6 88 99
115 // 23 45 67 21 6 88 99
116 // 23 45 21 67 6 88 99
117 // 23 45 21 6 67 88 99
118 // 23 45 21 6 67 88 99
119 
120 // 第三轮 4次
121 // 23 45 21 6 67 88 99
122 // 23 21 45 6 67 88 99
123 // 23 21 6 45 67 88 99
124 // 23 21 6 45 67 88 99
125 
126 // 第四轮 3次
127 // 21 23 6 45 67 88 99
128 // 21 6 23 45 67 88 99
129 // 21 6 23 45 67 88 99
130 
131 
132 // 第五轮 2次
133 // 6 21 23 45 67 88 99
134 // 6 21 23 45 67 88 99
135 
136 // 第六轮 1次
137 // 6 21 23 45 67 88 99
138 
139     </script>
140 </head>
141 <body>
142     
143 </body>
144 </html>

这里加了判断后可以减少外层循环
比如 排序123
基础排序为2轮4次
-i排序为2轮3次(它只舍去了第二轮循环的第二次比较)
bool判断的话为:1轮2次 因为它进行一轮2次比较后发现下一轮没有可比较的了 直接退出循环 输出排序