基础算法(3):排序(3)插入排序

1.插入排序实现

     插入排序的工作原理是：通过构建有序序列，对于未排序数据，在已经排序的序列从后向前扫描，找到位置并插入，类似于平时打扑克牌时，将牌从大到小排列，每次摸到一张牌就插入到正确的位置。

     实现逻辑：

  （1）从第一个元素出现，该元素认为已经被排好序

  （2）取出下一个元素，在已经排序的序列中从后向前扫描

    (3）如果扫描到某个元素大于取出的新元素，将该元素移到下一个位置

  （4）重复（3），直到找到已排序的元素小于或者等于新元素的位置

  （5）将新元素插入到该位置后面

  （6）重复（2）-（5）

     代码实现：

void insertSort(int* arr,int len)
{for(int i=i;i<len;i++){int cur=arr[i];int j=i-1;while(j>=0&&arr[j]>cur){arr[j+1]=arr[j];j--;}arr[j+1]=cur;}
}

2.插入排序的时间复杂度

     问题规模仍然为n，最好情况是序列是升序，这样只需要比较n-1次，最坏情况是序列是降序，需要比较n(n-1)次，所以时间复杂度为O(n^2)

3.leetcode题目

3.1 删除某些元素后的数组均值

void insertionSort(int *a ,int n){int i,j;int tmp ;for(i = 1; i < n; ++i){for(j = i - 1; j>=0; --j){if(a[j] > a[j+1]){tmp = a[j];a[j] = a[j+1];a[j+1] = tmp; }}}
}
double trimMean(int* arr, int arrSize){insertionSort(arr,arrSize);int cnt = arrSize / 20;double count = 0;for(int i = cnt; i < arrSize - cnt; ++i){count += arr[i];}return count /  (arrSize - 2*cnt);
}

3.2  去掉最低工资和最高工资后的工资平均值

double average(int* salary,int salarySize){for (int i = 1; i < salarySize; i++) {int tmp = salary[i];int j = i - 1;for (; j >= 0 && tmp < salary[j]; j--) {salary[j + 1] = salary[j];}salary[j + 1] = tmp;}double ans=0;for(int i=1;i<salarySize-1;i++){ans+=salary[i];}return ans/(salarySize-2); 
}

3.3 学生分数的最小差值

int minimumDifference(int* nums, int numsSize, int k) {for (int i = 1; i < numsSize; i++){int tmp = nums[i];int j = i - 1;for (; j >= 0 && tmp < nums[j]; j--) {nums[j + 1] = nums[j];}nums[j + 1] = tmp;}int ret=100000;for(int i=0;i+k-1<numsSize;i++){int ans=nums[i+k-1]-nums[i];if(ans<ret){ret=ans;}}return ret;
}