JS 冒泡排序详解

ybzy 2020-03-29 原文

JS 冒泡排序详解

冒泡排序原理：比较相邻两个数的大小，如果第一个数大于第二个数，那么交换位置，从第一位数开始，对后面每一对相邻的数据进行同样的比较和交换，直到最后没有任何一位需要进行比较大小和交换；

思路演算：

arr = [2, 5, 6, 3, 1];
//两两比较大小，如果大于那么交换
//2 > 5 ?  不交换，arr = [2, 5, 6, 3, 1]
//5 > 6 ?  不交换，arr = [2, 5, 6, 3, 1]
//6 > 3 ?  交换，arr = [2, 5, 3, 6, 1]
//6 > 1 ?  交换，arr = [2, 5, 3, 1, 6]

第一轮的数据两两比较大小，交换位置就完成了，最终数组中最大的数据 6 被交换到了最后，沉入数组末尾

//2 > 5 ?  不交换，arr = [2, 5, 3, 1, 6]
//5 > 3 ?  交换，arr = [2, 3, 5, 1, 6]
//5 > 2 ?  交换，arr = [2, 3, 1, 5, 6]

第二轮的数据两两比较大小，交换位置就完成了，最终数组中第二大的数据 5 被交换到了数组后面

//2 > 3 ?  不交换，arr = [2, 3, 1, 5, 6]
//3 > 1 ?  交换，arr = [2, 1, 3, 5, 6]

第三轮的数据两两比较大小，交换位置就完成了

//2 > 1 ?  交换，arr = [1, 2, 3, 5, 6]

第四轮的数据两两比较大小，交换位置就完成了

经过四轮的数据比较，显而易见，数据已经完成了升序排列。

从上面的演算中发现规律：
　　数组的长度 arr.length = 5，循环了4轮就完成了排序，
　　每一轮的循环 进行了 两两比较大小，
　　并且每一轮的中的 两两比较 次数都比前一次少，
　　直到没有两个数据可以拿来比较为止。

1 for(var i = 0; i < arr.length - 1; i++){
　　//表示要进行几轮比较
2 }

1 for(var i = 0; i < arr.length - 1; i++){
2      for(var j = 0; j < arr.length - 1 - i;j++){
3         // 每一轮的数据比较都是 从数组的 下标0 开始， 
          // 每一轮，两两比较的次数都比上一轮少1 次 
          // 当 i=0 的时候， j < 5 - 1 - 0 即 j < 4
　　　　　　// 当 i=1 的时候， j < 5 - 1 - 1 即 j < 3
　　　　　　// 依次类推
4     }        
5 }

 1 for(var i = 0; i < arr.length - 1; i ++){
 2      for(var j = 0; j < arr.length - 1 - i: j++){
　　　　　　　// 定义一个临时变量，用来存储较大的那个数据
 3          var temp;
　　　　　　　// 比较数组中相邻的那个数，如果第一个数比第二个数大，那么
 4          if(arr[j] > arr [j+1]){
　　　　　　　　　// 将较大的数 存放在 temp 变量中
 5              temp = arr[j];
　　　　　　　　　// 将 较小的数据 赋值给 前一位
 6              arr[j] = arr[j+1];
　　　　　　　　　// 将 存放了较大数据的临时变量 赋值给 后一位，  完成数据的交换位置
 7              arr[j+1] = temp;  
 8         }
 9     }  
10 }