快速排序

package com.wlh;

public class QuickSort {

	public static void qucikpass(int[] r, int left, int right) {
		int i, j;
		int middle;
		i = left;
		j = right;
		middle = r[i];
		while (i < j) {
			 //从右向左找小于middle的数组值
			while (r[j] >= middle && i < j)
				j--;
			//i和j没有碰到一起
			if (i < j) {
				//从右向左找到小于middle的数组值，然后r[i]位置上的数组值被其替换
				r[i] = r[j];
				i++;
				//从左向右找大于middle的数组值
				while (r[i] <= middle && i < j)
					i++;
				if (i < j) {
					//从左向右找大于middle的数组值，然后r[j]位置上的数组值被其替换
					r[j] = r[i];
					j--;
				}
			}
		}
		
		//i==j时，此时数组下标所指的位置就是middle该去的位置，将middle放入该位置，
		//此时r[i]左边的数组值都小于r[i]，右边的都大于r[i]
		r[i] = middle;//第一躺排序
		
		//递归调用次函数，对r[i]左边的数组进行排序
		if (left < i) {
			qucikpass(r, 0, i);
		}

		//递归调用次函数，对r[i]右边的数组进行排序
		if (right > j) {
			qucikpass(r, j +1, right);
		}
	}

	public static void main(String[] args) {
		
		//int[] pData = new int[] { 35, 40, 45, 10, 15 };
		int[] pData = new int[10];
		for (int i = 0; i < 10; i++){
			pData[i] = (int) (Math.random() * 100);
			System.out.print(pData[i] + " ");
		}
		System.out.println("\n======================== ");
		QuickSort.qucikpass(pData, 0, pData.length - 1);
		for (int i = 0; i < pData.length; i++)
			System.out.print(pData[i] + " ");
	}
}

低效率算法：

package com.wlh;

public class QuickSort3 {

	public static void qucikpass(int[] r, int left, int right) {
		int i, j;
		int middle,temp;
		i = left;
		j = right;
		middle = r[i];
		while (i < j) {
			 //从右向左找小于middle的数组值
			while (r[j] >= middle && i < j)
				j--;
			//i和j没有碰到一起
			if (i < j) {
				//从右向左找到小于middle的数组值，然后r[i],r[j]位置上的数组值交换
				temp=r[i];
				r[i] = r[j];
				r[j]=temp;
				i++;
				//从左向右找大于middle的数组值
				while (r[i] <= middle && i < j)
					i++;
				if (i < j) {
					//从左向右找大于middle的数组值，然后r[i],r[j]位置上的数组值交换
					temp=r[i];
					r[i] = r[j];
					r[j]=temp;
					j--;
				}
			}
		}
		
		
		//递归调用次函数，对r[i]左边的数组进行排序
		if (left < i) {
			qucikpass(r, 0, i);
		}

		//递归调用次函数，对r[i]右边的数组进行排序
		if (right > j) {
			qucikpass(r, j +1, right);
		}
	}

	public static void main(String[] args) {
		
		//int[] pData = new int[] { 35, 40, 45, 10, 15 };
			int[] pData = new int[10];
		for (int i = 0; i < 10; i++){
			pData[i] = (int) (Math.random() * 100);
			System.out.print(pData[i] + " ");
		}
		System.out.println("\n======================== ");
		QuickSort3.qucikpass(pData, 0, pData.length - 1);
		for (int i = 0; i < pData.length; i++)
			System.out.print(pData[i] + " ");
	}
}