QuickSort（快速排序自我模板）

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#define large 100055
#define Cutoff (3) //这里是定义的快排最小递归数量就是包含了三个元素的时候; 
using namespace std;
int A[large];
int midvalue(int A[],int left,int right)  //quicksort取三元素中间值作为枢纽元，并且进行了三次排序方便后面的处理; 
{
       int center=(left+right)/2;if(A[left]>A[center]) swap(A[left],A[center]);if(A[left]>A[right]) swap(A[left],A[right]);if(A[center]>A[right]) swap(A[right],A[center]);swap(A[center],A[right-1]);return A[right-1];
}
void InsertionSort(int A[],int left,int n)
{
    for(int i=1;i<n;i++){
    for(int j=0;j<n-i;j++){
    if(A[left+j]>A[left+j+1]){
    int t;t=A[j+left];A[j+left]=A[j+left+1]; A[j+left+1]=t; }}}
}
void Sort(int A[],int Left,int Right)
{
    int Point;int i,j;   //这里非常重要，这里的i是枢纽元左边数组的指针，j是枢纽元右边数组的指针 if(Left+Cutoff<=Right){
       Point = midvalue(A,Left,Right);  //这里是三元素法取枢纽元； i=Left,j=Right-1;   //这里的设计非常精妙。这样做一般不会出错； while(1){
    while(A[++i]<Point){
    }while(A[--j]>Point){
    }   //这里的设计也很精妙，为什么i++与j++就不能实现了，原因是若A[i]==A[j]==Point此时则会出现无线循环；if(i<j)swap(A[i],A[j]);elsebreak; }swap(A[i],A[Right-1]); //将枢纽元移动到正确的 位置上Sort(A,Left,i-1);Sort(A,i+1,Right); }else InsertionSort(A,Left,Right-Left+1);
}
int main()
{
       cout<<"please put your wanting sort numbers: ";int n;cin>>n;for(int i=1;i<=n;i++){
    cin>>A[i];}Sort(A,1,n);for(int i=1;i<=n;i++)cout<<A[i]<<" ";return 0;
}