这里只记住了编程题：

编程1：计算数列：2/1+3/2+5/3+8/5+…的前100项的和()

#include "stdafx.h"#include 
     
      using namespace std;int _tmain(int argc, _TCHAR* argv[]){    int a = 2, b = 1;//a为分子，b为分母    float s = 0;//求和    int n = 20;//前20项的和    int t = 0;//临时变量    for (int i = 0; i < n; i++)    {        s += (float)a / b;//累加项的和        t = a;//将分子的值给临时变量        a = a + b; //将分子+分母的和给新的分子        b = t; //将临时变量的值给分母    }    cout<
      <
     

编程题2：用希尔算法

基本思想：

    希尔排序就是对直接插入排序的一个优化。现在有一个array,希尔排序就是设定一个增量incrementNum(0<incrementNum<array.length)。先从array[0]开始，以incrementNum为增量的进行直接插入排序，直到数组末尾，然后从array[1]开始重复：以incrementNum为增量的进行直接插入排序; 然后从array[1]开始重复......一直到array[n]。然后取一个小于上一步增量的新的增量（比如设置为incrementNum/2）,对前一个步骤的结果array进行遍历，直接插入排序....，再取小于上一步增量的新的增量，重复进行：遍历，直接插入排序直到新的增量小于1之后再退出循环。

过程：

public class Xier {        public static void Shellsort(int[] arrays){        if(arrays == null || arrays.length <= 1){            return;        }        //增量        int incrementNum = arrays.length/2;        while(incrementNum >=1){            for(int i=0;i
       
        arrays[j+incrementNum]){                        int temple = arrays[j];                        arrays[j] = arrays[j+incrementNum];                        arrays[j+incrementNum] = temple;                    }                }            }            //设置新的增量            incrementNum = incrementNum/2;            System.out.println(Arrays.toString(arrays));        }    }        public static void main(String[] args) {        int[] a = { 57, 68, 59, 52, 72, 28, 96, 33 };        Xier.Shellsort(a);    }}
       

 

算法性能分析：

时间复杂度：最坏情况下为O(n^2)，平均时间复杂度为O(nlogn)

空间复杂度：归并排序需要一个大小为1的临时存储空间用以保存合并序列，所以空间复杂度为O(1)

算法稳定性：从上面图片中可以看出，数字5在排序后交换了位置，所以它是不稳定的算法。