改進的快速排序算法

快速排序算法的改進思路

1.選取好的基準，是兩邊的資料個數盡量的均勻

   取數組的第一個，中間，最後一個資料，取三個數中第二大的數作為基準

2. 不遞歸

3.與插入結合，當段内的數組個數小于等于16的時候，使用插入排序

具體實作代碼如下：

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <time.h>

/**********************************************
*改進的快速排序
*1.取第一個和最後一個和中間元素進行排序，
*  取排序好了的中間元素當基準元素
*2.不遞歸
*3.與插入結合
***********************************************/

//給三個數進行排序并傳回中間資料
int getmid(int start, int mid, int end)
{
	int t;
	if(start > mid)
	{
		t = start;
		start = mid;
		mid = t;
	}

	if(mid > end)
	{
		t = mid;
		mid = end;
		end = t;
	}

	if(start > mid)
	{
		t = mid;
		mid = start;
		start = t;
	}
	return mid;
}

/*****************主函數**********************/
void main()
{
	int n;   //輸入數組的長度

	printf("請輸入數組的長度：\n");
	scanf("%d",&n);

	int *a = (int *)malloc(n*sizeof(int));
	//int a[10] = {0,94,25,29,3,45,1,35,28,99};
	int *b = (int *)malloc(n*sizeof(int));  //使用隊列将程式改為非遞歸
	int head = 0;                  //隊頭
	int rear = 0;                  //隊尾
    srand(time(0));

	//初始化數組
	for(int i=0; i<n; i++)
	{
		a[i] = rand()%100;
	}

	//輸出排序前的數組
	printf("\n");
	printf("輸出排序前的數組：\n");
	for(i=0; i<n; i++)
	{
		printf("%d\t",a[i]);
	}

	//排序
	b[rear++]=0; //現将頭放到隊列中，再将尾放到隊列中
	b[rear++]=n-1;
	while(head != rear)
	{
		int start = b[head++];
		int end = b[head++];
		int mid = (start+end)/2;
		
		if(end-start <=16)
		{//使用插入排序
			for(i=1; i<=end; i++)
			{
				int temp=a[i];
				for(int j=i-1; j>=0; j--)
				{
					if(a[j]>temp)
					{
						a[j+1]=a[j];
					}
					else
					{
						break;
					}
				}
				a[j+1] = temp;
			}
		}
		else
		{//使用快速排序
			int front=start;
			int tail = end;
			int temp = getmid(a[front],a[mid],a[tail]);
			int t = temp;
			temp = a[start];
			a[start] = t;
			while(tail > front)
			{
				while(a[tail]>temp && tail>front)tail--;
				if(tail>front)
				{
					a[front++] = a[tail];
				}
				while(a[front]<temp && front<tail)front++;
				if(tail>front)
				{
					a[tail--]=a[front];
				}
			}
			a[front] = temp;
			if(front-1 > start)
			{
				b[rear++] = start;
				b[rear++] = front-1;
			}
			if(end > front+1)
			{
				b[rear++] = front+1;
				b[rear++] = end;
			}
		}
	}

	//輸出排序後的數組
	printf("\n");
	printf("輸出排序後的數組：\n");
	for(i=0; i<n; i++)
	{
		printf("%d\t",a[i]);
	}

	free(a);
}