#include <stdio.h>
//this program is edited by 200624101101杨振平
//this paper's edited time is Nov 7th,2008
//define count of array
#define N 9
//main function
void main()
{
//declare QuickSort function
void QuickSort(int r[ ], int first, int end);
//initial the array r[] which require to sort
int r[N]={9,8,7,6,5,4,3,2,1};
//call the QuickSort function
QuickSort(r,0,N-1);
//print the sort result array
for(int i=0;i<N;i++)
printf("%d/t",r[i]);
}
//implement the QuickSort function
void QuickSort(int r[ ], int first, int end)
{
//declare Partition function
int Partition(int r[ ], int first, int end);
//declare variable which axis value location in the array
int pivot;
if (first<end) {
//problem divide conquer,pivot to store axis value location in the array
pivot=Partition(r, first, end);
//recurrence to left son array to do quick sort
QuickSort(r, first, pivot-1);
//recurrence to right son array to do quick sort
QuickSort(r, pivot+1, end);
}
}
//implement the Partition function
int Partition(int r[ ], int first, int end)
{
//declare and init variables
int i=first;
int j=end;
int temp;
//exchange records to partition the array
while (i<j)
{
//right scan
while (i<j && r[i]<= r[j]) j--;
if (i<j) {
//exchange the min record to the front
temp=r[j];
r[j]=r[i];
r[i]=temp;
i++;
}
//left scan
while (i<j && r[i]<= r[j]) i++;
if (i<j) {
//exchange the man record to the last
temp=r[j];
r[j]=r[i];
r[i]=temp;
j--;
}
}
//i is the last axis value location in the array
return i;
}
