c++归并排序
归并排序是一个重要的排序算法,虽然看过很多次归并排序的代码,但是一段时间后就会忘掉,重新写的时候就又需要在网上查,所以这一次决定自己手写一段归并排序的代码,期间没有查找任何资料,最后在vs2017上调试多次并结合自己的回忆加思考成功的完成了代码的编写。我认为纯手写代码对于程序员是非常重要的,只有自己在没有任何帮助的情况下成功的编写了代码,才算是对这段代码有了一定的理解,所以在这里记录下自己写代码的过程,希望对大家有所帮助,另外笔者水平有限,忘大家谅解。
归并排序的思想是分治,就是将大问题分解为类似的小问题,然后通过解决小问题来解决大的问题。
归并算法的流程可以分为:
1.将数组分割为小的数组
2.对小的数组进行有序合并,当小数组中元素个数为1时就是第一次的有序合并,每一次的合
并都是对一个有序数组的合并,合并算法非常简单, 每一次合并的结果是保存在一个辅助数
组的,每一次合并完后要将结果从辅助数组辅助到原始数组中的对应位置,这一点很重要
1.分割
因为每一次分割是将数组一分为2的,然后在对分割后的数组进行分割,重复这个过程,分割的代码为:
template<class T>
void Guibing(T arr[],int left,int right) { //分割、排序、合并
int i = left, j = right, mid = (i + j) / 2; //left是数组的起点,right是数组的终点
if (i<j) { //这里是if,因为只需要执行一次就可以了,
//我第一次写成了while,程序就陷入死循环了
Guibing(arr,i,mid); //递归分割左半边数组
Guibing(arr,mid+1,j); //递归分割右半边数组
merge(arr, i,mid,mid+1,j); //合并左右2边有序数组
}
}
2.合并有序数组
template<class T>
void merge(T arr[], int lef, int rig, int left, int right) { //对有序数组的合并
//lef是左边数组的起点 lef是左边数组的终点
//left是右边数组的起点 right是右边数组的终点
int i1 = lef, i2 = left; //i1将lef保存下来 i2将left保存下来
int count = lef; //记录这次合并2个数组的最小起点,因为lef是左边数组的起点,所以它是最小的
//合并过程和合并两个有序链表类似
while (i1 <= rig&&i2 <= right) {
if (arr[i1] <= arr[i2]) {
tmparr[count++] = arr[i1++];
}
else {
tmparr[count++] = arr[i2++];
}
}
while (i1 <= rig) {
tmparr[count++] = arr[i1++];
}
while (i2<=right) {
tmparr[count++] = arr[i2++];
}
for (int i = lef; i <= right;i++) { //要将辅助数组中的值复制回原来的
arr[i] = tmparr[i]; //数组的对应位置,否则会出错,第一次没写这个,所以排序失败
}
}
例子:
数组: 8 1 7 2 47 6 3 4
递归分割:
第一次:左:8 1 7 2 右:47 6 3 4
第二次:左: 8 1 右: 7 2 左: 47 6 右 :3 4
第三次:左:8 右:1 左: 7 右: 2 左:47 右:6 左: 3 右:4
此时左右数组中只有一个元素可以进行合并了:
合并:
第一次:左:1 8 右:2 7 左: 6 47 右:3 4
第二次:左:1 2 7 8 右:3 4 6 47
第三次: 1 2 3 4 6 7 8 47
排序完成!!
写归并的时候记住,先分割,再合并,分割用if,合并时要将排序结果复制回原数组对应位置即可。
完整代码:
#include<iostream>
using namespace std;
#define N 8 //定义辅助数组的大小
template<class T>
void printarr(T arr[],int len) {
for (int i = 0; i < len;i++) {
cout << arr[i] << " ";
}
cout << endl;
}
int tmparr[N] = {0}; //辅助数组
template<class T>
void Guibing(T arr[],int left,int right) { //分割、排序、合并
int i = left, j = right, mid = (i + j) / 2;
if (i<j) {
Guibing(arr,i,mid);
Guibing(arr,mid+1,j);
merge(arr, i,mid,mid+1,j);
}
}
template<class T>
void merge(T arr[], int lef, int rig, int left, int right) { //对有序数组的合并
int i1 = lef, i2 = left;
int count = lef;
while (i1 <= rig&&i2 <= right) {
if (arr[i1] <= arr[i2]) {
tmparr[count++] = arr[i1++];
}
else {
tmparr[count++] = arr[i2++];
}
}
while (i1 <= rig) {
tmparr[count++] = arr[i1++];
}
while (i2<=right) {
tmparr[count++] = arr[i2++];
}
for (int i = lef; i <= right;i++) { //要将辅助数组中的值复制回原来的
arr[i] = tmparr[i]; //数组的对应位置,否则会出错
}
}
int main() {
int a[] = { 8,1,7,2,47,6,3,4 };
printarr(a, 8);
Guibing(a,0,7); //归并排序
printarr(tmparr, 8);
return 0;
}