1. 查找和排序
1. 插入排序

复杂度t=O(n的平方)
将一个记录插入到已排好序的有序表中，从而到一个新的长度++的有序表
具体操作：
1. 数i(表示第i个数)与它数i-1比，如果小，则把数i放在data[0]中作哨兵，且数i-1后移
2. 哨兵依次与数i-2及之前的数(以数j表示之)相比，如果哨兵小，则数j后移，否则覆盖在数j后面的位置上
3. 注意，当--j一直到0的时候，data[0]<data[j]就不成立了，自然结束循环。这正是哨兵的作用

void merge(int data[], int left, int mid, int right) {// 将有序的tmp[start..mid]和tmp[mid+1..end]归并为有序的data[start...end]int i,j,k;int *tmp = new int[right-left+1];i = left; j = mid+1; k = 0;while (i <= mid && j <= right) {if (data[i] <= data[j]) {tmp[k++] = data[i++];} else {tmp[k++] = data[j++];}}while (i <= mid) tmp[k++] = data[i++];while (j <= right) tmp[k++] = data[j++];// 复制回来i = left;k = 0;while (i <= right) data[i++] = tmp[k++];delete[] tmp;}void merge_sort(int data[], int left, int right) { // 最后结果放在在data中if (left >= right) return;int mid = (left + right) / 2;merge_sort(data, left, mid); // merge_sort(data, mid+1, right); merge(data, left, mid, right);} //merge_sort

=====待续