笔试常考排序算法（冒泡选择）

小鱼儿 2022-06-13 07:38 117阅读 0赞

### 冒泡排序    ###

#### 冒泡排序算法的运作如下：（从后往前） ####

*  比较相邻的元素。如果第一个比第二个大，就交换他们两个。
 *  对每一对相邻元素作同样的工作，从开始第一对到结尾的最后
 *  在这一点，最后的元素应该会是最大的数。
 *  针对所有的元素重复以上的步骤，除了最后一个。
 *  持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较  
    
    
    #### Java代码实现 ####

/** * 冒泡排序 * 相邻两个元素相比较，符合条件就交换位置 * 所以循坏一次能找到一个最值 * @param arr * @return */
        public int[] bubbleSort(int[] arr){
            for(int i = 0;i<arr.length-1;i++){
                //-i是因为循坏一次就有一个最值确定了不需要参与比较
                for(int j = 0;j<arr.length-i-1;j++){
                    if(arr[j]>arr[j+1]){
                        int temp = arr[j];
                        arr[j] = arr[j+1];
                        arr[j+1] = temp;
                    }
                }
            }
            return arr;
    
        }

算法时间复杂度：**冒泡排序的最坏时间复杂度为![这里写图片描述][SouthEast]**  
  
![这里写图片描述][SouthEast 1]  
  
**点击图片右击查看图片可看大图**

### 选择排序 ###

/** * 选择排序 * 内循环完成一次最值出现在0角标位置 * 第一次0角标元素与其他元素进行比较，找到最值放在0位置 * 第二次1角标元素与其他元素进行比较，找到最值放在1位置 * 一直到所有元素比较完毕 * @param arr * @return */
        public int[] selectSort(int[] arr){
            //减一是因为最后一个元素不用比较了
            for(int i = 0;i<arr.length - 1;i++){
                //从1开始是因为0和0比较没有意义
                for(int j = 1+i;j<arr.length;j++){
                    if(arr[i]>arr[j]){
                        int temp = arr[i];
                        arr[i] = arr[j];
                        arr[j] = temp;
                    }
                }
            }
            return arr;
        }

**比较操作的时间复杂度为O(n2)。**

![这里写图片描述][SouthEast 2]  
  
**点击图片右击查看图片可看大图**

#### 小结:      冒泡是相邻比较，满足条件就交换      选择是一个和其余的比较，满足条件就交换      相同点是一次外循环完毕都能找到一个最值 ####

[SouthEast]: /images/20220613/dd1ddc0855464e91866eb449da8d8206.png
[SouthEast 1]: /images/20220613/07c573df4bdc447bb913208a284d8a08.png
[SouthEast 2]: /images/20220613/9b94e702bba54fe09f3560e800583026.png