算法导论：启动相关知识

算法导论：起步相关知识
算法：非形式地说，就是任何良定义的计算过程，该过程取某个值或值的集合作为输入并产生某个值或值的集合作为输出。插入排序插入排序的工作方式像许多人排序一手扑克牌。每一步将一个待排序的元素，按其大小插入到前面已经排好序的一组元素的适当位置上去，直到元素全部插入为止。
伪代码：升序

std::advance
template <class InputIterator, class Distance>
  void advance (InputIterator& it, Distance n);
Advance iterator
Advances the iterator it by n element positions.



2.1-2 重写上文伪代码，使之按降序排序
void Merge(int a[], int b[], int low, int mid, int high){    int k = low;    int begin1 = low;    int end1 = mid;    int begin2 = mid + 1;    int end2 = high;    while(k <= high )    {        if(begin1 > end1)            b[k++] = a[begin2++];        else if(begin2 > end2)            b[k++] = a[begin1++];        else        {            if(a[begin1] <= a[begin2])                b[k++] = a[begin1++];            else                b[k++] = a[begin2++];        }    } } void MergePass(int a[], int b[], int seg, int size){    int seg_start_ind = 0;    while(seg_start_ind <= size - 2 * seg)     {        Merge(a, b, seg_start_ind, seg_start_ind + seg - 1, seg_start_ind + seg * 2 - 1);        seg_start_ind += 2 * seg;    }    //#如果一段是正好可歸併的數量而另一段則少於正好可歸併的數量#%    if(seg_start_ind + seg < size)        Merge(a, b, seg_start_ind, seg_start_ind + seg - 1, size - 1);    else        for(int j = seg_start_ind; j < size; j++) //#如果只剩下一段或者更少的數量#%            b[j] = a[j];} void MergeSort(int a[], int size){    int* temp = new int[size];    int seg = 1;    while(seg < size)    {        MergePass(a, temp, seg, size);        seg += seg;        MergePass(temp, a, seg, size);        seg += seg;    }    delete [] temp;} int main(){    int a[] = {3, 5, 3, 6, 4, 7, 5, 7, 4};    MergeSort(a, sizeof(a) / sizeof(*a));    //#輸出#%    for(int i = 0; i < sizeof(a) / sizeof(*a); i++)        cout << a[i] << ' ';    cout << endl;     return 0;}