高速排序之算法导论实现

#include <iostream>
using namespace std;
int partition(int *a,int p,int r)
{
	int x=a[r];
	int i=p-1;//note i important which is used for 
				//storage the number smaller than flag x=a[r]
	for (int j=p;j<r;j++)
	{
		if (a[j]<x)// if a[j] smaller than x=a[r],
					//exchange a[i+1] and a[j]
		{
			i++;
			int t=a[j];
			a[j]=a[i];
			a[i]=t;
		}
	}
	int t=a[i+1];// i+1 is the a[r] final position
				//  exchange a[r] and a[i+1]
	a[i+1]=a[r];
	a[r]=t;
	return i+1; //return the a[r] final position i+1
}
void quicksort(int *a,int p,int r)
{
	if (p<r)//the position lower than the higher
	{
		int q=partition(a,p,r);//q is the a[r] final position
						// depart the arry[p...q-1] and arry[q+1...r]
		quicksort(a,p,q-1);
		quicksort(a,q+1,r);
	}
}
int main()
{
	int arry[]={3,2,1,4,5,6,9,8,7,0};
	quicksort(arry,0,9);
	for (int i=0;i<10;i++)
		cout<<arry[i]<<" ";
	cout<<endl;
}

import java.util.Scanner;

public class QuickSort {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scanner=new Scanner(System.in);
		int n=Integer.parseInt(scanner.next());
		int a[]=new int[n];
		for (int i = 0; i < a.length; i++) {
			a[i]=Integer.parseInt(scanner.next());
		}
		quickSort(a, 0, n-1);
		for (int i = 0; i < a.length; i++) {
			System.out.print(a[i]+" ");
		}
	}
	
	public static void  quickSort(int a[], int p, int e) {
		if (p<e) {
			int q=partion(a, p, e);
			quickSort(a, p, q-1);
			quickSort(a, q+1, e);
		}
	}
	public static int partion(int a[], int p, int e) {
		int x=a[e];
		int j=p-1;
		for (int i = p; i < e; i++) {
			if (a[i]<x) {
				j++;
				int t=a[i];
				a[i]=a[j];
				a[j]=t;
			}
		}
		int t=a[j+1];
		a[j+1]=a[e];
		a[e]=t;
		return j+1;
	}
}	
//	public static <T> void  swap (T  a, T b) {
//		T temp=b;
//		b=a;
//		a=temp;
//	}