算法研究系列---快速排序

快速排序是由冒泡排序改进而来的.

算法思想:  

             在待排序的n个记录中，选取其中任意一个记录(通常是第一个)，把该记录放在适当的位置后，则数据序列被划分为两部分。所有比该记录小的记录均放置到该记录的前一部分；所有笔该记录大的记录均放置到该记录的后一部分，并把该记录排在这两部分的中间(称该记录为记录归位)，这个过程成为一趟快速排序。   之后对所有的两部分分别重述这一过程，直至每部分内只有一个记录或为空为止。简而言之,每趟使得一个记录放到适当位置，将表一分为二，对子表按递归的方式继续这种划分，直至划分的子表长度为1或0

package switchsort;

public class QuickSort {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] a = new int[] { 5, 1, 9, 8, 6, 3, 2, 8, 6,584,54,125,6,5,147,85478,241,2412,365,256,985,589,895,745,487 };
		a = quickSort(a, 0, a.length - 1);
		for (int i = 0; i < a.length; i++) {
			System.out.print(a[i] + "  ");
		}
	}

	public static int[] quickSort(int[] a, int start, int end) {
		int i = start;
		int j = end;
		int tmp;
		int middle = a[(start + end) / 2];
			while (i < j) {
				while (a[j] > middle) {
					j--;
				}
				while (a[i] < middle) {
					i++;
				}
				if (i <= j) {
					tmp = a[i];
					a[i] = a[j];
					a[j] = tmp;
					i++;
					j--;
				}
			}
			if (j > start) {
				quickSort(a, start, j);
			}
			if (i < end) {
				quickSort(a, i, end);
			}
		return a;
	}

	
}

 

评论

3 楼 yuxingfirst 2011-10-10  

Mon__cherie 写道

无意中发现一个bug

当数组中有两个一样的数字事   while循环会死循环
  LZ注意了么？

嗯 看到了  谢谢！ 代码已修正

2 楼 Mon__cherie 2011-10-09  

无意中发现一个bug

当数组中有两个一样的数字事   while循环会死循环
  LZ注意了么？

1 楼 fka2004 2011-10-09  

学习了，谢谢~~