It's our wits that make us men.

2019/7/19 C 练练手

Posted on By LuLu

leetcode两个数字相加

#include<stdio.h>

int main()
{
    int* twoSum(int* nums, int numsSize, int target, int* returnSize);
    int nums[4] = {2,7,11,15};
    int numsSize = 4;
    int target = 9;
    int returnSize[2];
    twoSum(nums,numsSize,target,returnSize);
    printf("%d,%d\n",returnSize[0],returnSize[1]);
    return 0;
}

int* twoSum(int* nums, int numsSize, int target, int* returnSize){
    int i,j;
    for(i = 0;i < numsSize;i++)
    {
        for(j = 0;j < numsSize;j++)
        {
            if(nums[i] + nums[j] == target)
            {
                returnSize[0] = i;
                returnSize[1] = j;
            }
                
        }
    }
    return returnSize;
}

排序

冒泡排序

两两元素进行比较,一轮一轮循环,直到没有要变换位置的元素。小的元素不断前移,故称冒泡排序

选择排序

每次遍历所有元素找到最小的放到最前面,再从未排序元素中找最小的,放到已排序元素末尾,重复到只剩一个元素

插入排序

遍历元素,从第一个元素开始放到第一个位子,第二个元素与已排序元素比较,放到合适位置(类似于打扑克的时候整牌)

希尔排序

简单插入排序的改进版(但是用得比较少),增量从大到小就好

先将增量设为5,即间隔为4的两个元素进行大小比较交换顺序

再将增量设为2,即间隔为1的两个元素进行大小比较交换顺序

最后增量设为1,讲一个大致有序的数列进行排序,会减少时间复杂度

它是首先突破时间复杂度排序为n方的一种排序方法

归并排序

如果是一个15个元素的数列,先将他们分成两个部分8和7

8的部分先两个进行比较排序,再将后两个比较排序,然后将这四个比较排序,再将第三组的两个进行排序,将第四组的两个进行排序,最后将后四个元素进行排序,再将前四个和后四个进行排序,这样8个就完成了对应排序

后七个也是如此

最后将前八个和后七个进行综合排序即可,综合排序时,记得将每次未排序元素的第一个进行比比较即可

快速排序

选取一个数,分成两部分,比它小的放到前面去;再对这两部分进行排序,使得整个序列有序