快速排序算法的原理及实现

快速排序
快速排序是冒泡排序的改进版，也是最好的一种内排序，还涉及到分治和递归，在很多面试题中都会出现，也是作为程序员必须掌握的一种排序方法。
冒泡排序中记录的比较和交换是在相邻的单元中进行，每次交换只能上移或者下移一个单元，因而总的比较和移动次数较多。

快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。
该方法的基本思想是：
1．先从数列中取出一个数作为基准数（简单起见可以取第一个数）。
2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。（分区）
3．再对左右区间重复第一步、第二步，直到各区间只有一个数。（递归）

快速排序算法的原理及实现

快速排序=冒泡+分治+递归
快速排序的过程：东拆西补或西拆东补，一边拆一边补

快速排序算法的实现

import java.util.Arrays;

public class TestQuickSort {	
	/**
	 * 分区，返回调整后基准数的位置（两个分区的边界）
	 * @param arr
	 * @param low
	 * @param high
	 * @return
	 */
	private static int partition(int []arr,int low,int high) {
		//指定两个指针，分别执行分区起始元素和结束元素
		int i = low;
		int j = high;
		//指定第一个元素是基准值，挖坑一个
		int x = arr[low];
		
		//生成队列
		while(i<j){
			//右边指针向左移动,直到找到小于基准值的元素
			while(i<j && arr[j]>=x){
				j--;
			}
			//使用右边元素填左边坑
			if(i<j){
				arr[i] = arr[j];
				i++;
			}			
			//左边指针向右移动,直到找到小于基准值的元素
			while(i<j && arr[i]<x){
				i++;
			}
			//使用左边元素填右边坑
			if(i<j){
				arr[j] = arr[i];
				j--;	
			}
		}
		//填最后的坑（基准值应该放的位置）
		arr[i] = x;//此时i==j
		
		//返回基准位置		
		return i;		
	}
	
	/**
	 * 快速排序
	 * @param arr
	 * @param low
	 * @param high
	 */
	private static void quickSort(int[] arr, int low, int high) {	
		if(low < high){
			//分区一次， 前小中基准后面大，返回基准数位置
			int n = partition(arr,low,high);			
			//对左边进行快速排序
			quickSort(arr,low,n-1);
			//对右边进行快速排序
			quickSort(arr,n+1,high);		
		}		
	}
	
	public  static void quickSort(int[] arr) {
		int low = 0;
		int high = arr.length-1;
		quickSort(arr,low,high);		
	}	
	
	public static void main(String[] args) {
		int arr[] = {72,6,57,88,60,42,83,73,48,85};
		//int arr[] = {72,83,83,83,83,83,83,73,83,85};
		System.out.println(Arrays.toString(arr));
		quickSort(arr);
		System.out.println(Arrays.toString(arr));
	}
}

快速排序算法的分析
1.当分区选取的基准元素为待排序元素中的最大或最小值时，为最坏的情况，时间复杂度和直接插入排序的一样，移动次数达到最大值
Cmax = 1+2+...+(n-1) = n*(n-1)/2 = O(n2) 此时最好时间复杂为O(n2)
2.当分区选取的基准元素为待排序元素中的"中值"，为最好的情况，时间复杂度为O(nlog2n)。
3.快速排序的空间复杂度为O(log2n). (用到了递归，当然占用空间多了)
4.当待排序元素类似[6,1,3,7,3]且基准元素为6时，经过分区，形成[1,3,3,6,7],两个3的相对位置发生了改变，所是快速排序是一种不稳定排序。

快速排序算法的分析2
时间效率：快速排序算法的运行时间依赖于划分是否平衡，即根据枢轴元素 pivot 将序列划分为两个子序列中的元素个数，
而划分是否平衡又依赖于所使用的枢轴元素。下面我们在不同的情况下来分析快速排序的渐进时间复杂度。

快速排序的最坏情况是每次进行划分时，在所得到的两个子序列中有一个子序列为空。此时，算法的时间复杂度T(n) = T p (n) + T(n-1)，
其中T p (n)是对具有n个元素的序列进行划分所需的时间，由以上划分算法的过程可以得到T p (n) = Θ(n)。由此，T(n) =Θ(n) + T(n-1) =Θ(n 2 )。
在快速排序过程中，如果总是选择r[low]作为枢轴元素，则在待排序序列本身已经有序或逆向有序时，快速排序的时间复杂度为Ο(n 2 )，
而在有序时插入排序的时间复杂度为Ο(n)。
快速排序的最好情况是在每次划分时，都将序列一分为二，正好在序列中间将序列分成长度相等的两个子序列。
此时，算法的时间复杂度T(n) = T p (n) + 2T(n/2)，由于T p (n) = Θ(n)，所以T(n) = 2T(n/2) +Θ(n)，
由master method知道T(n) = Θ(n log n)。
在平均情况下，快速排序的时间复杂度 T(n) = kn ㏑ n，其中 k 为某个常数，经验证明，在所有同数量级的排序方法中，
快速排序的常数因子 k 是最小的。因此就平均时间而言，快速排序被认为是目前最好的一种内部排序方法。
快速排序的平均性能最好，但是，若待排序序列初始时已按关键字有序或基本有序，则快速排序蜕化为起泡排序，其时间复杂度为Ο(n 2 )。
为改进之，可以采取随机选择枢轴元素pivot的方法，具体做法是，在待划分的序列中随机选择一个元素然后与r[low]交换，再将r[low]作为枢轴元素，
作如此改进之后将极大改进快速排序在序列有序或基本有序时的性能，在待排序元素个数n较大时，其运行过程中出现最坏情况的可能性可以认为不存在。

空间效率：虽然从时间上看快速排序的效率优于前述算法，然而从空间上看，在前面讨论的算法中都只需要一个辅助空间，
而快速排序需要一个堆栈来实现递归。若每次划分都将序列均匀分割为长度相近的两个子序列，则堆栈的最大深度为 log n，
但是，在最坏的情况下，堆栈的最大深度为 n。

快速排序算法的原理及实现

相关推荐