归并排序
20140315更新归并排序版本2,代码更精简直观。
版本1:
/* * 归并排序 */ void MergeSort(int data[], int low, int high) { /* 归并排序data[low, high) */ /* 将序列一分为二,分别归并排序,再合并排序 */ /* 函数出口为,子序列只含一个元素 */ if (high - low < 2) {/* 单元素区间 */ return; } int mid = (high + low) >> 1; MergeSort(data, low, mid); MergeSort(data, mid, high); /* 合并 */ int *pDataA, *pDataB; int lenDataA, lenDataB; int i, j, k; /* pDataA[0..lenDataA]即data[low..mid] */ /* pDataB指向(data + mid) */ /* 序列前一半副本pDataA[]需分配空间,后一半副本则直接在原序列读取 */ /* 合并时,在原序列上存储,前一部分数据会被覆盖 */ lenDataA = mid - low; pDataA = new int [lenDataA]; memcpy(pDataA, data + low, sizeof(int) * lenDataA); lenDataB = high - mid; pDataB = data + mid; /* 两部分合并排序 */ for (i = 0, j = 0, k = 0; i < lenDataA || j < lenDataB; ) { if (i < lenDataA && j < lenDataB) { if (pDataB[j] < pDataA[i]) { data[low + k++] = pDataB[j++]; } else { data[low + k++] = pDataA[i++]; } } else { while (i < lenDataA) { data[low + k++] = pDataA[i++]; } while (j < lenDataB) { data[low + k++] = pDataB[j++]; } } }//for (i = 0, j = 0, k = 0; i < lenDataA || j < lenDataB; ) delete [] pDataA; }
版本2:
/* * 归并排序 */ void MergeSort(int data[], int low, int high) { /* 归并排序data[low, high) */ /* 将序列一分为二,分别归并排序,再合并排序 */ /* 函数出口为,子序列只含一个元素 */ if (low >= high - 1) { return; } int mid = (low + high) >> 1; MergeSort(data, low, mid); MergeSort(data, mid, high); /* pDataA[0..lenDataA]即data[low..mid] */ /* pDataB指向(data + mid) */ /* 序列前一半副本pDataA[]需分配空间,后一半副本则直接在原序列读取 */ /* 合并时,在原序列上存储,前一部分数据会被覆盖 */ int lenDataA = mid - low, lenDataB = high - mid; int *pDataA = new int [lenDataA], *pDataB = data + mid; memcpy(pDataA, data + low, sizeof(int) * lenDataA); int i = 0, j = 0, k = 0; while (i < lenDataA && j < lenDataB) { data[low + k++] = pDataA[i] <= pDataB[j] ? pDataA[i++] : pDataB[j++]; } while (i < lenDataA) { data[low + k++] = pDataA[i++]; } while (j < lenDataB) { data[low + k++] = pDataB[j++]; } delete [] pDataA; }