【万人千题】《算法零基础100讲》(第38讲) 排序进阶 - 希尔排序【题解】

【万人千题】《算法零基础100讲》(第38讲) 排序进阶 - 希尔排序【题解】

目录

传送门

 课后习题

排序数组

多数元素

 存在重复元素

 最大间距

 按奇偶排序数组

三角形的最大周长

---

传送门

三角形的最大周长

今天学习的还是排序哈(这排序算法不是一般的多)，希尔排序，以前没接触过，今天算是第一次接触这个名字，直接来看英雄哥的代码，看的我一脸糊涂，后来去网上看了看大致思路重新来看就明白很多。对于这些抽象的，多画图帮助自己理解

 

例如对于序列：1 4 2 6 5 3 0 7

初始时增量gap = N/2 = 4

 每次缩小增量

 当增量减至 1 时，整个序列恰被分成一组，算法便终止。

 

代码实现

 void ShellSort(int *nums,int numsSize){
     int i,j,tem,gap;         //gap 是每隔gap位作为取一个数
     for(gap=numsSize/2;gap>0;gap/=2){  //增量每次减半
         for(i=gap;i=gap;j-=gap){
                 if(tem < nums[j-gap]){
                     nums[j] = nums[j-gap];  // 大于tem的往后移
                 }
                 else        //前面没有比tem大的数了
                    break;
             }
             nums[j] = tem;
         }
     }
 }

 课后习题 排序数组

912. 排序数组https://leetcode-cn.com/problems/sort-an-array/

 题目描述：

给你一个整数数组 nums，请你将该数组升序排列。

又是这题哈，今天换希尔排序来做

 void ShellSort(int *nums,int numsSize){
     int i,j,tem,gap;         //gap 是每隔gap位作为取一个数
     for(gap=numsSize/2;gap>0;gap/=2){  //增量每次减半
         for(i=gap;i=gap;j-=gap){
                 if(tem < nums[j-gap]){
                     nums[j] = nums[j-gap];  // 大于tem的往后移
                 }
                 else        //前面没有比tem大的数了
                    break;
             }
             nums[j] = tem;
         }
     }
 }
int* sortArray(int* nums, int numsSize, int* returnSize){
    ShellSort(nums,numsSize);
    *returnSize = numsSize;
    return nums;
}

多数元素

 169. 多数元素https://leetcode-cn.com/problems/majority-element/

好多是做过的题目，这里就直接贴代码了

int majorityElement(int* nums, int numsSize){
    int value = nums[0],count = 1;
    for(int i=1;i 
 存在重复元素 
217. 存在重复元素https://leetcode-cn.com/problems/contains-duplicate/
 
 
 
bool cmp(void *a,void *b){
    return *(int*)a > *(int*)b;
}
bool containsDuplicate(int* nums, int numsSize){
    qsort(nums,numsSize,sizeof(int),cmp);
    for(int i=1;i 
 最大间距 
164. 最大间距https://leetcode-cn.com/problems/maximum-gap/
 
bool cmp(void *a,void *b){
    return *(int*)a > *(int*)b;
}
int maximumGap(int* nums, int numsSize){
    if(numsSize < 2) return 0;
    qsort(nums,numsSize,sizeof(int),cmp);   //排序
    int res = INT_MIN;
    for(int i=1;i res)
            res = nums[i] - nums[i-1];
    }
    return res;
}
 
 按奇偶排序数组 
905. 按奇偶排序数组https://leetcode-cn.com/problems/sort-array-by-parity/
 
 
 
 题目描述：
 
 
给定一个非负整数数组 A，返回一个数组，在该数组中， A 的所有偶数元素之后跟着所有奇数元素。
 
 
你可以返回满足此条件的任何数组作为答案。
 
 
思路：将比较条件修改成偶数优先就行了
 
 
bool cmp(void *a,void *b){
    if((*(int*)a)%2 == 1 && (*(int*)b)%2 == 0)
        return true;        // 如果奇数在前，偶数在后就交换
    else
        return false;
}
int* sortArrayByParity(int* nums, int numsSize, int* returnSize){
    qsort(nums,numsSize,sizeof(int),cmp);
    *returnSize = numsSize;
    return nums;
}
 
三角形的最大周长 
976. 三角形的最大周长https://leetcode-cn.com/problems/largest-perimeter-triangle/
 
 
 
 题目描述：
 
 
给定由一些正数（代表长度）组成的数组 A，返回由其中三个长度组成的、面积不为零的三角形的最大周长。
 
 
如果不能形成任何面积不为零的三角形，返回 0。
 
 
思路：排序后从后面往前遍历，当遇到满足三角形条件的直接跳出
 
 
bool cmp(void *a,void *b){
    return *(int*)a > *(int*)b;
}
int largestPerimeter(int* nums, int numsSize){
    qsort(nums,numsSize,sizeof(int),cmp);
    int i,ans = 0;
    for(i = numsSize-1;i>=2;--i){
        if(nums[i] < nums[i-1]+nums[i-2]){
            ans = nums[i]+nums[i-1]+nums[i-2];
            break;
        }
    }
    return ans;
}

 
 今天的打卡完成！！
 
 
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5634685.html