一起学算法（冒泡排序篇）

小灰灰 2023-10-14 10:08 2阅读 0赞

### 1.概念 ###

冒泡排序（Bubble Sort）又称泡式排序，是一种简单的排序算法

**核心思想**：它重复地走访过要排列的次数，一次比较两个元素，如果它们的顺序错误就把它们交换过来，走访数列的工作是重复地进行交换直到不需要交换为止，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或者降序排列），就像水中的气泡会冒起来一样

**步骤：**

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

![a7acf5f8ed0c4d38adbc823ffe425c80.png][]

想必一幅图大家已经基本看懂冒泡排序的原理

**具体实现**：使用双重循环，外层循环控制循环的次数，内层循环进行数字的比较，内层每一次循环结束之后，都要找出最大的数据，放到参与比较的这堆数据的最右边，下次循环不再比较该数

public void bubbleSort(int[] arr) {
            //入参进行判断
            if (arr == null || arr.length == 0) {
                return;
            }
            //每次确定无序列表中最大的，从右往左
            for (int i = 1; i < arr.length; i++) { // 表示进行的轮数
                //比较的次数是数组的总长度减去已经排好序的长度
                for (int j = 0; j < arr.length - i; j++) { 
                   //两两进行比较，直到长度完结
                    if (arr[j] > arr[j + 1]) {
                        int temp = arr[j];
                        arr[j] = arr[j + 1];
                        arr[j + 1] = temp;
                    }
                }
            }
        }

#### leetcode题单： ####

##### [最后一块石头][Link 1] #####

//冒泡排序
        public void bubbleSort(int [] nums){
            if(nums==null||nums.length==0){
                return;
            }
            for (int i =1; i <nums.length; i++) {
                for (int j = 0; j<i ; j++) {
                    if(nums[j]>nums[j+1]){
                        int temp=nums[j];
                        nums[j]=nums[j+1];
                        nums[j+1]=temp;
                    }
                }
            }
        }
    
        public int lastStoneWeight(int[] stones) {
            if(stones==null||stones.length==0){
                return 0;
            }
            int n=stones.length-1;
            for (int i =0; i<stones.length-1; i++) {
                 bubbleSort(stones);
              if (stones[n - 1] == 0) break;           //说明最多只剩一块石头
                 stones[n] -= stones[n - 1];          //两种不同情况使用同一表达式处理
                 stones[n - 1] = 0;   
            }
            return stones[n];
        }

##### [元素计数][Link 2] #####

class Solution {
        //快排   冒泡排序也可以做
        public void fastSort(int [] num,int left,int right){
            if(left>=right){
                return;
            }
            if(num==null||num.length==0){
                return;
            }
            int povit=num[left];
            int i=left;
            int j=right;
            while(i<j){
                while(i<j&&num[j]>povit){
                    j--;
                }
                if(i<j){
                    num[i++]=num[j];
                }
                while(i<j&&num[i]<povit){
                    i++;
                }
                if(i<j){
                    num[j--]=num[i];
                }
            }
            num[i]=povit;
            fastSort(num,i+1,right);
            fastSort(num,left,i-1);
        }
        public int countElements(int[] nums) {
          if(nums==null||nums.length==0){
              return 0;
          }
          //将原数组进行排序
          fastSort(nums,0,nums.length-1);
          int ans=0;
            for (int i = 0; i < nums.length; i++) {
                if(nums[i]==nums[0]||nums[i]==nums[nums.length-1]){
                    continue;
                }
                ans++;
            }
            return ans;
        }
    }

##### [合并两个有序数组][Link 3] #####

class Solution {
        public void merge(int[] nums1, int m, int[] nums2, int n) {
    int[] arr = new int[m + n];
            int i = 0;
            int j = 0;
            int index = 0;
            // 进行比较
            while (i < m && j < n) {
                if (nums1[i] < nums2[j]) {
                    arr[index++] = nums1[i];
                    i++;
                } else {
                    arr[index++] = nums2[j];
                    j++;
                }
            }
    
            while (i < m) {
                arr[index++] = nums1[i];
                i++;
            }
            while (j < n) {
                arr[index++] = nums2[j];
                j++;
            }
            // 反向填充
            for (int k = 0; k < m + n; k++) {
                nums1[k] = arr[k];
            }
    
    
        }
    }

##### [数组中两元素的最大乘积][Link 4] #####

class Solution {
        //快排   冒泡排序也同样可以做
        public void fastSort(int [] num,int left,int right){
            if(left>=right){
                return;
            }
            if(num==null||num.length==0){
                return;
            }
            int povit=num[left];
            int i=left;
            int j=right;
            while(i<j){
                while(i<j&&num[j]>povit){
                    j--;
                }
                if(i<j){
                    num[i++]=num[j];
                }
                while(i<j&&num[i]<povit){
                    i++;
                }
                if(i<j){
                    num[j--]=num[i];
                }
            }
            num[i]=povit;
            fastSort(num,i+1,right);
            fastSort(num,left,i-1);
        }
        public int maxProduct(int[] nums) {
         if(nums==null||nums.length==0){
             return 0;
         }
         fastSort(nums,0,nums.length-1);
         return (nums[nums.length-1]-1)*(nums[nums.length-2]-1);
        }
    }

[a7acf5f8ed0c4d38adbc823ffe425c80.png]: https://img-blog.csdnimg.cn/a7acf5f8ed0c4d38adbc823ffe425c80.png
[Link 1]: https://leetcode.cn/problems/last-stone-weight/
[Link 2]: https://leetcode.cn/problems/count-elements-with-strictly-smaller-and-greater-elements/
[Link 3]: https://leetcode.cn/problems/merge-sorted-array/
[Link 4]: https://leetcode.cn/problems/maximum-product-of-two-elements-in-an-array/