// Fast_Sort.cpp : Defines the entry point for the console application.
//快速排序，利用遞歸的方法
//遞歸一定是有返回條件的，只有這樣才曾結(jié)束遞歸，切記這一點(diǎn)

#include "stdafx.h"
#include "stdio.h"
#include "string.h"
typedef int status;
#define OK 0
#define MaxNum 100
int MidArray[MaxNum];   //定義一個(gè)全局變量來存儲(chǔ)數(shù)據(jù)

/**此函數(shù)的作用是快速排序
@param data  -----
@param start  -----
@param length  -----
@return  int ----- 返回一個(gè)整數(shù)值
*/
status Fast_sort(int data[],int start,int length)
{
	int mid,i,j=0,k=0;
	int position=0;//記住中間者的位置
	if (length<=1)
	{
        return OK;
	}
	mid=data[start];  //首先是找到第一個(gè)對(duì)比的數(shù)
	for(i=start+1;i<length+start;i++)
	{
		//從第二個(gè)數(shù)開始對(duì)比
	    if(data[i]<=mid)  //只要小于等于的情況
		{
			MidArray[position]=data[i];
			position++;
		}
		else
		{
			MidArray[length-1-k]=data[i];   //這樣就沒有浪費(fèi)MidArray的空間了 
			k++;
		}
	//	j++;
	} //這樣就分開了
	//下一步就是調(diào)整
    //	data[start+position]=mid;
	//  j=0;           //將j再初始化一下
	for(i=start;i<length+start;i++)
	{
		
		data[i]=MidArray[i-start];  //再賦給原數(shù)組
		if((i-start)==position)     //找到mid的位置
		{
			data[i]=mid;
		}
   //     printf("%d  ",data[i]);
	}
   
	//下一步再遞歸調(diào)整兩邊的，注意q位置的特性
    Fast_sort(data,start,position);
	Fast_sort(data,position+1,length-position-1);
   
}


int main(int argc, char* argv[])
{
   //printf("Hello World!\n");
	int data[10]={5,3,6,1,7,8,4,45,55,66};
	int i;
	Fast_sort(data,0,7);
	for(i=0;i<10;i++)
	{
		printf("%d  ",data[i]);
	}
	return 0;
}