经典算法:快速排序

我去去去的,搞个快速排序搞了那么长时间,看百度百科里面的解释,真是不知道是我理解能力低呢,还是我真的很笨...哎,总之是我的原因,哈哈~再来仔细分析一下快速排序:

以下是百度百科中的解释:

"

设要排序的数组是A[0]……A[N-1]，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。整个排序就是一个递归的过程.

一趟快速排序的算法是：

　　1）设置两个变量I、J，排序开始的时候：I=0，J=N-1；

　　2）以第一个数组元素作为关键数据，赋值给key，即 key=A[0]；

　　3）从J开始向前搜索，即由后开始向前搜索（J=J-1），找到第一个小于key的值A[J]，并与A[I]交换；

　　4）从I开始向后搜索，即由前开始向后搜索（I=I+1），找到第一个大于key的A[I]，与A[J]交换；

　　5）重复第3、4、5步，直到 I=J； (3,4步是在程序中没找到时候j=j-1，i=i+1，直至找到为止。找到并交换的时候i， j指针位置不变。另外当i=j这过程一定正好是i+或j-完成的最后另循环结束。)

"

其中,我读了老长时间没有读懂第三步和第四步的意思...

现在来总结一下:首先,快速排序的思想,就是取数组中某个数作为pivot,这里用最右边的那个吧,然后剩下的先分一下类,怎么分呢?这样分:分成左右两个部分,左边的要比这个pivot小(或者大),右边的要比这个pivot大(或者小),然后,把这个pivot插入到左右部分的中间,这样呢,就完成了一次排序,然后判断一下进行递归排.额...不知道说清楚没有,反正就是这个样子啦.

要实现这个思路,要想想用什么办法呢,用什么办法呢,用什么办法呢?一?有了,这样吧,肯定是循环啦,在循环中,有两个标签,一个是在左边晃,一个是在右边晃,左边的要从头往右找,找到大于那个pivot的值以后,好,停下,等着右边找,等右边从右往左找到比pivot小的值后,也停下,这样,都知道了是该交换了.

那么,循环里面就要先让左边标签动,如果这次不行的话,就应该+1,并且其他的不执行任何操作,右边循环的时候同理,因此,我们应该安排一个continue来控制+1后赶紧跳出去.只有左边和右边都不continue了,才到了两个要交换的时候.

恩恩,核心的思路就应该是这样的.

还有一个值得注意的是,当左边的标签和右边的标签重叠的时候,就应该是跳出循环的时候了,但是,跳出后还是要判断一下当前这个标签指向的值是大于pivot还是小于pivot,如果是小的话,那可不能换,还要继续往右走.

最后才去交换pivot和这个标签.

这样呢,就完成了一次循环.下面就是进行判断是不是要递归了.要注意的是,判断的条件了.

好啦,啰嗦完了,放上代码,欢迎扔砖,嘻嘻~

package com.xingyun.pi;

import java.util.Calendar;
import java.util.Date;

/**
 * 实现快速排序的算法
 * 
 * @author xingyunpi
 * 
 */
public class Sorts {
	static int data[] = { 5, 2, 6, 8, 1, 3};// 要排序的数组

	public static void main(String args[]) {
		for (int i = 0; i < data.length; i++) {
			System.out.print(data[i] + ",");
		}
		System.out.println("-----------原始");		
		int end = data.length - 1;
		int start = 0;
		int fastsort[] = quicksort(data,start,end);
		for (int i = 0; i < fastsort.length; i++) {
			System.out.print(fastsort[i] + ",");
		}
		System.out.println("-----------快速");
	}


			
	/**
	 * 伤不起的算法:快速排序
	 * 把最左边,或者是最右边的最为pivot.然后讲剩下的n-1个数进行排序,
	 * 最后让pivot和中间那个交接的地方交换
	 * @param data
	 * @param start
	 * @param end
	 * @return
	 */
	public static int[] quicksort(int data[],int start,int end){
		int left = start;
		int right = end - 1;
		int pivot = data[end];
		while(left < right){
			if (data[left] < pivot){//不参与交换
				left++;
				continue;
			}
			if(data[right] > pivot){//不参与交换
				right--;
				continue;
			}
			//如果两个都不满足,就会执行下面的程序,也就是说左右都应该交换了
			swap(data,left,right);
			left++;
		}
		//这个时候,left=right
		//确定与end交换的那个数,如果是小的话(中间数是小于end的情况),left还应该往右移
		if(data[left] < pivot){
			left++;
		}
		swap(data,left,end);//将最右边的数插到中间来
		if(left > start){//这里一定是写大于start,因为要考虑右边的排序
			quicksort(data,start,left-1);
		}
		if(left < end){//同样,这里一定要是end
			quicksort(data,left + 1,end);
		}
		return data;
	}

	/**
	 * 打印当前时间,是为了比较各种排序的效率
	 */
	public static void printtime() {
		Date time = Calendar.getInstance().getTime();
		System.out.println(time.toString());
	}
	/**
	 * 数组data的第i个数和第j个数进行交换
	 * 
	 * @param data
	 * @param i
	 * @param j
	 */
	public static void swap(int data[], int i, int j) {
		int temp;
		temp = data[i];
		data[i] = data[j];
		data[j] = temp;
	}
}

(*^__^*) 嘻嘻……come on!