用于普通和模板版本STL向量的归并排序和选择排序算法。

• 下载源文件 - 7 Kb

引言

归并排序算法和选择排序算法用 C++ 实现（普通版本和模板版本）。

归并排序 A[1..n]

1. 如果输入序列只有一个元素

– 返回

2. 将输入序列划分为两半

3. 使用相同的算法对两个子序列进行排序

4. 合并两个排序后的子序列以形成输出序列

分而治之

• 这是一种算法设计范例，包含以下步骤

– 分：将问题分解为更小的

子问题

– 治：递归地解决每个子问题

递归地

– 合：将每个子问题的解决方案组合起来，形成问题的解决方案

归并排序 – O(N * Log N)

• 假设您要对 250,000,000 个项目进行排序

N = 250,000,000

N*Log N = 250,000,000 * 28

假设您可以执行 1 次操作/纳秒

7.25 秒

归并排序分析

MergeSort(A, left, right) T(n)

if (left < right)             O(1)

    mid := (left + right) / 2;         O(1)

   MergeSort(A, left, mid);         T(n/2)

   MergeSort(A, mid+1, right);         T(n/2)

   Merge(A, left, mid, right);         O(n)


Statement Work

当 n = 1 时，T(n) = O(1)，

当 n > 1 时，2T(n/2) + O(n)

当 n = 1 时，T(n) = O(1)，

当 n > 1 时，2T(n/2) + O(n)

递归方程

请使用下面的代码

// Sorting2.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"

#include "Sorting2.h"
#include <math.h>
#include <string>
#include <vector>
#include <algorithm>
#include <iterator>

#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif

/////////////////////////////////////////////////////////////////////////////
// The one and only application object

CWinApp theApp;
void SelectionSort(vector<int>& rData)
{
 int nLen = rData.size();
 if (nLen < 2)
  return;

 for (int nIndex = 0; (nIndex < (nLen - 1)); nIndex++){

  int nKey = rData[nIndex];
  int nMatchingIndex = nIndex;
  for (int nFindKey = (nIndex + 1); (nFindKey < nLen); nFindKey++){

   int& nData = rData[nFindKey];
   if (nData < nKey)
    nMatchingIndex = nFindKey, nKey = nData;
  }
  if (nMatchingIndex != nIndex)
   swap(rData[nIndex], rData[nMatchingIndex]);
 }
}

template<class _II>
void SelectionSort(_II _F, _II _L)
{
 if (_F == _L)
  return;

 for (; (_F != _L); _F++){

  _II _K = _F;
  _II _X = _F; //Save the matching index...
  _II _T = _F;
  for (_II _FI = ++_T; (_FI != _L); _FI++){

   if (*_FI < *_K)
    _X = _K = _FI;
  }
  if (_F != _X)
   swap(*_F, *_X);
 }
}
/*
MergeSort(A, left, right)   T(n) 
BEGIN
if (left < right)     O(1)
 mid := (left + right) / 2;  O(1)
 MergeSort(A, left, mid);  T(n/2)
 MergeSort(A, mid+1, right);  T(n/2)
 Merge(A, left, mid, right);  O(n)
END
*/
void Merge(vector<int>& rData, int nLeft, int nMid, int nRight)
{
 //Left  = 0;
 //Mid   = 3;
 //Right = 7;
 int nLeftArrayLen  = (nMid - nLeft) + 1;
 int nRightArrayLen = (nRight - nMid);
 
 vector<int> LeftArray, RightArray;
 LeftArray.resize(nLeftArrayLen);
 RightArray.resize(nRightArrayLen);
 
 vector<int>::iterator itrFirst, itrLast;
 
 //Create the left sub array...
 itrFirst = rData.begin() + nLeft;
 itrLast  = itrFirst + nLeftArrayLen;
 copy(itrFirst, itrLast, LeftArray.begin());
 
 //Create the right sub array...
 itrFirst = rData.begin() + nMid + 1;
 itrLast  = itrFirst + nRightArrayLen;
 copy(itrFirst, itrLast, RightArray.begin());

 int nLIndex = 0;
 int nRIndex = 0;
 int nCopyIndex = nLeft;
 for (; (nCopyIndex <= nRight && 
  nLIndex < nLeftArrayLen && 
  nRIndex < nRightArrayLen);){
 
  if (LeftArray[nLIndex] <= RightArray[nRIndex])
   rData[nCopyIndex++] = LeftArray[nLIndex++];
  else
   rData[nCopyIndex++] = RightArray[nRIndex++];
 }
 //Copy the remaining elements from the left subarray to main array...
 while (nCopyIndex <= nRight && nLIndex < nLeftArrayLen)
  rData[nCopyIndex++] = LeftArray[nLIndex++];
 //Copy the remaining elements from the right subarray to main array...
 while (nCopyIndex <= nRight && nRightArrayLen)
  rData[nCopyIndex++] = RightArray[nRIndex++];
}

void MergeSort(vector<int>& rData, int nLeft, int nRight)
{
 if (nLeft < nRight){

  int nMid = ((nLeft + nRight) / 2);
  MergeSort(rData, nLeft, nMid);
  MergeSort(rData, nMid + 1, nRight);
  Merge(rData, nLeft, nMid, nRight);
 }
}

//This Temlate verion works only for "vectors" of any native and user defined data types
//that supports the <=, =(assign) operators.
//Template merge for vectors...
template<class _Type, class _II>
void Merge(_II _Left, _II _Mid, _II _Right)
{
 //Left  = 0;
 //Mid   = 3;
 //Right = 7;
 size_t nLeftArrayLen  = (_Mid - _Left) + 1;
 size_t nRightArrayLen = (_Right - _Mid);
 
 _Type LeftArray, RightArray;
 LeftArray.resize(nLeftArrayLen);
 RightArray.resize(nRightArrayLen);
 
 _II itrFirst, itrLast;
 
 //Create the left sub array...
 itrFirst = _Left;
 itrLast  = itrFirst + nLeftArrayLen;
 copy(itrFirst, itrLast, LeftArray.begin());
 
 //Create the right sub array...
 itrFirst = (_Mid + 1);
 itrLast  = itrFirst + nRightArrayLen;
 copy(itrFirst, itrLast, RightArray.begin());
 
 DWORD nLIndex = 0;
 DWORD nRIndex = 0;
 _II _CopyIndex = _Left;
 while (nLIndex < nLeftArrayLen && nRIndex < nRightArrayLen && _CopyIndex <= _Right){
  if (LeftArray[nLIndex] <= RightArray[nRIndex])
   *_CopyIndex++ = LeftArray[nLIndex++];
  else
   *_CopyIndex++ = RightArray[nRIndex++];
 }
 //Copy the remaining elements from the left subarray to main array...
 while (nLIndex < nLeftArrayLen && _CopyIndex <= _Right)
  *_CopyIndex++ = LeftArray[nLIndex++];
 //Copy the remaining elements from the right subarray to main array...
 while (nRIndex < nRightArrayLen && _CopyIndex <= _Right)
  *_CopyIndex++ = RightArray[nRIndex++];
}
//Template merge sort for vectors...
template<class _Type, class _II>
void MergeSort(_II _Left, _II _Right)
{
 if (_Left < _Right){
 
  _II _Mid = _Left + ((_Right - _Left) / 2);
  MergeSort<_Type>(_Left, _Mid);
  MergeSort<_Type>(_Mid + 1, _Right);
  Merge<_Type>(_Left, _Mid, _Right);
 }
}

using namespace std;
int _tmain(int argc, TCHAR* argv[], TCHAR* envp[])
{
 int nRetCode = 0;
 
 // initialize MFC and print and error on failure
 if (!AfxWinInit(::GetModuleHandle(NULL), NULL, ::GetCommandLine(), 0))
 {
  // TODO: change error code to suit your needs
  cerr << _T("Fatal Error: MFC initialization failed") << endl;
  nRetCode = 1;
 }
 else
 {
  // TODO: code your application's behavior here.
  CString strHello;
  strHello.LoadString(IDS_HELLO);
  cout << (LPCTSTR)strHello << endl;
 }

#define CONT_TYPE int
#define STL_VECTOR_TYPE vector<CONT_TYPE>

 STL_VECTOR_TYPE Data;
 typedef STL_VECTOR_TYPE::iterator itrCont;
 srand(32);
 Data.resize(9999);
 /*
 Data[0] = 5;
 Data[1] = 2;
 Data[2] = 6;
 Data[3] = 7;
 Data[4] = 4;
 Data[5] = 3;
 Data[6] = 2;
 Data[7] = 1;
 Data[8] = 1;
 */
 generate(Data.begin(), Data.end(), rand);
 random_shuffle(Data.begin(), Data.end());
 
 copy(Data.begin(), Data.end(), ostream_iterator<CONT_TYPE>(cerr, " "));
 cerr << "\n";

 time_t t1 = 0, t2 = 0;
 time(&t1);
 {
  //SelectionSort(Data);
  
  //Template version
  //SelectionSort(Data.begin(), Data.end());
  
  //MergeSort(Data, 0, Data.size() - 1);
  
  //Template version
  MergeSort<STL_VECTOR_TYPE>(Data.begin(), Data.end() -1);
 }
 time(&t2);
 time_t timediff = difftime(t2, t1);
 copy(Data.begin(), Data.end(), ostream_iterator<CONT_TYPE>(cerr, "\n"));
 
 cerr << "\n\n" << timediff << "\n";
 return nRetCode
}

参考文献

• 计算机和编程入门