quicks.cpp

非常全的排序算法c实现

/*算法思想简单描述：
它的基本思想是通过一趟扫描后，使得排序序列的长度能大幅度地减少。
快速排序通过一趟扫描，就能确保某个数（以它为基准点）的左边各数都比它小，
右边各数都比它大。然后又用同样的方法处理它左右两边的数，
直到基准点的左右只有一个元素为止.*/
#include<iostream.h>//快速排序
#define MAX 4
void quick_sort(int a[],int low,int high);
int main()
{ 
    int *p,i,n,a[MAX];
    p=a;
	n=MAX;

	cout<<"Input "<<n<<" number for sorting :"<<endl;
    for(i=0;i<MAX;i++)
	{
	  cin>>a[i];
	}
	cout<<endl;
    quick_sort(p,0,MAX-1);
  
	cout<<"After quick_sort:"<<endl;
    for(i=0;i<MAX;i++)
	{
	 cout<<a[i]<<" ";
	}
    cout<<endl;
	return 0;
}

void quick_sort(int a[],int low,int high)//快速排序
{
  int i,j,t;

  if (low<high) //要排序的元素起止下标,保证小的左边,大的右边.以下标为low的元素为基准点
  {
    i=low;
    j=high;
    t=a[low]; //暂存基准点的数

    while(i<j) //循环扫描*
	{
       while(i<j&&a[j]>t) //在右边的只要比基准点大仍放在右边
	   {
          j--; //前移一个位置
	   }

       if(i<j) 
	   {
         a[i]=a[j]; //上面的循环退出：即出现比基准点小的数，替换基准点的数
         i++; //后移一个位置，并以此为基准点
	   }

       while (i<j&&a[i]<=t) /*在左边的只要小于等于基准点仍放在左边*/
	   {
          i++; //后移一个位置
	   }

       if(i<j)
	   {
         a[j]=a[i]; //上面的循环退出：即出现比基准点大的数，放到右边
         j--; //前移一个位置
	   }
	}

  a[i]=t; //一遍扫描完后，放到适当位置
  quick_sort(a,low,i-1);  //对基准点左边的数再执行快速排序
  quick_sort(a,i+1,high);  //对基准点右边的数再执行快速排序
 }
}