排序算法(1)之快速排序——java实现

题外话：

一般情况下，快速排序被认为是最快的排序算法（人如其名啊），因此可以说是最常用的排序算法，并受大多数公司的青睐，是一定要熟练掌握的。

 

简介：

快速排序是不稳定的，而且是中比较个性的排序

 算法——初始顺序越乱，排序效果越好，一般情况下，我们认为其时间复杂度为O（NlogN），当排序队列已经是顺序队列，时间复杂度达到最差O（n*n），具体是实现是用分治算法，因此涉及到栈，再因此，其空间复杂度略大，达到同样的O(NlogN)，在这个效率为先的环境下，以牺牲些许空间换取更短的时间还是非常值得的。

 

算法思想：

快排采取了分治策略，也是分治算法的一个经典习题，因此其算法思想也符合分治算法，具体的思想是：

1.从数列中找到一个数

2.确定该数在队列中的位置，比它小的都放在左边，大的都在右边

3.将左右两部分分而治之。

 

伪代码如下：

void quickSort(int[] a, int begin, int end) {

	/*
	* 找到所选数字的位置，并记录下来该位置index
	*/
	
	quickSort(a, begin, i - 1);//对左边子问题进行排序
	quickSort(a, i + 1, end);//对右边子问题进行排序
	}

 

下一步，好了，算法框架已经搭好，剩下的问题就是，怎么找到所选数字的位置。

结合实例来详细介绍一下：

     ↓(i)                                                                                                                                                  ↓(j)

0	1	2	3	4	5	6	7	8	9	10	11
5	7	8	2	6	125	41	341	34	63	28	97

首先我们需要找到97在数列中的位置：

首先设左右两个指针，i 向左走，j 向右走，a[ i ] 遇到比97大的，就换到a[ j ]的位置，j-- （换 j 向左走）

                                                                        ↓i（换到 j 处）                                              ↓ j   ←    ↓ j

0	1	2	3	4	5	6	7	8	9	10	11
5	7	8	2	6	125	41	341	34	63	28	97

 

得：                                                                    ↓ i                                                                ↓ j

0	1	2	3	4	5	6	7	8	9	10	11
5	7	8	2	6		41	341	34	63	28	125

同理，a[j] 遇到比97小的，就换到a[ i ]的位置，i++

                                                                          ↓ i   →  ↓ i                                                       ↓ j

0	1	2	3	4	5	6	7	8	9	10	11
5	7	8	2	6	28	41	341	34	63		125

 

i、j分别向左走向右走，迟早会遇到。

当两个指针相遇，即i == j时，这样就能完成了比97小的，都被换到了左边，大的都被换到了右边。想不通的面壁去。因此 相遇的位置即97的位置。

 

PS：我们看到每当做一次交换，则换另一个指针走。

 

这样每趟只需要做n次对比、操作，分治之后的树的高度是logN，因此时间复杂度为O(NlogN)

 好了，下面用代码实现：

	int i = begin;//记录两个指针的初始位置
	int j = end;
	int tem = a[end];//选择基数，可以随便选，一般选择端点，简单，安全
	boolean tag = true;//标记该哪个指针走，true表示 i 指针走
	while (i != j) {//如果两个指针没相遇，则一直循环下去
		if (tag) {//左边指针走
			if (a[i] < tem) {//如果不满足交换条件，就继续走
				i++;
				continue;
			} else {//满足交换条件，将大数换到右边
				a[j] = a[i];
				j--;//该句可以略去，若略去，a[j]要多对比一次
				tag = !tag;//换右指针向左走
			}
		} else {
			if (a[j] > tem) {//同上
				j--;
				continue;
			} else {
				a[i] = a[j];
				i++;//可略去
				tag = !tag;
			}
		}
	}
	a[i] = tem;//最右当i 、j相遇时，把当时所选的数放进去即可

  

上述代码相对比较傻瓜，是完全按照上面一步一步来的，代码可以进一步压缩：

 

while(i < j){

   while(i < j && a[j] > tem){ j--;}
   swap(a[i],a[j]);//交换两个数
   while(i < j && a[j] < tem){i++;}
   swap(a[i],a[j]);
}
a[i] = tem;

 当然，分治法用到了递归，是肯定要设置一个出口的，

if(end <= begin){
   return;
}

 以上即可。

 

 

附录：

下面把完整外码贴出来

 

public class QuickSort {

	static void quickSort(int[] a, int begin, int end) {

		/*
		 * 找到某个数字的制定位置，并记录下来
		 */
		if(end <= begin){
			return;
		}
		int i = begin;
		int j = end;
		int tem = a[end];
		boolean tag = true;
		while (i != j) {
			if (tag) {
				if (a[i] < tem) {
					i++;
					continue;
				} else {
					a[j] = a[i];
					tag = !tag;
				}
			} else {
				if (a[j] > tem) {
					j--;
					continue;
				} else {
					a[i] = a[j];
					tag = !tag;
				}
			}
		}
		a[i] = tem;
		quickSort(a, begin, i - 1);
		quickSort(a, i + 1, end);
	}

	public static void main(String[] args) {
		int[] a = { 5, 7, 8, 2, 6, 125, 41, 341, 34, 63, 28, 97 };
		quickSort(a, 0, a.length - 1);
	}

}