参考 剑指offer的方法，比较简单。
#include<iostream>
#include <vector>
#include <set>
#include <functional>
#include <stdlib.h>
#include <stdio.h>
#include <string>
#include <sstream>
#include <list>
#include <map>
#include <stack>
#include <algorithm>
#include<iomanip>
using namespace std;
int RandomInRange(int start, int end)
{
return start + rand() % (end - start+1);
}
int partion(vector<int> &vi, int start, int end)
{
if (start < 0 || end >= vi.size() || start > end)
throw new exception("Invalid Patameter ");
int index = RandomInRange(start, end);
std::swap(vi[index], vi[end]);
int small = start - 1;
for (int i = start; i < end; i++)
{
if (vi[i] < vi[end])
{
//++small;
//if (i != small)
// std::swap(vi[i], vi[small]);
std::swap(vi[i], vi[++small]);
}
}
std::swap(vi[end], vi[++small]);
return small;
}
void QuickSort(vector<int>& vi, int start, int end)
{
if (start == end)
return;
int index = partion(vi, start, end);
if (index > start)
QuickSort(vi, start, index - 1);
if (index < end)
QuickSort(vi, index + 1, end);
}
void QuickSort(vector<int>& vi)
{
QuickSort(vi, 0, vi.size() - 1);
}
//***********************************************
void Merge(vector<int>& vi, vector<int>& tmp, int leftPos, int rightPos, int rightEnd)
{
if (leftPos >= rightPos || rightPos>rightEnd)
return;
int leftEnd = rightPos - 1;
int count = rightEnd - leftPos + 1;
int tmpPos = leftPos;
while (leftPos <= leftEnd && rightPos <= rightEnd)
{
if (vi[leftPos] <= vi[rightPos])
tmp[tmpPos++] = vi[leftPos++];
else
tmp[tmpPos++] = vi[rightPos++];
}
while (leftPos <= leftEnd)
tmp[tmpPos++] = vi[leftPos++];
while (rightPos <= rightEnd)
tmp[tmpPos++] = vi[rightPos++];
for (int i = 0; i < count; i++,rightEnd--)
vi[rightEnd] = tmp[rightEnd];
}
void MergeSort(vector<int>& vi, vector<int>& tmp, int start, int end)
{
if (start >= end)
return;
int mid = (start + end) / 2;
MergeSort(vi, tmp, start, mid);
MergeSort(vi, tmp, mid + 1, end);
Merge(vi, tmp, start, mid + 1, end);
}
void MergeSort(vector<int> vi)
{
vector<int> tmp(vi.size());
MergeSort(vi, tmp, 0, vi.size() - 1);
for (auto i : vi)
cout << i << " ";
cout << endl;
}
int main(int argc, char** args)
{
vector<int> vi = { 1, 5, 3, 4, 6, 9, 2, 7, 8 };
for (auto i : vi)
cout << i << " ";
cout << endl;
MergeSort(vi);
QuickSort(vi);
for (auto i : vi)
cout << i << " ";
cout << endl;
system("pause");
return 0;
}