#算法学习录#归并&插入排序

2016-04-28 本文已影响0人 LRC_cheng

我们直接对代码进行分析：
void MERGE_SORT(int A[], int p, int r){  //分离数据树
int q;
q = (p + r) / 2;
if (r - p > 3){
  MERGE_SORT(A, p, q);
  MERGE_SORT(A, q + 1, r);
}
MERGE(A, p, q, r); //排序
}

划分区间，注意数组下标从0开始！p,r为划分数组的起始下标和最后一个元素的下标，，q为中间下标,q大于5时进行归并排序，小于5时进行插入排序（当个数较少时，用插入排序可以减少递归调用的空间使用，且其效率较高）

具体排序过程：
void MERGE(int A[], int p, int q, int r){  //排序
if (r - p > 3){
  int n1, n2, i = 0, j = 0, k;      //当p=0,q=4,r=9时
  int *L, *R;
  L = new int[NUM];
  R = new int[NUM];

n1 = q - p + 1; //n1=5
n2 = r - q; //n2=5

  for (i = 0; i < n1; i++){
   L[i] = A[p + i];                  //A[0]开始到A[4]赋给左边数组L[0]到L[4]
  }
  for (j = 0; j < n2; j++){
   R[j] = A[q + j + 1];            //A[5]开始到A[9]赋给右边数组R[0]到L[4]
  }

L[n1] = MAX; //设置哨兵
R[n2] = MAX; //设置哨兵

  i = j = 0;
  for (k = p; k <= r; k++){    //k=p=0,r=9,使十个数都排列到A[]中
   if (L[i] <= R[j]){               //当L[i]比R[j]小时，把L[i]放到A[K]中，反之亦然
    if (j != n2){                  //R[j]不等于标志位
     A[k] = L[i];
     i++;
    }
    else{
     for (; k <= r; k++){     //R[j]等于标志位时，把剩余的L[i]放到A中
      A[k] = L[i];
      i++;
     }
    }
   }
   else{
    if (i != n1){
     A[k] = R[j];
     j++;
    }
    else{
     for (; k <= r; k++){
      A[k] = R[j];
      j++;
     }
    }
   }
  }
  delete[]L;      //释放空间
  delete[]R;
}
else{               //插入排序
  int temp, i;
  for (int j=p+1; j <= r; j++){
   temp = A[j];
   i = j - 1;
   while (i >= p && A[i] > temp){
    A[i + 1] = A[i];
    i--;
    A[i + 1] = temp;
   }
  }
}
}
这种排序方法就像把一副扑克牌分成两份（牌面向下放置），然后每次从两叠牌上方各抽一张比较，按顺序叠放合并。就是一个完全二叉树向上合并过程。