js冒泡排序经典代码_冒泡排序 js

js冒泡排序经典代码_冒泡排序 js基本思想:两两比较相邻记录的关键字,如果反序则交换,直至没有反序为止。 最初的冒泡排序(初级版): 由于这样的排序仅仅是交换顺序,不算是真正的冒泡排序,效率也比较低。 当i=0, arr[0]和它后边的每一项进行比较大小,前者大于后者,则进行交换。始终保证arr[0]为最小值。 当i=1,(arr[

js冒泡排序经典代码_冒泡排序

基本思想两两比较相邻记录的关键字,如果反序则交换,直至没有反序为止。

  • 最初的冒泡排序(初级版)
 1 //从小到大
 2 function BubbleSort(arr){
 3     var i,j,temp;
 4     for(i=0;i<arr.length-1;i++){
 5         for(j=i+1;j<arr.length;j++){
 6             if(arr[i]>arr[j]){
 7                 temp=arr[j];
 8                 arr[j]=arr[i];
 9                 arr[i]=temp;
10             }
11         }
12     }
13     return arr;
14 }
15 var arr=[10,7,9,11,22,33,4,2,0,1000];
16 BubbleSort(arr);  
17 console.log(arr); //[0, 2, 4, 7, 9, 10, 11, 22, 33, 1000]

由于这样的排序仅仅是交换顺序,不算是真正的冒泡排序,效率也比较低。

当i=0,

arr[0]和它后边的每一项进行比较大小,前者大于后者,则进行交换。始终保证arr[0]为最小值。

当i=1,(arr[0]已经为最小值,不需要进行比较,)

arr[1]和它后边的每一项进行比较大小,前者大于后者,则进行交换。始终保证arr[1]为最小值(除去arr[0]以外)。

…….直至i=arr.length-2时,保证前arr.length-1项均“比较”小(小于后边的所有项),此时不再需要进行比较。(当n个数,前n-1个为“比较”小的值后,最后一个还有什么比较的意义呢??)

  • 正宗的冒泡排序(将小的数字如同气泡一样慢慢的浮上表面)

 

 1     //从小到大
 2     function BubbleSort(arr){
 3         var i,j,temp;
 4         for(i=0;i<arr.length-1;i++){
 5             for(j=arr.length-1;j>i;j--){
 6                 if(arr[j]<arr[j-1]){ //j为从后往前循环
 7                     temp=arr[j-1];
 8                     arr[j-1]=arr[j];
 9                     arr[j]=temp;
10                 }
11             }
12         }
13         return arr;
14     }
15     var arr=[10,7,9,11,22,33,4,2,0,1000];
16     BubbleSort(arr);

17 console.log(arr);// [0, 2, 4, 7, 9, 10, 11, 22, 33, 1000]

 当i=0时,

j的第1次循环:j=arr.length-1,j从数组的最后一项开始和前一项比较大小,当前者小于后者,交换位置。

j的第2次循环:j=arr.length-2,继续和前一项比较大小。

……直至j=1时结束。此时数组的第一项为最小值。

当i=2时,

j的第1次循环:j=arr.length-1,j从数组的最后一项开始和前一项比较大小,当前者小于后者,交换位置。

j的第2次循环:j=arr.length-2,继续和前一项比较大小。

……直至j=2时结束(即比较完第三项和第二项,第一项已经确定,不需要进行比较)。此时数组的第二项为最小值(除去第一项以外)。

继续循环i,i=arr.length-2时。比较j的第arr.length项和第i=arr.length-1项,即可得到最终结果。

  •  优化后的冒泡排序

当待排序的序列为{2,1,3,4,5,6,7,8,9},那么仅仅需要交换第一个和第二个关键字即可。但是前面的算法还是会将循环都执行一遍,造成了多余的计算。

此时我们可以添加一个标记变量flag。

 1 //从小到大
 2 function BubbleSort(arr){
 3     var i,j,temp;
 4     var flag=true;     //flag进行标记
 5     for(i=0;i<arr.length-1&&flag;i++){  //若flag为false则退出循环
 6         flag=false;    //初始化为false
 7         for(j=arr.length-1;j>i;j--){
 8             if(arr[j]<arr[j-1]){ //j为从前往后循环
 9                 temp=arr[j-1];
10                 arr[j-1]=arr[j];
11                 arr[j]=temp;
12                 flag=true; //如果有数据交换则为true
13             }
14         }
15     }
16     return arr;
17 }
18 var arr=[10,7,9,11,22,33,4,2,0,1000];
19 BubbleSort(arr); 20 console.log(arr); // [0, 2, 4, 7, 9, 10, 11, 22, 33, 1000]

标记变量声明时状态为true,进行循环后,标记变量初始化为false状态。当后边的项两两进行比较时,发生交换则将标记变量状态更正为true,如果自始至终标记变量的状态都没有更正为true,说明为有序,则在外层循环的终止判断语句中退出。

优化的关键在于:

在变量i的for循环中,增加了对flag是否为true的判断。通过这种改进,可以避免在有序的情况下进行无意义的循环判断。

  • 时间复杂度

1.最好的情况,即数组有序,可以推断出就是n-1次的比较,时间复杂度为O(n) 
2.当最坏的情况,即数组逆序,第一个数需要排n-1次,第二个数需要排n-2次,第3个数需要排n-3次……这样依次类推,最后一个数只需要排一次,加起来共需要排n(n-1)/2次,所以时间复杂度为O(O^2)

看完大话数据结构,根据自己的理解整理了下,还请大家留下宝贵意见。

 

今天的文章js冒泡排序经典代码_冒泡排序 js分享到此就结束了,感谢您的阅读,如果确实帮到您,您可以动动手指转发给其他人。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:http://bianchenghao.cn/44877.html

(0)
编程小号编程小号
上一篇 2023-09-07
下一篇 2023-09-07

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注