1、插入排序
插入排序是将一个元素插入到已经排好序的子序列中，实现下，n表示数组的长度。在排第i元素时，先将第i个元素暂存（temp=a[i]），然后i-1个位置开始依次将比a[i]大的元素后移。最终将a[i]插入到正确位置。
//插入排序void insert_sort(int *a,int n){int temp,i,j;for(i=1;i<n;i++){temp = a[i];//暂存第i个元素for(j=i-1;j>=0 && a[j]>temp;j–){//如果前一个元素总是比a[i]大，则不停的向后移动元素a[j+1] = a[j];}a[j+1] = temp;}}最坏情况：整个序列是逆序，这个时候在插入第i个元素的时候需要比较i次（前面有i个元素），所以总的比较次数为：
，即n(n-1)/2，所以时间复杂度为O(n^2).
平均情况：在插入第i个元素的时候，前面一共有i+1个位置可以插入，在插入到最左边的位置和第一个元素后面时均需要比较i次，所以插入第i个元素比较次数为：
，总的比较次数为：
，所以复杂度为O(n^2).
2、快速排序
快速排序是一种分治法的思想，主要思想是首先找一个“基准”元素，将所有比基准元素大的元素放到基准元素右边，所有比基准元素小的元素放到基准元素左边，这样基准元素在整个序列中的最终位置就确定了，同时，基准元素经序列分为两个子序列，，对子序列进行上述同样的操作，最终就能得到有序的序列。
//以第一个元素为基准，将元素分成左右两部分，左边的都比基准小，右边的都比基准大。//返回基准位置int partition(int *a,int left,int right){int i = left,j=right;int pivot = a[left];//将pivot暂存，因为之后这个位置将由比pivot小的数占据while(i<j){for(;i<j && a[j]>=pivot;j–);//从右边找一个比pivot小的数a[i] = a[j];//将这个数放到左边空位，空位是由pivot或之前比pivot大的数留出来的for(;i<j && a[i]<=pivot;i++);//从左边找一个比pivot大的数a[j] = a[i];//将这个数放到右边空位}a[i] = pivot;return i;}//快速排序void quick_sort(int *a,int left,int right){int split_point;if(left<right){split_point = partition(a,left,right);quick_sort(a,left,split_point-1);quick_sort(a,split_point+1,right);}}partition函数的功能就是将整个序列分成左右两部分，中间是基准元素的最终位置，这个函数分别从右边j和左边i开始找，总的比较次数为子序列的长度-1，(第一个是pivot不用比较)，且i<=j，所以partition复杂度为O(n)。
最坏情况：当整个序列是正序的时候，这样每次递归将序列分成两个子序列时，第一个序列只有一个元素，第二个序列有n-1个元素，而每次递归的非递归代价(partition的代价，比较次数)为子序列的长度-1，总的比较次数为：(n-1)+(n-2)+…+1=n(n-1)/2，所以时间复杂度为O(n^2)。
平均情况：假设划分点（pivot的最终位置）在每个位置的概率是相等的。这时快速排序的递归表达式为：
其中(n-1)表示非递归代价(partition代价)，可以注意到对T(i)和T(n-1-j)从i=0到n-1求和是相等的，所以递归表达式最终转化为：
，通过数学归纳法可以证明T(n)的复杂度为O(nlgn)。
最终结算结果为：T(n)约等于
。
无神的瞳孔，我迫切想逃离这周遭被钢筋混凝土堆架的城市，
