算法可视化系列——排序算法——快速排序

排序算法可视化系列——篇四“快速排序”

 

快速排序

基本思想分析：

        我们前面介绍的算法相比现在要说的快速排序来说在大数组的性能方面较差，

快速排序是采用一种分治策略，稍微说一下什么是分治策略，我们之前使用递归时，

是将问题分解为更小规模的同类问题进行处理，最后将结果综合起来，而分治的思

想是同样将问题拆为更小规模，但是小规模问题的解法可能完全不同，所以将这些

不同的小问题结果组织起来形成原始问题的解，这就是分治策略。我们在进行快速

排序就是使用分治的策略，具体如下：

        我们在无序数组中选取一个元素称为主元，一般简单的选取方法是选择数组的

最后一个元素，但是如果需要精益求精，那么我们就不能这么选取主元，后面再说

选取主元的问题，选取主元后，我们对数组从第一位元素开始进行遍历，直到数组

的倒数第二个元素（因为此时最后一个元素为主元），在遍历过程中我们需要比较

此时位置元素与主元元素的大小，然后进行交换（具体和谁进行交换看下面算法描

述），如果大于主元元素，则不做任何操作，最后遍历结束，我们将主元元素与其

它元素中的一个交换位置，使得交换位置后满足：

 

• 主元元素左边的元素均不大于主元元素
• 主元元素右边的元素均大于主元元素

那么我们知道主元元素其实已经处于自己排好序的正确位置，这样我们就可以称为

进行了一次划分，然后我们再对从起始到主元元素之前的子数组进行递归调用快速

排序，对主元元素后面的子数组同样调用快速排序，这样就可以将数组排好序。

 

 

 算法描述：

   //首先进行递归调用的快速排序(假设对简单整型数组)

   public static void QuickSor(int[] ar , int start , int end){

if(end > start){

int mid = merge(ar,start,end);//调用划分方法，得到主元位置

进行递归调用

QuickSort(ar,start,mid - 1);

QuickSort(ar,mid + 1,end);

}

}

 

//对数组进行划分的方法，返回最后主元的位置

private int merge(int[] ar, int start, int end){

声明一个变量作为主元元素，值为数组中最后一个元素

声明一个变量index = -1记录小于主元元素的位置索引，因为还没有比较所以设为-1

for(进行循环，遍历数组，直到倒数第二个元素){

比较此刻元素与主元元素的大小

如果小于主元元素，则把index自增1然后将位置index元素与此刻元素交换

如果大于，则不进行任何操作

}

最后将主元元素与++index位置的元素进行交换

保证了，在index之前的子数组元素均小于主元，而在之后的均大于主元

return index;

}

 

从上面可以看出我们类似的对数组进行二分，而且事实证明每次如果可以将两个子数组

划分的大小接近相同，此时的时间复杂度最小，所以直到需要分的时间复杂度为O(log(n))，

而每次度需要迭代进行O(n)，所以整个快速排序的时间复杂度为O(n * log(n))，这还是在理

想情况下，即两个子数组接近相等，但是事实证明它平均时间复杂度即为O(n * log(n))，但是

如果遇到比较坑爹的事的话，比如每次分了以后，都有一个子数组为空，那么另外一个就是

n-1，那么时间复杂度就是O(n^2)，其实这与开始如何选取主元有关系。

 

算法的Java基本实现：

 

/**
* 快速排序的Java简单实现
* 基于对整型数组的简单实现
*
*/
public class QuickSort{
	public void quickSort(int[] a,int start,int end){
		if(end > start){
			/**
		* 调用进行划分的方法，返回主元的索引
		*/
		int mid = partition(a,start,end);
		/**
		* 递归调用，进行排序
		*/
		quickSort(a,start,mid - 1);
		quickSort(a,mid + 1,end);
		}
	}
	
	/**
	* 进行划分的方法
	*/
	public static int partition(int[] a,int start,int end){
		int values = a[end];//进行划分的主元
		int i = start - 1;//用于记录小于主元values值的索引
		for(int j = start; j < end; j++){
			if(a[j] < values){
				i = i + 1;
				int temp_data = a[i];
				a[i] = a[j];
				a[j] = temp_data;
			}
		}
		/**
		* 最后移动主元，使得主元元素左边的元素小于等于主元
		* 右边元素大于等于主元
		*/
		for(int k = end - 1; k > i; k--){
			a[k + 1] = a[k];
		}
		a[i + 1] = values;
		return i + 1;
	}
	
}

 

 

下面是关于快速排序的动态演示：

一、排序中。。。。。。

 

 二、排序中。。。。。。

 三、排好序。

 上面就是对于快速排序的动态演示，下面附录的了这一部分的源代码：