活动地址：21天学习挑战赛

文章目录

一、插入排序的基本思想

二、直接插入排序法

1.算法步骤

2.排序过程

 3.算法实现

4.复杂度分析

三、每日一练

解题思路

解题代码

---

一、插入排序的基本思想

        每一趟将一个待排序的记录，按其关键字的大小插入到已经排好序的一组记录的适当位置，直到所有待排序记录全部插入为止。例如抓牌，每次从牌堆里面抓取一张插入到合适的位置，直到抓完牌为止，即可得到一个有序的牌。

 

二、直接插入排序法

        直接插入排序（Straight Insertion Sort）是一种最简单的排序方法，其基本操作是将一条记录插入到已经排序好的有序表中，从而得到一个新的、记录数量增1的有序表。

1.算法步骤

1. 设待排序的记录存放在数组r[1...n]中
2. 循环n-1次，每次使用顺序查找法，查找r[i](i=2,...n)在已经排好序的序列r[1...i-1]中的插入位置，然后将r[i]插入到飙车为i-1的有序序列r[1...i-1]中，直到将r[n]插入到表长为n-1的有序序列r[1,...,n-1]中，最后得到一个表长为n的有序序列

2.排序过程

已知待排序记录的关键字序列为：{15，26，2，3，5，36，27，4，46，48，50，38，44，19，47}

利用直接排序法将其进行排序的过程如下图所示：

 3.算法实现

public class DayTwo {
    public static void main(String[] args) {
        DayTwo d=new DayTwo();
        int []a={15,26,2,3,5,36,27,44,46,48,50,38,4,19,47};
        System.out.println("原数组为：");
        d.printArray(a);
        System.out.println("\n插入排序后：");
        d.InsertSort(a);
        d.printArray(a);
    }
    public void InsertSort(int []arr){
        //第一个记录本身就是有序的，所以从第二个元素开始
        for(int i=1;i
            int temp=arr[i];//使用临时变量存储待插入的值
            int j=i-1;
            while(j>=0&&arr[j]>temp){
                arr[j+1]=arr[j];//当前面的数比待插入的数要大时则逐个后移
                j--;
            }
            //当找到第一个小于待插入的数字时，需要将待插入数字插入到它的后一个位置上,故为j+1
            arr[j+1]=temp;
        }
    }
    public void printArray(int []arr){
        for(int i=0;i
            System.out.print(arr[i]+" ");
        }
    }
}

执行结果

4.复杂度分析

（1）时间复杂度

从时间来看，排序的基本操作为：比较两个关键字的大小和移动记录。对于其中的某一个趟插入排序，代码中内层的循环次数取决于待插入记录关键字与前i-1个记录的关键字之间的关系。

其中，最好的情况下（正序），是比较一次不移动元素；最坏的情况下（逆序），是比较i次，依次同前面的i-1个记录进行比较，移动i+1次。对于整个排序过程需要执行n-1趟，最好情况下，总的比较次数达到最小值n-1，记录不需要移动；最坏的情况下，总的关键字比较次数KCN和记录移动次数RMN均达到最大值，分别为：KCM=n^2/2  RMN=n^2/2  若待排序序列中出现各种可能排列的概率相同，则可取上述最好的情况和最坏的情况地平均情况来考虑。

最平均情况下，直接插入排序关键字的比较次数和记录移动次数均约为n^2/4

综上所述，直接插入排序的时间复杂度为O(n^2)

（2）空间复杂度

直接插入排序只需要一个存放记录的临时变量，所以空间复杂度为O(1)

三、每日一练

删除排序数组中的重复项

     给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。

    由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。

将最终结果插入 nums 的前 k 个位置后返回 k 。不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

示例1：

输入：nums = [1,1,2]
输出：2, nums = [1,2,_]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

示例2：

输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

解题思路

双指针法：右指针往右移动，左指针在与右指针比对中，出现新元素时右移动

• 如果右指针指向的值等于左指针指向的值，说明遇到了重复的元素，则左指针不动，右指针继续右移去找新元素
• 如果右指针指向的值不等于左指针指向的值，说明出现了新的元素，那么左指针往右移动一步，然后再把右指针所指向的值赋值给左指针所对应的空间，从而覆盖掉原来的值，实现原地修改且不重复
• 最后返回左指针移动的步数，但要加1，因为左指针是从0开始的，但第一个元素肯定是要保留在原来数组中的，所以自然数组总长度等于左指针移动步数，即新元素出现的个数再加上第一个元素

解题代码

class Solution {
    public int removeDuplicates(int[] nums) {
       if(nums==null||nums.length==0) return 0;
       int left=0;
       for(int right=1;right
          if(nums[right]!=nums[left]){
              nums[++left]=nums[right];
           }
        }
        return ++left;
    }
}

 提交结果