一、基本理解
插入排序(nsertion Sort)，一般也被稱為直接插入排序，是一種簡單直觀的排序算法。
**工作原理：**將待排列元素劃分為「已排序」和「未排序」兩部分，每次從「未排序的」元素中選
擇一個插入到「已排序的」元素中的正確位置。
二、題目練習
1619. 刪除某些元素后的數組均值
void insertSort(int * n, int size) {int i, j;for(i = 1; i < size; ++i) {int temp = n[i];for(j = i - 1; j >= 0; --j) {if(temp < n[j]) {n[j + 1] = n[j];}else {break;}}n[j + 1] = temp;}
}double trimMean(int* arr, int arrSize) {insertSort(arr, arrSize);int cnt = arrSize / 20;double ans = 0;for(int i = cnt; i < arrSize - cnt; ++i) {ans += arr[i];}return ans / (arrSize - 2*cnt);
}
1491. 去掉最低工資和最高工資后的工資平均值
// 選擇排序
void insertSort(int * a, int n) {// 正序出發for(int i = 1; i < n; ++i) {int temp = a[i];int j = i - 1;while(j >= 0 && temp < a[j]) {a[j + 1] = a[j];j--;}a[j + 1] = temp;}
}double average(int* salary, int salarySize) {insertSort(salary, salarySize);double ans = 0;for(int i = 1; i < salarySize - 1; ++i) {ans += salary[i];}return ans / (salarySize - 2);
}
1984. 學生分數的最小差值
void insertSort(int * a, int n) {int i, j;for(i = 1; i < n; ++i) {int temp = a[i];for(j = i - 1; j >= 0; --j) {if(temp < a[j]) {a[j + 1] = a[j];} else {break;}}a[j + 1] = temp;}
}int minimumDifference(int* nums, int numsSize, int k) {insertSort(nums, numsSize);int ret = 100001;for(int i = 0; i + k - 1 < numsSize; ++i) {int cha = nums[i + k - 1] - nums[i];if(ret > cha) {ret = cha;}}return ret;
}
