【算法集训】基础算法：基础排序 - 冒泡排序

一、基本理解

贴上��解，更容易理解代码：https://visualgo.net/zh/sorting

冒泡排序(Bubble Sort)又称为泡式排序，是一种简单的排序算法。

核心思想：

它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就像水中的气泡会冒起来一样。

二、题目练习

1046. 最后一块石头的重量

// 冒泡排序void BubbleSort(int * n, int size) {    // 从右往左先从最大的开始确定,所以从最后一个开始    for(int i = size - 1; i > 0; --i) {        for(int j = 0; j  n[j + 1]) {                int tmp = n[j];                n[j] = n[j + 1];                n[j + 1] = tmp;            }        }    }}int lastStoneWeight(int* stones, int stonesSize) {    while(stonesSize > 1) {        BubbleSort(stones, stonesSize);        int x = stones[stonesSize - 1];        int y = stones[stonesSize - 2];        // 题目给的两种粉碎条件        if(x == y) {            stonesSize -= 2;        }else {            int z = x - y;            stones[stonesSize - 2] = z;            stonesSize -= 1;        }    }    // 是否存在石头    return stonesSize == 0 ? 0 : stones[0];}

2148. 元素计数

void BubbleSort(int * n, int size) {    for(int i = size - 1; i > 0; --i) {        for(int j = 0; j  n[j + 1]) {                int tmp = n[j];                n[j] = n[j + 1];                n[j + 1] = tmp;            }        }    }}int countElements(int* nums, int numsSize) {    BubbleSort(nums, numsSize);    int ans = 0;    for(int i = 1; i  
88. 合并两个有序数组
 
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {    for(int i = 0; i  nums1[j + 1]) {                int t = nums1[j];                nums1[j] = nums1[j + 1];                nums1[j + 1] = t;            }        }    }}
 
1464. 数组中两元素的最大乘积
 
int maxProduct(int* nums, int numsSize) {    for(int i = 0; i  nums[j + 1]) {                int temp = nums[j];                nums[j] = nums[j + 1];                nums[j + 1] = temp;            }        }    }    return (nums[numsSize - 1] - 1) * (nums[numsSize - 2] - 1);}