归并排序（C++实现、递归、非递归）

（本博客旨在个人总结回顾）

1.概括

        归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。归并排序是一种稳定的排序方法。

2.实现

C++递归和非递归实现：（一般递归转为非递归，可以使用stack实现）

// MergeSort.cpp : 定义控制台应用程序的入口点。 // #include "stdafx.h" #include <iostream> using namespace std; /* * @name Sort（有序和排序都为升序） * @brief 将左右为有序的数组排序 * @param [in] int * pUnsortArray 左右两部分已经为有序的待排序数组 * @param [in] int nLeft 左下标 * @param [in] int nMid 中间下标 * @param [in] int nRight 右下标 * @param [in] int * pSortArray 排序后放置的临时数组 * @return void */ void Sort(int* pUnsortArray, int nLeft, int nMid, int nRight, int* pSortArray) { int nBegin = nLeft; int nEnd = nRight; int nIndex1 = nLeft; int nIndex2 = nMid +1; while (nBegin <= nEnd) { if (nIndex1 <= nMid && nIndex2 <= nRight) { if (pUnsortArray[nIndex1] <= pUnsortArray[nIndex2]) { pSortArray[nBegin++] = pUnsortArray[nIndex1++]; } else { pSortArray[nBegin++] = pUnsortArray[nIndex2++]; } } else if (nIndex1 <= nMid) { pSortArray[nBegin++] = pUnsortArray[nIndex1++]; } else if (nIndex2 <= nRight) { pSortArray[nBegin++] = pUnsortArray[nIndex2++]; } } //排序完修改原数组 for (int i = nLeft; i <= nRight; i++) { pUnsortArray[i] = pSortArray[i]; } } void Merge(int* pUnsortArray, int nLeft, int nRight, int* pSortArray) { if (nLeft >= nRight) { return; } int nMid = (nLeft + nRight) / 2; Merge(pUnsortArray, nLeft, nMid, pSortArray); Merge(pUnsortArray, nMid + 1, nRight, pSortArray); Sort(pUnsortArray, nLeft, nMid, nRight, pSortArray); } /* * @name MergeSortRecursion * @brief 归并排序递归实现 * @param [in] int * array 待排序数组 * @param [in] int nLength 数组长度 * @return void */ void MergeSortRecursion(int* array, int nLength) { if (NULL == array || nLength <= 1) { return; } int* pSortArray = new int[nLength]; Merge(array, 0, nLength - 1, pSortArray); delete[] pSortArray; } /* * @name MergeSortUnrecursion * @brief 归并排序非递归实现 * @param [in] int * array 待排序数组 * @param [in] int nLength 数组长度 * @return void */ void MergeSortUnrecursion(int* array, int nLength) { if (NULL == array || nLength <= 1) { return; } int* pSortArray = new int[nLength]; int nSize = 1;//分出的最小组 while (nSize <= nLength) { int nBegin = 0; int nMid = 0; int nEnd = 0; while (nEnd < nLength - 1) { nMid = nBegin + nSize - 1; nEnd = nMid + nSize; if (nEnd >= nLength) { nEnd = nLength - 1; } Sort(array, nBegin, nMid, nEnd, pSortArray); nBegin = nEnd + 1; } nSize *= 2; } delete[] pSortArray; } int _tmain(int argc, _TCHAR* argv[]) { int a[100] = { }; for (int i = 0; i < 100; i++) { a[i] = 50 - i; } int nLength = sizeof(a) / sizeof(a[0]); cout << "排序前：" << endl; for (int i = 0; i < 100; i++) { cout << a[i] << " "; } cout << endl; cout << "come here" << endl; MergeSortUnrecursion(a, nLength); cout << "排序后：" << endl; for (int i = 0; i < nLength; i++) { cout << a[i] << " "; } cout << endl; system("pause"); return 0; }

运行结果：