快速排序

原创
2013/10/04 13:13
阅读数 102
 * 设数组a中存放了n个数据元素,low 为数组的低端下标,high为数组的高端下标,从数组a中任取一个元素(这个元素通常取a[0])作为标准元素,
 * 一该标准元素来调整数组a中其他各个元素的位置,使排在标准元素前面的元素均小于标准元素,而排在标准元素后面均小于标准元素。
 * 这样一次排序过程后,一方面将标准元素放在了未来排好序的数组中该标准元素应该在的位置。

 * 另一方面将数组中的元素以标准元素为中心分成了两个子数组,位于标准元素左边的均小于标准元素,位于标准元素右边的均大于等于标准元素。

import java.util.Arrays;

public class QuickSort {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int arr[] = {60,55,48,37,10,90,84,36,5,10};
		quickSort(arr,0,arr.length-1);
		System.out.println(Arrays.toString(arr));
	}
	
	private static int partition(int arr[],int low,int high){
		int i,j,temp;
		i = low;
		j = high;
		temp = arr[low];
		while(i<j){
			//扫描右端
			while(i<j && temp<arr[j]) {
				j--;
			}
			if(i<j){
				arr[i] = arr[j];
				i++;
			}
			
			//在数组的左端扫描
			while(i<j && arr[i]<temp){
				i++;
			}
			if(i<j){
				arr[j] = arr[i];
				j--;
			}
		}
		arr[i] = temp;
		return i;
	}
	
	public static void quickSort(int arr[],int low ,int high){
		if(low<high){
			int i = partition(arr, low, high);
			quickSort(arr, low, i-1);
			quickSort(arr, i+1, high);
		}
	}
	
}

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部