// youhua.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include<stdio.h> 
#include<stdlib.h> // 隨機數(shù)的函數(shù)用到 
#include<time.h> // clock函數(shù)要用到 
#include <iostream.h>
//#include "time.h"


void InsertSort(int A[],long low,long high)
{
	for (long i = low; i <high; i++)
	{
		int t = A[i];
		long j = i;
		while ((j > 0) && (A[j - 1] > t))
		{
			A[j] = A[j - 1];
			j--;
		}
		A[j] = t;
	}
}
void Swap( int &i, int &j)
//只有兩個元素時直接交換
{
	int t;
	t = i;
	i = j;
	j = t;
}
int Partition(int A[], long low, long high)
{
	int p;
	p = A[low];
	while (low < high)
	{
		while (low < high && A[high] >= p)
		{
			high--;
		}
		if (low != high)
		{
			Swap(A[low], A[high]);
			low++;
		}
		while (low < high && A[low] <= p)
		{
			low++;
		}
		if (low != high)
		{
			Swap(A[low], A[high]);
			high--;
		}
	}
	return low;
}

int p1;
void QuickSort(int A[], long low, long high,int k)
{
				
	if (low < high) 
	{
		if(high-low<k)          
		{
			return;
			
		}
		else{
			int p1 = Partition(A, low, high);
			QuickSort(A, low, p1 - 1,k);
			QuickSort(A, p1 + 1, high,k);
		}
	}
}



//快速排序優(yōu)化
void OptimizedQuickSort(int A[], long low, long high,int k)
{   
	//只有一個數(shù)時無需交換
	if (high <= low)
	{
		return;
	}


	QuickSort(A, low, high,k);
	InsertSort(A,low,high);
}


void main()
{
	clock_t start, finish;
	double   duration;
	int i;
	
	int length=100000000;
	int *A=new int[length];
    int k;
	long low=0 ;
    long high=1000000;
	cout<<"輸入規(guī)模n為"<<high<<endl;
	for(k=1;k<500;k=k+20)
	{
	
	start = clock();

	srand((unsigned)time(NULL)); //隨機數(shù)的種子器 
	for(i=0;i<high+1;i++) //賦值 
	{A[i]=rand()%high+1; }


	
	OptimizedQuickSort(A, low, high, k);
	
	   finish = clock();
	   duration = (double)(finish - start);
	   cout<<"當(dāng)k值取"<<k<<"時"<<" "<<"運行時間是："<<duration<<"ms"<<endl;
	   
}

}