本文共 1319 字,大约阅读时间需要 4 分钟。
#includeusing namespace std;void mergeSort(int data[], int head, int tail); void merge(int data[], int head, int mid, int tail);int main(){ int data[4] = { 7, 5, 6, 4 }; int len = 4; mergeSort(data, 0, len - 1); for (int i = 0; i < 4; ++i) { cout << data[i] << ' '; } cout << endl; return 0;}void mergeSort(int data[], int head, int tail){ if (head < tail) { int mid = (head + tail) / 2; mergeSort(data, head, mid); mergeSort(data, mid + 1, tail); merge(data, head, mid, tail); } return;}void merge(int data[], int head, int mid, int tail){ //len1和len2分别表示左边序列和右边序列的长度 int len1 = mid - head + 1; int len2 = tail - mid; int *L = new int[len1]; int *R = new int[len2]; //分别给数组L和R赋值 for (int i = 0, m = head; i < len1; ++i, ++m) { L[i] = data[m]; } for (int j = 0, n = mid + 1; j < len2; ++j, ++n) { R[j] = data[n]; } //比较大小,从小到大排列 int i = 0, j = 0, k = head; for ( ; i < len1 && j < len2; ++k) //i和j分别指向数组L和R的下标,k为指向数组data的下标 { if (L[i] > R[j]) { data[k] = R[i]; ++j; } else if (L[i] < R[j]) { data[k] = L[i]; ++i; } else { data[k] = L[i]; i += 1; k += 1; data[k] = R[j]; j += 1; } } //将剩下的元素存入data中 if (i == len1) { while (j < len2) { data[k++] = R[j++]; } } if (j == len2) { while (i < len1) { data[k++] = L[i++]; } } delete L; //new的空间最后记得delete掉! delete R; return;}
转载地址:http://wttai.baihongyu.com/