JavaScript 数组中的冒泡排序和选择排序

分手后的思念是犯贱 2023-07-17 15:30 25阅读 0赞

# 冒泡排序 #

### 原理 ###

相邻的两个单位，比较存储的数据
    如果第一个单元的数据较大，就将两个相邻单元交换存储数据

### 过程 ###

从起始单元开始比较,第一次循环,会选择出一个最大值,放在数组所有单元的最后
    之后,每次循环,都会比较出一个本次循环的最大值,放在当前参与比较单元的最后
    之前已经比较选出的单元,不会参与下一次比较

### 排序的优化 ###

1. 单次循环,最后一个单元,通过倒数第二个单元,参与比较
           最后一个单元,就不参与单次循环
    2. 之前比较出的最大值,不再参与下一次的比较
    3. n个单元,只要循环比较n-1次,最后就一个单元时,不要再循环比较

### 核心 ###

交换存储的数据：
          两个相邻的单元,比较数据大小,第一个单元数值较大,就交换两个单元存储的数据

### 实例 ###

# 选择排序 #

### 原理 ###

假设起始位置为最小值，与后面的值逐一比较
    如果后面的值小于最小值，将索引值赋值给最小值的索引
    交换最小值与起始位置值

### 过程 ###

先定义循环的起始位置默认为最小值所在位置
    
    从起始位置下一个位置开始,执行循环
    如果有位置上的数值,小于,存储索引位置上的数值
    
    循环结束,比较存储的索引,是否是起始位置索引
    如果不是,就交换两个位置上的数值
    会将本次循环的最小值,放置在循环的起始位置上
    
    再执行多次循环,完成排序

### 排序优化 ###

1. 之前比较的数值不参与一次标记
    2. n个单元,只要比较n-1次

### 核心 ###

找到最小值的索引,与起始位置交换数值
    先找索引 在交换数值

### 实例 ###

// 选择排序
    // 从起始位置开始,找最小的数值所在的索引下标
    // 如果最终存储的索引下标,不是起始位置,就与起始位置交换存储数据
    // 执行一次循环,会将最小值存储在起始位置上
    // 
    // 下一次循环,之前的起始位置,不再参与循环
    // 
    // 外层循环:实现循环次数,是数组单元个数-1
    // 内层循环:每次循环,将本次循环找出来的最小值,与起始位置进行数值交换
    // 先默认起始位置的数值为最小值,存储起始位置的索引值
    // 之后从起始位置的下一个位置开始循环,生成之后的所有索引下标,
    // 如果之后位置上的数值,小于存储的索引位置的数值,就存储这个数值的索引
    // 循环结束,变量中存储本次内层循环选择出的最小值的索引下标
    // 进行比较判断,如果这个索引值,不是起始索引值,就交换两个索引值对应的数据
    
    // 程序的优化:
    // 外层优化:之前比较出的数值,不参与下一次的比较
    // 内层优化:从起始位置的下一个位置开始循环
    
    var arr = [3,44,38,5,47,25,36,2,79,8,1];
    
    // 外层循环,实现排序循环次数,次数是单元个数 -1
    for(var j = 0 ; j <= arr.length-1 -1 ; j++){ 
        // 先默认起始位置就是最小值位置,存储起始位置的索引,也就是 j
        // 之前的起始位置,不参与下一次循环
        var min = j;
        
        // 默认的最小值位置是当前循环的起始位置,是j
        // 比较,要从下一个位置开始,内层循环起始,是比较的起始位置+1开始循环 
        for(var i = j+1 ; i <= arr.length-1 ; i++){ 
            // 如果有单元的数值,小于存储的索引对应的数值
            if(arr[min] > arr[i]){ 
                // 变量中,存储当前较小值的索引下标
                // 不是做数据交换,是存储这个数值位置的索引下标
                min = i;
            }
        }
        // 内层循环执行完毕,存储的索引下标如果不是起始的索引j
        // 就交换 min中存储的索引下标对应的数值 和 j索引下标应的数值
        if(min != j){ 
            var m = 0;
            m = arr[j];
            arr[j] = arr[min];
            arr[min] = m;
        }
    }
    
    console.log(arr);

# 冒泡排序与选择排序的区别 #

### 选择排序: ###

如果发生大小顺序问题，只是做赋值索引的操作
    等循环完成，执行判断，做一次数据交换

### 冒泡排序: ###

每次发生大小顺序问题，都要执行数据交换操作
    执行数据交换的次数，高于选择排序
    
    执行数据交换的操作比较繁琐，执行次数过多，执行效率低。