本文共 10686 字，大约阅读时间需要 35 分钟。
总结：
①复杂度O(n): 桶排序 、计数排序、基数排序
这三个的共同点是都对nums分类，另外声明数组或链表，计数排序声明 nums中（最大值-最小值）个数组，就像是最简单的hash table，空间占用可能很大，对于判断某个元素是否出现比较常用；基数排序是对 数组元素的每一位进行排序，采用最低有效位优先；桶排序先确定桶的个数len，nums[i]%len或nums[i]/len具体问题具体分析，再对桶内的数据分别排序；
②复杂度平均运行时间O(NlogN)，最坏运行时间可能为O(N*N): 希尔排序(平均运行时间？）、归并排序、快速排序、堆排序；
只使用元素间比较的任何排序算法在最坏情况下至少需要Ω(NlogN).
算法细节：
希尔排序，又称为 减小增量排序，一般习惯采用：1 ，2, ，...,n/2，当采用Hibbard增量 1, 3, 7, ... , 2^k-1时最坏运行时间会减小；
快速排序，枢纽元的选择、分割策略、小数组的时候会慢于插入排序等等，快速和归并都用了归并的思想。
堆排序不需要额外O(n)空间，具体实现不熟悉。（之前认为是需要的，但是可以把DeleteMin的最小元素放在堆的后面，所以空间复杂度是O(1)）
③复杂度O(N*N): 冒泡排序、插入排序Insertion Sort List （相邻的元素比较交换）；
④冒泡和插入、归并排序是稳定的，而希尔排序、快速排序是不稳定，当前面的排序后面会用时，需要考虑稳定性；
C语言描述中说，任何排序通过附加条件都可以coding成稳定，感觉应该是在排序之后，用附加条件重新排列吧。
⑤根据题目选择最适合的方法，不一定快的就最适合，比如给的数据已经排好序，另外增加数据可以用插入。
将两个常用的排序加进来，理解了方法还是背下来比较好，找工作也需要
希尔：
void shell_sort(int *nums, int numsSize){ int j; for (int increment = numsSize / 2; increment > 0; increment /= 2){ for (int i = increment; i = increment; j -= increment){ if (tmp < nums[j - increment]) nums[j] = nums[j - increment]; else break; } nums[j] = tmp; } }} 快排：先左还是先右和枢纽元放的位置有关，都可以
void swap_ij(int *nums, int i, int j){ int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp;}
void quick_sortM(int *nums, int start, int end){ if (start >= end) return; int pivot = nums[end]; int i = start, j = end; //把大等于的放右边，小于放左边 while (i < j){ //顺序很重要，要先找右边的，这样截止时i上的是比nums[start]小的吧，如果选枢纽元是end的话，应该要反过来 while (i = pivot){ j--; } if (i < j){ swap_ij(nums, i, j);//在swap之后进行递增递减的话会改变i位置上，最好不要 } } swap_ij(nums, i, end); quick_sortM(nums, start, i - 1); quick_sortM(nums, i + 1, end);}
题目：
主要是逻辑分析清楚：
方法一：
struct Interval* insert(struct Interval* intervals, int intervalsSize, struct Interval newInterval, int* returnSize) { int i; *returnSize = 0; struct Interval* ret = (struct Interval*)malloc((intervalsSize + 1)*sizeof(struct Interval)); if (intervalsSize == 0) { *returnSize = 1; ret[0] = newInterval; return ret; } for (i = 0; i < intervalsSize; i++){ if (intervals[i].end < newInterval.start ) { ret[*returnSize].start = intervals[i].start; ret[*returnSize].end = intervals[i].end; (*returnSize)++; if (i == intervalsSize - 1 || intervals[i + 1].start > newInterval.end) { ret[*returnSize].start = newInterval.start; ret[*returnSize].end = newInterval.end; (*returnSize)++; } } else if (intervals[i].start > newInterval.end) { if (i == 0) { ret[*returnSize].start = newInterval.start; ret[*returnSize].end = newInterval.end; (*returnSize)++; } ret[*returnSize].start = intervals[i].start; ret[*returnSize].end = intervals[i].end; (*returnSize)++; } else { ret[*returnSize].start = intervals[i].start < newInterval.start ? intervals[i].start : newInterval.start; while (i + 1 < intervalsSize && newInterval.end >= intervals[i + 1].start) { i++; } { ret[*returnSize].end = intervals[i].end >= newInterval.end ? intervals[i].end : newInterval.end; (*returnSize)++; } } } return ret;} 方法二：用类似于栈的方法做的，因为原数据没有overlapping，比较简单，新增加的数据与原来的重复时，start插在重复的前面，end插在后面，还好插入排序可以方便实现稳定性
struct inter{ int number; char type;};struct Interval* insert(struct Interval* intervals, int intervalsSize, struct Interval newInterval, int* returnSize) { struct inter *flag = (struct inter*)malloc((intervalsSize+1) * 2 * sizeof(struct inter)); struct Interval* ret = (struct Interval*)malloc((intervalsSize + 1)*sizeof(struct Interval)); if (intervalsSize == 0){ *returnSize = 1; ret[0] = newInterval; free(flag); return ret; } int i ,j; for (i = 0; i < intervalsSize; i++){ flag[2 * i].number = intervals[i].start; flag[2 * i].type = 's'; flag[2 * i + 1].number = intervals[i].end; flag[2 * i + 1].type = 'e'; } //因为intervals已经排序并且无重复，用插入排序最好 struct inter tmp1,tmp2; tmp1.number = newInterval.start, tmp1.type = 's'; tmp2.number = newInterval.end, tmp2.type = 'e'; if (tmp1.number>flag[2 * intervalsSize - 1].number){ flag[2 * intervalsSize] = tmp1; } else { for (i = 0; i < 2 * intervalsSize; i++){ if (tmp1.number<=flag[i].number) { for (j = 2 * intervalsSize - 1; j >= i; j--){ flag[j + 1] = flag[j]; } flag[i] = tmp1; break; } } } if (tmp2.number >= flag[2 * intervalsSize].number){ flag[2 * intervalsSize+1] = tmp2; } else { for (; i < 2 * intervalsSize + 1; i++){ if (tmp2.number = i; j--){ flag[j + 1] = flag[j]; } flag[i] = tmp2; break; } } } int size = 0; *returnSize = 0; for (i = 0; i < 2 * (intervalsSize+1); i++){ if (flag[i].type == 's'){ size++; if (size == 1) { ret[*returnSize].start = flag[i].number; } } else { size--; if (size == 0) { ret[*returnSize].end = flag[i].number; (*returnSize)++; } } } free(flag); return ret;} 分析：两种方法时间复杂度都是O(n),第一个空间额外申请，速度也稍慢
给的数据刚开始不是sorted的，先按start大小排序，之后又是逻辑分析；尝试了类似地第二种方法，因为用的希尔排序稳定性被打乱，start和end乱了，wrong
struct Interval* merge(struct Interval* intervals, int intervalsSize, int* returnSize) { if (intervalsSize <= 0) return intervals; struct Interval* ret = (struct Interval*)malloc(intervalsSize*sizeof(struct Interval)); struct Interval tmp; int increment, i, j; for (increment = intervalsSize / 2; increment > 0; increment /= 2){ for (i = increment; i < intervalsSize; i++){ tmp = intervals[i]; for (j = i; j>=increment; j -= increment){ if (tmp.start < intervals[j - increment].start) { intervals[j] = intervals[j - increment]; } else break; } intervals[j] = tmp; } } ret[0].start = intervals[0].start; ret[0].end = intervals[0].end; *returnSize = 1; for (i = 1; i < intervalsSize; i++){ if (intervals[i].start<=ret[*returnSize - 1].end && intervals[i].end <= ret[*returnSize - 1].end) { ; } else if (intervals[i].start<=ret[*returnSize - 1].end && intervals[i].end > ret[*returnSize - 1].end) { ret[*returnSize - 1].end = intervals[i].end; } else if (intervals[i].start > ret[*returnSize - 1].end) { ret[*returnSize].start = intervals[i].start; ret[*returnSize].end = intervals[i].end; (*returnSize)++; } } return ret;} # Definition for an interval.# class Interval(object):# def __init__(self, s=0, e=0):# self.start = s# self.end = eclass Solution(object): def merge(self, intervals): """ :type intervals: List[Interval] :rtype: List[Interval] """ if not intervals: return intervals intervals.sort(key = lambda x: x.start) # 用内置的sort比intervals = sorted(intervals, key=lambda x: x.start)快了不少 ret = [] ret.append(intervals[0]) for each in intervals: if each.start > ret[-1].end: ret.append(each) else: ret[-1].end = max(ret[-1].end, each.end) return ret
leetcode的运行时间好像不太准，差距好大
Largest Number
逻辑没理清楚，12>121,830<8308,2<2281，9061<9153,用C++就是几句话的事情。。。，希尔排序的规则是可以自己定义的，char* int2string(int num){ char *ret = (char*)malloc(11*sizeof(char)); int i = 0; if (num == 0){ ret[0] = 0 + 48; ret[1] = '\0'; return ret; } while (num){ ret[i++] = num % 10+48; num /= 10; } int length = i; int tmp; for (i = 0; i < length / 2; i++){ tmp = ret[i]; ret[i] = ret[length - 1 - i]; ret[length - 1 - i] = tmp; } ret[length] = '\0'; return ret;}int islarger(int a, int b){///不是正常的比较,原来用的递归算法，但是3544>3061，用递归的话，61>544 char *ac = int2string(a); char *bc = int2string(b); char fir1 = *(ac),fir2 = *(ac+1); if (strlen(ac) == strlen(bc)) return strcmp(ac, bc); while (*ac == *bc){ ac++; bc++; } if (*ac != '\0' && *bc != '\0') return (*ac - *bc); if (*ac == '\0'){ while (*(bc+1)!='\0' && fir1 == *bc) bc++; if (*bc < fir1) return true; if (*bc == fir1) return fir2 - *bc; if (*bc > fir1) return false; } if (*bc == '\0') { while (*(ac + 1) != '\0' && fir1 == *ac) ac++; if (*ac > fir1) return true; if (*ac == fir1) return *ac - fir2; if (*ac < fir1) return false; }}int* sort2largest(int* nums, int numsSize){ int i, j, k, increment; int tmp; for (increment = numsSize / 2; increment > 0; increment /= 2){ for (i = increment; i < numsSize; i++){ tmp = nums[i]; for (j = i; j >= increment; j -= increment){ if (islarger(tmp , nums[j - increment]) > 0) nums[j] = nums[j - increment]; else break; } nums[j] = tmp; } } return nums;}char* largestNumber(int* nums, int numsSize) { char *ret = (char*)malloc(numsSize*11*sizeof(char)); ret[0] = '\0'; nums = sort2largest(nums, numsSize); if (nums[0] == 0) { ret[0] = 48; ret[1]= '\0'; return ret; } int i; for (i = 0; i < numsSize; i++){ ret = strcat(ret, int2string(nums[i])); } ret = strcat(ret,"\0");//?? return ret;}
求未排序数列经排序后相邻最大的差，题目要求最好O(n).
方法一：没达到要求，但也可以通过
int maximumGapII(int* nums, int numsSize) { if (numsSize<2) return 0; int i, j, increment; int tmp; for (increment = numsSize / 2; increment > 0; increment /= 2){ for (i = increment; i < numsSize; i++){ tmp = nums[i]; for (j = i; j >= increment; j -= increment){ if (tmp < nums[j - increment]) { nums[j] = nums[j - increment]; } else break; } nums[j] = tmp; } } int diff = 0; for (i = 1; i < numsSize; i++){ if (nums[i] - nums[i - 1] > diff) diff = nums[i] - nums[i - 1]; } return diff;} 方法二：桶排序 理解起来就是 好几个桶，把满足条件的放进去；相当于排好序的一排数，按照条件抓紧桶里，桶里的数都是相邻的；这道题没有在桶内排序，而是对桶的一个应用。
桶排序的思想：假设有n个元素，A到B
最大差值>(B-A)/(N-1) (小于等于B-A) 取桶的大小len=(B-A)/(N-1)，则最多会有(B - A) / len + 1个桶！！！注意 len==0时的情况 对于任意K，桶的位置 （K-A）/ len,维护每个桶的最大最小值 由于同一个桶内的元素之间的差值至多为len - 1(才可能是相邻的)，因此最终答案不会从同一个桶中选择。 对于每一个非空的桶p，找出下一个非空的桶q，则q.min - p.max可能就是备选答案。返回所有这些可能值中的最大值。注意，一定要是非空的桶。有除法的时候一定要注意除0溢出，还有只有一个桶的特殊情况。
struct inbucket{ int min ; int max ;};int maximumGap(int* nums, int numsSize) { if (numsSize < 2) return 0; int min = INT_MAX, max = 0; int i; for (i = 0; i < numsSize; i++) { if (nums[i]>max) max = nums[i]; if (nums[i] < min) min = nums[i]; } int len = (max - min) / (numsSize - 1); int bucknum = (len == 0 ? 1:((max - min) / len + 1)); struct inbucket *bucket = (struct inbucket *)malloc(bucknum*sizeof(struct inbucket)); for (i = 0; i < bucknum; i++) { bucket[i].min = INT_MAX; bucket[i].max = 0; } int tmp; for (i = 0; i < numsSize; i++) { if (len == 0) tmp = 0; else tmp = (nums[i] - min) / len; if (bucket[tmp].min > nums[i]) bucket[tmp].min = nums[i]; if (bucket[tmp].max < nums[i]) bucket[tmp].max = nums[i]; } int maxgap = 0; int pre = 0;//第一个和最后一个肯定有值 for (i = 0; i < bucknum; i++) { if (bucket[i].min != INT_MAX) { if(bucket[i].min - bucket[pre].max > maxgap) { maxgap = bucket[i].min - bucket[pre].max; } pre = i; } } if (bucknum == 1) maxgap = bucket[0].max - bucket[0].min; return maxgap;} 用python写的桶排序比普通的方法还慢一些。
感觉排序算法的编程比较难，掌握原理之后也容易忘记，还是背下好的代码更方便，希尔排序选择排序中避免明显使用交换的方法等等。
总结的结论，有错误的欢迎指出，对这一块儿真的比较难确定。
转载地址：http://phovi.baihongyu.com/