快速排序(Java实现).md

1.概述

快速排序和前面的冒泡排序一样,也是交换排序的一种,但是他是基于分治的算法思想,元素进行位置交换时可以跨度很大,而冒泡中只能进行相邻元素的交换,这样可以减少很多交换次数

它的基本思想是:通过一趟排序讲要排序的序列分成两个子部分,其中一部分的所有数据要比另一部分的所有数据小,然后再按照这个方法对两个子部分也分别进行快速排序,这个过程可以递归进行。

2.示意图

image image

Demo步骤解析:

1.一开始选定数组的最后一个元素5作为基准值,也就是最终排序结果应该是以5为界限划分为左右两边。

2.从左边开始,寻找比5大的值,然后与5进行调换(因为如果比5小的值本来就应该排在5前面,比5大的值调换之后就去到了5的后面),一路过来找到了7,将7与5调换,结束此次遍历。

3.从右边开始,由于7已经是上一轮排好序的便不再动它,从10开始,一路向左遍历,寻找比5小的值,然后与5进行调换(因为如果比5大的值本来就应该排在5后面,比5小的值调换之后就去到了5的后前面),一路过来找到了4,将4与5调换,结束此次遍历。

4.从左边开始,由于3和4都是前两轮已经排好序的便不再动它,从2开始,一路向右遍历,寻找比5大的值,然后与5进行调换(道理同步骤2),一路过来找到了9,将9与5调换,结束此次遍历。

5.从右边开始,由于排在9后面的那几个数字都是上几轮排好序的便不再动它,从1开始,一路向右遍历,寻找比5小的值,然后与5进行调换(道理同步骤3),一下子就找到了1,将1与5调换,结束此次遍历。

6.这个时候,发现5的左右两边都是排好序了的,所以结束此轮排序,5的左右两边抽出来各自进行下一轮的排序,规则同上,直到无法再拆分下去,即完成了整体的快速排序。

3.算法实现

public class QuickSort {
	
	/**
	 * 将数组的某一段元素进行划分,小的在左边,大的在右边
	 * @param a
	 * @param start
	 * @param end
	 * @return
	 */
	public static int divide(int[] a, int start, int end){
		//每次都以最右边的元素作为基准值
		int base = a[end];
		//start一旦等于end,就说明左右两个指针合并到了同一位置,可以结束此轮循环。
		while(start < end){
			while(start < end && a[start] <= base)
				//从左边开始遍历,如果比基准值小,就继续向右走
				start++;
			//上面的while循环结束时,就说明当前的a[start]的值比基准值大,应与基准值进行交换
			if(start < end){
				//交换
				int temp = a[start];
				a[start] = a[end];
				a[end] = temp;
				//交换后,此时的那个被调换的值也同时调到了正确的位置(基准值右边)
,因此右边也要同时向前移动一位
				end--;
			}	
			while(start < end && a[end] >= base)
				//从右边开始遍历,如果比基准值大,就继续向左走
				end--;
			//上面的while循环结束时,就说明当前的a[end]的值比基准值小,应与基准值进行交换
			if(start < end){
				//交换
				int temp = a[start];
				a[start] = a[end];
				a[end] = temp;
				//交换后,此时的那个被调换的值也同时调到了正确的位置(基准值左边),因此左边也要同时向后移动一位
				start++;
			}	
			
		}
		//这里返回start或者end皆可,此时的start和end都为基准值所在的位置
		return end;
	}
 
	/**
	 * 排序
	 * @param a
	 * @param start
	 * @param end
	 */
	public static void sort(int[] a, int start, int end){
		if(start >= end){
			//如果只有一个元素,或者没有元素,就不用再排下去了
			return;
		} 
		else{
			//如果不止一个元素,继续划分两边递归排序下去
			int partition = divide(a, start, end);
			sort(a, start, partition-1);
			sort(a, partition+1, end);
		}
			
	}
	
}

4.性能分析

最好的情况下,如果基准值刚好取在中间,这样能够减少递归划分的次数,最大效率的进行快速排序,此时的时间复杂度为O(nlogn)

最坏的情况下,每次只能划分出一个元素,因而总共需要(n-1)次划分,总的比较次数为(n-1)+(n-2)+...+1=n(n-1)/2,即退化为O(n^2)。

另外,快排是不稳定的,元素可以进行有跨度的交换,相同数值的元素之间的顺组可能被打乱。

快排的性能还是取决于基准值的选取,他决定了划分次数和比较次数。