参考 剑指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;}