分治算法-快速排序_头歌分治算法快速排序怎么用

快速排序

为了弥补上一篇线性时间选择问题的不足，你们的小周周想来想去，觉得还是讲一下快速排序比较好一点，这样大家就更加容易理解线性时间选择问题了。

快速排序的思想

快速排序也是分治递归思想，其主要是要找一个基准元（一个作为比较的元素，一般选取数组第一个元素作为基准元）出来，将数组里面的元素和他比较，用一个while()循环从左边开始找到比基准元大的元素，然后就退出；接着再用一个while()循环从右边开始找比基准元小的元素，找到就退出。然后将左边找到的元素的下标和右边找到的元素的下标进行比较，如果左边的元素的下标比右边的元素的下标小，则交换两个元素的位置，如果左边的元素的下标比右边的元素的下标大，则退出最外层循环，因为快速排序的思想就是要使左边的子序列都比基准元小，右边的子序列都比基准元大，如果左边的元素的下标比右边的元素的下标大还进行交换两个元素的话就不满足快速排序的思想了。再循环结束之后别忘了更改基准元，因为循环结束后，右边找的最后一个元素比基准元小，交换基准元和右边最后找的最后一个元素之后就能使得新的数组左边都比新的基准元小，右边都比新的基准元大。当序列只剩一个元素时，就不用再递归分解序列了，因为一个元素本身就是排好序的。

代码如下所示（java）

public class quickSort {
	public static void main(String[] args) {
		int []a= {12,38,1,3,89,100,2,7,29,28,43,78,28,11,4};
		System.out.println("快速排序前如下：");
		for(int i=0;i<=a.length-1;i++) {
			System.out.print(a[i]+" ");
		}
		System.out.println();
		sort(a,0,a.length-1);
		System.out.println("快速排序后如下：");
		for(int i=0;i<=a.length-1;i++) {
			System.out.print(a[i]+" ");
		}
	}
	public static void sort(int []a,int l,int r) {
		if(l<r) {
			int mid=partion(a,l,r);
			sort(a,l,mid-1);  //左半部分进行快速排序
			sort(a,mid+1,r);//左半部分进行快速排序
		}
	}
	public static int partion(int []a,int l,int r) {
		int i=l;
		int j=r+1;
		int x=a[l];  //基准元素
		while(true) {
			while(a[++i]<x&&i<r);  //寻找左边比基准元大的元素
			while(a[--j]>x); //寻找右边比基准元小的元素
			if(i>=j) { //i对应左半部分，j对应右半部分
				break;
			}
			swap(a,i,j);  //左边比基准元素大的元素和右边比基准元素小的元素交换位置
		}
		a[l]=a[j]; //更改基准元素 使得基准元素左边的值都比基准元素小，右边的值都比基准元素大
		a[j]=x;
		return j;  //返回基准元素下标
	}
	public static void swap(int []a,int i,int j) {
		int temp;
		temp=a[i];
		a[i]=a[j];
		a[j]=temp;
	}
}
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
44

运行结果如下图所示

测试数组a={12,38,1,3,89,100,2,7,29,28,43,78,28,11,4}

希望小周周这样的讲解能给大家带来方便，如果大家理解了快速排序了，大家可以去看看小周周写的关于线性时间选择问题那篇文章线性时间选择问题，看看你对快速排序掌握了没。如果你还有什么不懂不理解的，记得联系小周周哦，欢迎大家留言~
如果这篇文章对你有一定的帮助，别忘了给小周周一颗小心心呐，小手轻轻送上心，小编努力再更新。
【无名之辈 我是谁 小小的天 也有大大的梦想】