【算法集訓】基礎算法：基礎排序

一、基本理解

貼上圖解，更容易理解代碼：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 < i; ++j) {if(n[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 < i; ++j) {if(n[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 < numsSize - 1; ++i) {if(nums[i] == nums[0] || nums[i] == nums[numsSize - 1]) {continue;}ans ++;}return ans;
}

88. 合并兩個有序數組

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {for(int i = 0; i < n; ++i) {nums1[m + i] = nums2[i];}for(int i = 0; i < nums1Size - 1; ++i) {for(int j = 0; j < nums1Size - 1 - i; ++j) {if(nums1[j] > 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 < numsSize - 1; ++i) {for(int j = 0; j < numsSize - 1 - i; ++j) {if(nums[j] > 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);
}