勇闯BAT 冒泡排序 Top K问题

柔光的暖阳◎ 2023-01-19 11:50 104阅读 0赞

该算法的核心思想是**将无序表中的所有记录**，**通过两两比较关键字**，**得出升序序列或者降序序列**。

*  **总共2层循环**
 *  外面的一层代表冒泡的趟数，一趟可以筛选出一个最大值或者最小值，所以n个数的数组，需要n-1躺，因为i从0开始，即 `for(int i = 0 ;i<arr.length-1;i++)`
 *  里面的一层代表对比次数，n个数的数组，第一躺交换n-1次，选出一个最大值，第二趟交换n-2次，因为已经筛选出一个最大值了，只需比较后边的即可，故：`for(int j = 0 ;j<arr.length-i-1;j++)`
 *  相邻2个数比较，交换位置，这里跟趟数没关系，都是j的事情
    
        if(arr[j]>arr[j+1]){ 
          int temp=arr[j];
          arr[j]=arr[j+1];
          arr[j+1]=temp;
        }
 *  **有序是在数组的最右侧开始有序，注意是最右侧**

**每趟选出一个最大值**  
![20160316103848750][]

//N个数字冒泡排序，总共要进行N-1趟比较，每趟的排序次数为(N-i)次比较
        public static void bubbleSort(int[] arr) { 
            //一定要记住判断边界条件，很多人不注意这些细节，面试官看到你的代码的时候都懒得往下看，你的代码哪个项目敢往里面加？
            if (arr == null || arr.length < 2) { 
                return;
            }
            //需要进行arr.length趟比较
            for (int i = 0; i < arr.length - 1; i++) { 
                //第i趟比较
                for (int j = 0; j < arr.length - i - 1; j++) { 
                    //开始进行比较，如果arr[j]比arr[j+1]的值大，那就交换位置
                    if (arr[j] > arr[j + 1]) { 
                        int temp = arr[j];
                        arr[j] = arr[j + 1];
                        arr[j + 1] = temp;
                    }
                }
    
            }
            System.out.println("最终得出的数组为：");
            for (int k = 0; k < arr.length; k++) { 
                System.out.print(arr[k] + " ");
            }
        }

**拓展Top K问题**，每次冒泡选出一个最大值，则冒K次泡即可  
**有序是在数组的最右侧开始有序，注意是最右侧**

for (int i =0;i<k;i++){  // 冒几次泡 即取几次最大的值 
        for(int j=0;i<length-i-1;j++) { 
        // 交换
     }
    }

[20160316103848750]: /images/20221021/5660fc598fa5456991adcb0923926fea.png