两个数组的最小乘积和&&说明希尔排序对插入排序的优化

插入排序、冒泡排序、选择排序，希尔排序 以leetcode 上的一道中等题来作为练习

1874. 两个数组的最小乘积和

在写代码之前我们先来分析一下题目 题目描述

给定两个长度相等的数组a和b，它们的乘积和为数组中所有的a[i] * b[i]之和，其中0 <= i < a.length。

比如a = [1,2,3,4]，b = [5,2,3,1]时，它们的乘积和为15 + 22 + 33 + 41 = 22
现有两个长度都为n的数组nums1和nums2，你可以以任意顺序排序nums1，请返回它们的最小乘积和。

示例 1:

输入: nums1 = [5,3,4,2], nums2 = [4,2,2,5]
输出: 40
解释: 将 num1 重新排列为 [3,5,4,2] 后，可由 [3,5,4,2] 和 [4,2,2,5] 得到最小乘积和 34 + 52 + 42 + 25 = 40。
示例 2:

输入: nums1 = [2,1,4,5,7], nums2 = [3,2,4,8,6]
输出: 65
解释: 将 num1 重新排列为 [5,7,4,1,2] 后，可由 [5,7,4,1,2] 和 [3,2,4,8,6] 得到最小乘积和 53 + 72 + 44 + 18 + 2*6 = 65。

读完题目之后-思路也是非常清晰

• 要让两个数组每个位置上的乘积最小，首先肯定是要对数组排序
• 排好序之后，我们只需要，让一个数组当中的最小值乘以另外一个数组当中的最大值，这样依次相乘，我们就能够保证最后的和最小
• 废话不多说，我们直接写代码

1·简单插入排序 插入排序思想

• 将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增加1的有序表
• 序列的一个元素肯定是有序的，所以在排序比较是我们要从下标为1的开始和已经有序的元素进行比较，直到有序元素为0
• 在比较的过程中，如果遇到大于已经有序的元素表中第J个元素大于第i个元素那么我们就将第j个位置的元素向后挪动到j+1的位置 nums[j+1]=nums[j];
• 如果小于等于的时候我们跳出循环
• 那最后我们把第i个位置的元素，插入到空出来的的位置–也就是j+1的位置–为什么呢，因为最后我们通过j–遍历，j减去了1，所以要加回来

插入排序时间复杂度和空间复杂度分析

插入排序要两个for循环嵌套，所以时间复杂度为o(n^2),空间复杂度为o(1)

插入排序画图分析

class Solution {
public:
    int minProductSum(vector<int>& nums1, vector<int>& nums2) {
        //插入排序
        //从数组元素中拿一个未排序的数字和已排序的进行比较，找第一个小于其值的位置，放在他的后面，将后面的数字依次向后移动
        for(int i=1;i<nums1.size();i++){
            int temp=nums1[i];
            int j;
            for(j=i-1;j>=0;j--){
                if(nums1[j]>temp){
                    nums1[j+1]=nums1[j];
                }else{
                    break;
                }
            }
            nums1[j+1]=temp;
        }
        for(int i=1;i<nums2.size();i++){
            int temp=nums2[i];
            int j;
            for(j=i-1;j>=0;j--){
                if(nums2[j]>temp){
                    nums2[j+1]=nums2[j];
                }else{
                    break;
                }
            }
            nums2[j+1]=temp;
        }
        long long sum=0;
        for(int i=0,j=nums1.size()-1;j>=0;j--,i++){
            sum+=nums1[i]*nums2[j];
        }
        return sum;
    }
};

希尔排序 算法思想简介

希尔排序又称最小增量排序它也是一种属于插入排序类的方法，在时间效率上对前者有非常大的改进

• 先将整个待排序记录序列分割成为若干个子序列，分别进行插入排序，待整个序列基本有序时，再对全体记录进行一次排序
• 希尔排序的时间复杂度大约是(n^1.3)
• 使用时需注意，增量必须为质数，并且最后一个增量必须为1

画图看下过程吧，还是上面的数字的例子

我们再来写下代码

• 首先我们要进行对应的分组–我们需要先写一个分组函数，对原本的序列进行分组，那在这里我们用一个数组来保存我们的增量

int arr[2]{5，3，1}

• 调用插入排序来进性排序，那插入排序我们需要修改一下，之前是在已经排好序当中我们去比较调换，先我们要一组，一组的进行比较调换，那我们怎么办呢？

在这写代码的时候有可能会陷入一个误区那就是我们一个组一个组的比较，这样是比较麻烦的，那在正确的做法是这样的

• 第一组的第2个值，第二组的第2个值
• 第一组的第3个值，第三组的第3个值

代码

class Solution {
public:
    vector<int> Shell(vector<int>&arr,int gap){
        for(int i=gap;i<arr.size();i++){
            int temp=arr[i];
            int j;
            for(j=i-gap;j>=0;j=j-gap){
                if(arr[j]>temp){
                    arr[j+gap]=arr[j];
                }else{
                    break;
                }
            }
            arr[j+gap]=temp;
        }
        return arr;
    }
public:
    vector<int> Shell_Sort(vector<int> &arr){
        int gap[]={5,3,1};
        for(int i=0;i<sizeof(gap)/sizeof(gap[0]);i++){
            Shell(arr, gap[i]);
        }
        return arr;
    }
public:
    int minProductSum(vector<int>& nums1, vector<int>& nums2) {
        Shell_Sort(nums1);
        Shell_Sort(nums2);
        long long sum=0;
        for(int i=0,j=nums1.size()-1;j>=0;j--,i++){
            sum+=nums1[i]*nums2[j];
        }
        return sum;
    }
};

 int gap[]{7,5,3,1};

当我们这里是7,5,3,1的时候，我们通不过，超时

但当我们改一行代码，我们就可以看到实实在在的改变,当我们将gap设置成500以内的质数的时候，我们发现时间就通过了

int gap[]{499,491,487,479,467,463,461,457,449,443,439
,433,431,421,419,409,401,397,389,383,379,373,367,359,353,349,347,337,331,317,313,311,307,293,283,281,277,271,269,263,257
,251,241,239,233,229,227,223,211,199,197,193,191,181,179,173,167,163,157,151,149,139,137,131,127,113,109,107,103,101,97,
89,83,79,73,71,67,61,59,53,47,43,41,37,31,29,23,19,17,13,11,7,5,3,1};

2·使用系统的快速排序

• 首先我们使用快速排序先来做一次，第一次孩子为了通过，使用了系统的的快速排序，我们先来看下最终通过的时间😊

代码

class Solution {
public:
    int minProductSum(vector<int>& nums1, vector<int>& nums2) {
        //词题直接排序，从小到大，然后依次相乘，再相加
        sort(nums1.begin(),nums1.end());
        sort(nums2.begin(),nums2.end());
        reverse(nums2.begin(),nums2.end());
        int sum=0;
        for(int i=0;i<nums1.size();i++)
        {
            sum+=nums1[i]*nums2[i];
        }
        return sum;
    }
};

通过时间

3·冒泡排序

首先介绍一下冒泡排序的算法思想

1. 比较相邻位置的元素，如果第一个比第二个大，就交换他们两个的值
2. 对每一对相邻元素做同样的事情，从开始第一对到最后一对，那在这里有一个要注意的点就是，因为你是成对出现的，比较的是相邻的，所以遍历的时候，最后一个值是不能作为起始值，不然会造成数组越界,同时对已经排好序的就不用再排了，所以在这里循环结束的条件是 j
3. 持续上述的 *** 作，直到没有要比较的数字
4. 冒泡排序时间复杂度为o(n^2)因为双重for循环，空间复杂度为o(1),不需要额外空间

代码-直接超时

class Solution {
public:
    int minProductSum(vector<int>& nums1, vector<int>& nums2) {
        int sum=0;
        int len1=nums1.size(),len2=nums2.size();
        //先来将第一个数组有小到达排序
        for(int i=0;i<len1;i++){
            for(int j=0;j<len1-i-1;j++){
                if(nums1[j]>nums1[j+1]){
                    int temp=nums1[j];
                    nums1[j]=nums1[j+1];
                    nums1[j+1]=temp;
                }
            }
        }
        //将第二个数组从大到小排序
        for(int i=0;i<len2;i++){
            for(int j=0;j<len2-i-1;j++){
                if(nums2[j]<nums2[j+1]){
                    int temp=nums2[j];
                    nums2[j]=nums2[j+1];
                    nums2[j+1]=temp;
                }
            }
        }
        //排好序之后，直接便利求最小和
        for(int i=0;i<len1;i++){
            sum+=nums1[i]*nums2[i];
        }
        return sum;
    }
};

超时

4·选择排序-我来了

先理解算法思想

1. 首先在排序中找到最小元素，放到序列的起始位置
2. 再从剩余的部分继续找
3. 重复2的步骤直到结束
   时间复杂度一依旧是o（N^2）,估计过不了，不过没关系，我们自己写着练习嘛

代码-依旧超时

class Solution {
public:
    int minProductSum(vector<int>& nums1, vector<int>& nums2) {
        int sum=0;
        int len1=nums1.size(),len2=nums2.size();
        //先来将第一个数组由小到达排序
        for(int i=0;i<len1;i++){
            for(int j=i;j<len1;j++){
                if(nums1[i]>nums1[j]){
                    int temp=nums1[j];
                    nums1[j]=nums1[i];
                    nums1[i]=temp;
                }
            }
        }
        //将第二个数组从大到小排序
        for(int i=0;i<len2;i++){
            for(int j=i;j<len2;j++){
                if(nums2[i]<nums2[j]){
                    int temp=nums2[j];
                    nums2[j]=nums2[i];
                    nums2[i]=temp;
                }
            }
        }
        //排好序之后，直接便利求最小和
        for(int i=0;i<len1;i++){
            sum+=nums1[i]*nums2[i];
        }
        return sum;
    }
};

#include 
#include 
using namespace std;
class Solution {
public:
    /**
     * 冒泡排序-时间复杂度位 o(n^2)-空间复杂度位o(1)
     * 1·比较相邻元素，如果第一个比第二个大，就交换他们两个
     * 2·对每一对相邻元素做同样的工作，从开始第一个对到结尾最后一对。做完这些元素之后，最后的元素就是最大的值，针对所有的元素重复以上步骤，除了最后一个
     * 3·持续每次对上面元素执行 *** 作，直到没有比较的数字
     * @param nums
     * @return
     */
    static vector<int> Bubbling_sort(vector<int>&nums){
        for(int i=0;i<nums.size();i++){
            //在这里有一个注意的点，j
            for(int j=0;j<nums.size()-i-1;j++){
                if(nums[j]>nums[j+1]){
                    int temp=nums[j];
                    nums[j]=nums[j+1];
                    nums[j+1]=temp;

                }
            }
        }
        return nums;
    }

    /**
     * 选择排序-时间复杂度为o(n^2)-空间复杂度为o(1)
     * 1·首先在排序中找到最小元素，方到序列起始位置
     * 2·再从剩余的部分继续找
     * 3·重复第2步直到结束
     * @param nums
     * @return
     */
    static vector<int> Selection_sort(vector<int>&nums) {
        for(int i=0;i<nums.size();i++){
            for(int j=i+1;j<nums.size();j++){
                if(nums[j]<nums[i]){
                    int temp=nums[i];
                    nums[i]=nums[j];
                    nums[j]=temp;
                }
            }
        }
        return nums;
    }
    /**
     *插入排序-插入排序的时间复杂度为o(n^2)
     * 1·将待排序序列的第一个元素看做一个有序序列，把第二个元素到最后一个元素当成为排序序列
     * 2·从头到尾依次扫描未排序的序列，将扫描大到的每个元素插入有序序列的适当位置，如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面
     * @param nums
     * @return
     */
    static vector<int> Insertion_sort(vector<int>&nums){
        for(int i=1;i<nums.size();i++){
            //前面已经有序的元素
            int orderly=i-1;
            //定义一个变量记录当前元素得值
            int current=nums[i];
            //用来判断是否需要排序
            while(orderly>=0&&current<nums[orderly]){
                //如果需要交换则将前面得元素依次向后移动
                    nums[orderly+1]=nums[orderly];
                        orderly--;

            }
            //将要移动位置赋值为 记录得要交换得值
            nums[orderly+1]=current;
        }
        return nums;
    };
    //打印排序结果
    static void Print_sort(vector<int>&nums){
        for (int num: nums)cout << num << " ";
        cout<<endl;
        cout<<"_____________________"<<endl;
    }
};
int main() {
    int n;
    cin>>n;
    vector<int>arr;
    //输入测试数据
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        arr.push_back(x);
    }

   /* cout<<"冒泡排序"<

    cout<<"插入排序"<<endl;
    Solution::Insertion_sort(arr);
    Solution::Print_sort(arr);
    return 0;
}