optimizedquicksort.cpp

OptimizedQuickSort 理论上快速排序的平均时间复杂度是nlgn.最差是n^2. 但实际实现中可能表现的不如插入排序等其他算法。

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

#include "stdafx.h"
#include<stdio.h> 
#include<stdlib.h> // 随机数的函数用到 
#include<time.h> // clock函数要用到 
#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);
		}
	}
}



//快速排序优化
void OptimizedQuickSort(int A[], long low, long high,int k)
{   
	//只有一个数时无需交换
	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<<"输入规模n为"<<high<<endl;
	for(k=1;k<500;k=k+20)
	{
	
	start = clock();

	srand((unsigned)time(NULL)); //随机数的种子器 
	for(i=0;i<high+1;i++) //赋值 
	{A[i]=rand()%high+1; }


	
	OptimizedQuickSort(A, low, high, k);
	
	   finish = clock();
	   duration = (double)(finish - start);
	   cout<<"当k值取"<<k<<"时"<<" "<<"运行时间是："<<duration<<"ms"<<endl;
	   
}

}