快速排序(quick sort)——数据结构与算法复习

public static <T extends Comparable<? super T>> void quickSort(T[] data,
			int beg, int end) {
		if (beg < end) {
			int partition = partition(data, beg, end);
			quickSort(data, beg, partition - 1);
			quickSort(data, partition + 1, end);
		}
	}

	private static <T extends Comparable<? super T>> int partition(T[] data,
			int beg, int end) {
		int left = beg;
		int right = end;
		// 用第一个元素作分区元素
		T p = data[beg];
		
		//从两边开始遍历
		while (left < right) {
			//从左向右遍历，直到遇到 一个比分区元素大的元素
			while (data[left].compareTo(p) <= 0 && left<right) {
				left++;
			}

			//从右向左遍历，直到遇到一个比分区元素小的元素
			while (data[right].compareTo(p) > 0) {
				right--;
			}

			if (left < right) {
				T temp = data[left];
				data[left] = data[right];
				data[right] = temp;
				left++;
				right--;
			}
		}
		
		//
		data[beg] = data[right];
		data[right]=p;
		return right;
	}