fast_sort.cpp

主要实现了对快速排序算法的改进工作

// Fast_Sort.cpp : Defines the entry point for the console application.
//快速排序，利用递归的方法
//递归一定是有返回条件的，只有这样才曾结束递归，切记这一点

#include "stdafx.h"
#include "stdio.h"
#include "string.h"
typedef int status;
#define OK 0
#define MaxNum 100
int MidArray[MaxNum];   //定义一个全局变量来存储数据

/**此函数的作用是快速排序
@param data  -----
@param start  -----
@param length  -----
@return  int ----- 返回一个整数值
*/
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];  //首先是找到第一个对比的数
	for(i=start+1;i<length+start;i++)
	{
		//从第二个数开始对比
	    if(data[i]<=mid)  //只要小于等于的情况
		{
			MidArray[position]=data[i];
			position++;
		}
		else
		{
			MidArray[length-1-k]=data[i];   //这样就没有浪费MidArray的空间了 
			k++;
		}
	//	j++;
	} //这样就分开了
	//下一步就是调整
    //	data[start+position]=mid;
	//  j=0;           //将j再初始化一下
	for(i=start;i<length+start;i++)
	{
		
		data[i]=MidArray[i-start];  //再赋给原数组
		if((i-start)==position)     //找到mid的位置
		{
			data[i]=mid;
		}
   //     printf("%d  ",data[i]);
	}
   
	//下一步再递归调整两边的，注意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;
}