#pragma once#include "InsertSort.h"int GetMidIndex(int* array, int left, int right)//优化：三数取中法，使选出的key值接近二分{	int mid = left + (right-left)/2;	if (array[left] < array[right])	{		if (array[right] < array[mid])//left
     
      
       = key)			--end;		if (begin < end)		{			swap(array[begin], array[end]);		}	}	if (array[begin] > array[right])	{		swap(array[begin], array[right]);		return begin;	}	else	{		return right;	}}int PartSort2(int* array, int left, int right){	assert(array);	int key = array[right];	int begin = left;	int end = right;	while (begin < end)	{		while (begin < end && array[begin] <= key)			++begin;		swap(array[begin], array[end]);		while (begin < end && array[end] >= key)			--end;		swap(array[end], array[begin]);	}	return begin;}int PartSort3(int* array, int left, int right){	int midIndex = GetMidIndex(array, left, right);	swap(array[right], array[midIndex]);	int key = array[right];	int cur = left;	int prev = left-1;	while (cur < right)	{		if (array[cur] < key && ++prev != cur)			swap(array[cur], array[prev]);		++cur;	}	swap(array[++prev], array[right]);	return prev;}void QuickSort(int* array, int left, int right){	assert(array);	if (left >= right)	{		return;	}	if (right-left < 50)//优化：当区间小于一定值后使用其他方法排序	{		InsertSort(array+left, right-left+1);	}	int div = PartSort3(array, left, right);	QuickSort(array, left, div-1);	QuickSort(array, div+1, right);}void QuickSortTest(){	int array[] = {0, 4, 9, 5, 8, 3, 7, 1, 2, 9};	QuickSort(array, 0, sizeof(array)/sizeof(array[0])-1);	for (size_t i = 0; i < sizeof(array)/sizeof(array[0]); ++i)	{		cout<
       
        <<" ";	}	cout<
       
      
     

非递归写法：

#include 
     
      void QuickSort_NonR(int* a, int left, int right){	assert(a);	stack
      
        s;	s.push(right);	s.push(left);	while (!s.empty())	{		int begin = s.top();		s.pop();		int end = s.top();		s.pop();		int div = PartSort1(a, begin, end);		if (begin < div-1)		{			s.push(div-1);			s.push(begin);		}		if (div+1 < end)		{			s.push(end);			s.push(div+1);		}	}}