一、时间复杂度
1、定义
一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n)，使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n))，称O(f(n))为算法的渐进时间复杂度(O是数量级的符号 )，简称时间复杂度。
A、时间频度：
一个算法花费的时间与算法中语句的执行次数成正比，哪条语句执行的次数多，它花费的时间就多，所以一个算法中语句执行的次数称为时间频度，记为T(n)。
B、时间复杂度：
n称为问题的规模，当n不断变化时，时间频度T(n)也会不断变化。要想知道它变化时呈现什么规律，由此引入了时间复杂度的概念。
时间频度与时间复杂度是不同的，时间频度不同但时间复杂度可能相同。
如：T(n)=n2+3n+4与T(n)=4n2+2n+1它们的频度不同，但时间复杂度相同，都为O(n^2)。
常见的时间复杂度有：
一般情况下所说的时间复杂度即为最坏情况下的时间复杂度， 这样做的原因是：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界，这就保证了算法的运行时间不会比最坏的情况下更长。如果最差情况下的运行时间能够满足要求，那所有的情况下都不会有问题了。
2、如何计算
A、找到执行次数最多的语句
B、计算语句执行次数的数量级
C、用大O来表示结果
举例：
(1)
for(i = 1; i <= n; i++) { //循环了n*n次，O(n2)
for(j = 1; j <= n; j++) {
s++;
}
}
(2)
for(i = 1; i <= n; i++) { //循环了(n+n-1+...+1)≈(n2)/2，O(n2)
for(j = 1; j <= n; j++) {
s++;
}
}
(3)
i=1;k=0;
while(i <= n-1) { //循环了n-1≈n次，O(n)
k += 10 * i;
i++;
}
(4)
for(i = 1; i <= n; i++) { //循环了(1^2+2^2+3^2+...+n^2)=n(n+1)(2n+1)/6≈(n^3)/3，
for(j = 1; j <= n; j++) { //O（n^3)
for(k = 1; k <= j; k++) {
x=x+1;
}
}
}
(5)
x=91; y=100;
while(y > 0) {//T(n)=O(1)，与n无关
if(x > 100) {
x = x - 10;
y--;
} else {
x++;
}
}
3、总结：
A、取决于执行次数最多的语句，如当有若干个循环语句时，算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度f(n)决定的。
B、如果算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)
C、算法的时间复杂度不仅仅依赖于问题的规模，还与输入实例的初始状态有关
二、希尔排序
希尔排序是又称“缩小增量排序”。它也是一种插入排序，但在时间效率上比传统的插入排序，折半插入排序，表插入排序等有较大改进。
1、基本思想
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
简单插入排序很循规蹈矩，不管数组分布是怎么样的，依然一步一步的对元素进行比较，移动，插入，比如[5, 4, 3, 2, 1, 0]这种倒序序列，数组末端的0要回到首位置很是费劲，比较和移动元素均需n-1次。而希尔排序在数组中采用跳跃式分组的策略，通过某个增量将数组元素划分为若干组，然后分组进行插入排序，随后逐步缩小增量，继续按组进行插入排序操作，直至增量为1。希尔排序通过这种策略使得整个数组在初始阶段达到从宏观上看基本有序，小的基本在前，大的基本在后。然后缩小增量，到增量为1时，其实多数情况下只需微调即可，不会涉及过多的数据移动。
2、基本步骤
选择增量gap = length / 2，缩小增量继续以gap = gap / 2的方式，这种增量选择可以用一个序列来表示，{n/2,(n/2)/2...1}，称为增量序列。这种增量称为希尔增量，但其实这个增量序列不是最优的（希尔排序的增量序列的选择与证明是个数学难题）。
举例：
原始数组，元素颜色相同的为一组
初始增量gap = length / 2 = 5，也就是说整个数组分成5组:[8, 3] [9, 5] [1, 4] [7, 6] [2, 0]
对这5组进行插入排序，结果如下，之后缩小增量gap = 5 / 2 = 2，数组分成了2组：[3, 1, 0, 9, 7] [5, 6, 8, 4, 2]
再对上面两个数组进行插入排序，结果如下，再次缩小增量gap = 2 / 2 = 1，整个数组只有一组数据了[0, 2, 1, 4, 3, 5, 7, 6, 9, 8]
之后只需对这个数组进行微调，无需进行大量的移动操作，即可完成整个数组的排序
3、算法：
void shellsort(int a[], int n) {
int gap = n / 2;
int i, j;
int tmp;
for(gap = n / 2; gap > 0; gap /= 2) { //增量起始值为n/2,之后逐次减半
//从第gap个元素，逐个对其所在组进行直接插入排序操作
for(i = gap; i < n; i++) {
tmp=a[i];
j = i;
if(a[j] < a[j - gap]) {
while(j - gap >= 0 && tmp < a[j - gap]) {
//移动法
a[j] = a[j - gap];
j = j - gap;
}
a[j] = temp;
}
}
}
}
