（7）排序算法——交换排序之快速排序

发表于   |   分类于   |   阅读次数

1、基本思想：

快速排序也是一种交换排序，它是通过一次排序将数组分割成两部分，其中的一部分都比另一部分的所有数据都要小

2、算法描述：

假设有数组arr[n]，升序排列。

  1. 快速排序首先要有一个基准值，一般选择使用数组第一个元素。
  2. 首先数组从右往（j=n-1）左查找比基准值小的元素a，找到后，再从左往（i=0）右查找比基准值大的元素b，找到后交换a、b。直到i=j。
  3. 前两步执行完成，数组就变成了，基准值左边的数都比基准值小，基准值右边的数都比基准值大。也就是说本次所使用的基准值已经在正确的位置上。这一过程被称为一趟排序。
  4. 将基准值左边的元素作为一个数组，右边的元素作为一个数组，分别递归执行前三步。直到没有数组可以执行。
  5. 排序算法每一趟排序的目的都是将基准值放到正确的位置。所有的基准值都放在了正确的位置，排序也就完成了。





完整排序步骤如下图，快速排序就是不断将基准值放到正确的位置，并按照基准值所在位置将数组拆分，对子数组分别进行快速排序。

将每个拆分出来的子数组的基准值放在正确的位置，快速排序就完成了。

3、Java实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
 * 快速排序
 * @author lizhen
 */
public class QuickSort {
	/**
	 * 升序排列
	 * @param arr 需要排序的数组
	 * @param left 需要进行排序的元素的起点
	 * @param right 需要进行排序的元素的终点
	 */
	public void quickSort(int[] arr, int left, int right) {
		//使用递归必须要有结束条件
		if(left>=right){
			return;
		}
		int i = left;
		int j = right;
		//设置基准值
		int temp = arr[left];
		while(i<j){
			//寻找满足条件的i和j   
			//首先从右往左查找 ,这里只要arr[j]>=temp,就去判断下一个元素，直到找到那个不再大于等于基准值temp的元素。
			while(arr[j]>=temp && i<j)
				j--;
			//同样的，从左到右，找到大于基准值的元素。
			while(arr[i]<=temp && i<j)
				i++;
			//得到最终的i和j，i与j对应的元素交换
			if(i<j){
				int t = arr[i];
				arr[i] = arr[j];
				arr[j] = t;
			}
		}
		//一次循环完成，将基准值与i交换。交换完成后当前数组temp前边的都小于temp，后边的都大于temp
		arr[left] = arr[i];
		arr[i] = temp;
		//递归调用，直到起止位置之间不再有元素。
		quickSort(arr,left,i-1);
		quickSort(arr,i+1,right);
	}
}

4、效率分析：