一, 实现思想
1, 将数组分成一个个小序列 (当然在一开始这些小序列都是一个元素)
2, 将相邻两个小序列合并起来 (当然在合并的时候排好序)
二, 实现图例
1, 递归实现
2, 非递归实现 (循环实现)
三, 代码实现
(递归和非递归地合并代码都是一样的, 即 merge 函数都是一样)
1, 递归代码实现
- #include <stdio.h>
- int data[] = {8, 3, 2, 6, 7, 1, 5, 4};
- int length = 8;
- // 将两个序列合并
- void merge(int first1, int last1, int last2)
- {
- int *temp = new int[length]; // 数组 temp 作为合并的辅助空间, 注意这个数组和原来的数组是一样大小的, 为了方便
- int i = first1; // 左序列第一个元素下标
- int j = last1 + 1; // 右序列第一个元素下标
- int k = first1; // 左序列第一个元素下标, 用于记录合并后的初始位置 (将 temp 复制到 data 上)
- while (i <= last1 && j <= last2)
- {
- if (data[i] <= data[j])
- temp[k++] = data[i++]; // 升序排序, 将小的放前面. 如要修改, 改变一下符号即可.
- else
- temp[k++] = data[j++];
- }
- while (i <= last1) // 做一些收尾工作, 比如只剩下一边有几个 (当然了, 这几个必定是有序的了)
- temp[k++] = data[i++]; // 注意这里的 ++ 也很有必要, 因为有可能一边的序列有好几个剩下的
- while (j <= last2)
- temp[k++] = data[j++];
- for (i = first1; i <= last2; i++)
- data[i] = temp[i];
- delete[] temp;
- }
- //MergeSort 和 merge 接收的都是数组的下标
- void MergeSort(int first, int last)
- {
- if (first == last)
- return;
- else
- {
- int mid = (first + last) / 2;
- MergeSort(first, mid);
- MergeSort(mid + 1, last);
- merge(first, mid, last);
- }
- }
- int main(void)
- {
- int last = 7;
- for (int i = 0; i <last + 1; i++)
- printf("%d", data[i]);
- printf("\n");
- MergeSort(0, last);
- for (int i = 0; i < last + 1; i++)
- printf("%d", data[i]);
- return 0;
- }
- /*
- 输出
- ------------------------------------
- 8 3 2 6 7 1 5 4
- 1 2 3 4 5 6 7 8
- ------------------------------------
- */
二, 非递归实现 (循环实现)
- #include <stdio.h>
- int data[] = {8, 3, 2, 6, 7, 1, 5, 4};
- int length = 8;
- // 将两个序列合并
- void merge(int first1, int last1, int last2)
- {
- int *temp = new int[length]; // 数组 temp 作为合并的辅助空间, 注意这个数组和原来的数组是一样大小的, 为了方便
- int i = first1; // 左序列第一个元素下标
- int j = last1 + 1; // 右序列第一个元素下标
- int k = first1; // 左序列第一个元素下标, 用于记录合并后的初始位置 (将 temp 复制到 data 上)
- while (i <= last1 && j <= last2)
- {
- if (data[i] <= data[j])
- temp[k++] = data[i++]; // 升序排序, 将小的放前面. 如要修改, 改变一下符号即可.
- else
- temp[k++] = data[j++];
- }
- while (i <= last1) // 做一些收尾工作, 比如只剩下一边有几个 (当然了, 这几个必定是有序的了)
- temp[k++] = data[i++]; // 注意这里的 ++ 也很有必要, 因为有可能一边的序列有好几个剩下的
- while (j <= last2)
- temp[k++] = data[j++];
- for (i = first1; i <= last2; i++)
- data[i] = temp[i];
- delete[] temp;
- }
- //MergePass 和 merge 接收的都是数组的下标
- void MergePass(int h)
- {
- int i = 0;
- while (i + 2 * h <= length)
- {
- merge(i, i + h - 1, i + 2 * h - 1);
- i = i + 2 * h;
- }
- if (i + h < length) // 如果还有一块长度是 h, 另一块长度 < h, 则进行下面这种合并 (主要是限制一下范围)
- merge(i, i + h - 1, length - 1);
- }
- int main(void)
- {
- int last = 7;
- for (int i = 0; i < last + 1; i++)
- printf("%d", data[i]);
- printf("\n");
- int h = 1;
- while (h < length)
- {
- MergePass(h);
- h = 2 * h;
- }
- for (int i = 0; i < last + 1; i++)
- printf("%d", data[i]);
- return 0;
- }
- /*
- 输出
- ------------------------------------
- 8 3 2 6 7 1 5 4
- 1 2 3 4 5 6 7 8
- ------------------------------------
- */
四, 总结
排序除了要了解这个大致的框架外, 如果想要实现, 还需要明确一下用什么来判断结束, 也就是各种各样的条件
来源: http://www.bubuko.com/infodetail-3654083.html