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

2023-12-15 14:08:29

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;
}

文章来源:https://blog.csdn.net/pancodearea/article/details/135014483
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。