排序算法（二）

接下来，我准备说一下快速排序，归并排序和堆排序。
在讲快速排序和归并排序前，首先说一下分而治之的思想，就是说，先将要处理的问题简化，即将复杂的大问题分解为简单的小问题，然后分而治之。一般步骤如下：1）将问题分解为小的子问题。每个子问题与大问题同型，但规模更小。2）递归解决这些子问题。3）将子问题的解答合并获得大问题的解答。在这个策略下，实际编程时也是将工作分为这三步。大家要理解的是这种思想，例如，在问题分解时，我们不一定就每一步都分解成两个子问题，可能是三个子问题或者更多个子问题。其次，讲一下基于比较算法的时间复杂度下限。n个数有n！种排列顺序，一棵比较2叉树有对应的n！个叶节点，要排好序，需要log(n!)个步骤（我们这里都认为对数的底是2，其实转换成其他底，转换时只是一个常数因子的差别）。因为不等式log(n!)>=c.nlogn是成立的（c为某个常数，c>0），所以基于比较的排序方法的时间复杂度下限是O(nlogn)。
1.快速排序
选择一个数v，对一个数组进行划分，把小于v的数放到左边，把大于v的数放到右边，之后再递归的处理左边部分和右边部分，最后形成的是一个有序的序列。这可以看成一个二分。问题的分析可以描述为递归关系
T(n)=2T(n/2)+O(n);
这个T(n)可以推导出为大约为nlogn。所以说，快速排序的时间复杂度为O(nlogn)。
每次划分的方法,这里每次选择数组末尾元素v作为划分的元素，从数组的左边开始扫描，找到比v大的元素位置i停止，从数组开始扫描，找到比v小的元素位置j停止，若i>=j，就是说两个交叉了，那么这次划分结束，否则，交换i和j位置的值：

public static int partion(int [] arr,int start,int end){
	int i=start-1,j=end,v=arr[end];
	
	while(true){
		while(less(arr[i++],v));
		while(less(v,arr[j--])) if(j==l) break;//这里要注意，若到了数组左边，则停止扫描
		if(i>=j) break;
		exch(arr,i,j);
}
exch(arr,i,end);
return i;
}

有了划分的程序，那么快速排序根据上面我们的提的思路，很容易就写出来了。

public static void quicksort(int [] arr,int start,int end){
	if(start>=end) return;
int i=partion(arr,start,end);
	quicksort(start,i-1);//递归排序左边部分
	quicksort(i+1,end);//递归排序右边部分
}

深入讨论一下快速排序：1）划分元素的选择，我们当然希望每次选择的元素都能把数组划分为相等的两半。如果数据在随机的时候，我们随便选择一个元素作为划分元素，可以达到这样的效果。但是在最坏的情况下，数据不是随机，而是已经接近排好序的时候，第i次元素扫描可能接近n-i比较，因此，这个时候快速排序的时间复杂度是O(n^2);怎么改善这种情况呢，其实思想很简单，我们可以采用随机化选择划分元素，例如使用Math.random()方法来随机选择一个元素，但是大家要知道，产生随机数是需要消耗一些时间的，那么可以采用一个技巧，我们每次选择数组的头元素，中间元素，末尾元素，采用三个数中中间大的值进行划分（这种划分称作三者取中法），这样做可以显著提高快速排序的效率。2）如果数组中相等元素比较多时，如果要提高效率，可以采用三路划分的方法，也就是说，在进行划分时，把数组分为小于v的部分，等于v的部分和大于v的部分。3）因为递归操作在处理小数据量时，效率反而并不高，因此这个时候，我们划分的子问题量比较小时（一般情况下，我们选择这个数据量为15），这个时候我们可以采用插入排序来进行处理，这样可以显著的提高效率。4）快速排序的副产品，例如，我们选择一个数组中第k大的数，可以这样做，每次划分返回的位置为i，若i=k，则位置i的元素就是第k大的元素，若i<k，我们可以在右边元素里进行继续进行划分，若i>k，则我们可以在左边部分继续进行划分炒作，这样，可以在线性时间内找到第k大的数。其实，在这种情况也还要继续分析，若总的数据量比较小，k比较小，我们可以采用选择排序，nk时间内就可以找到第k大的元素了。
2. 归并排序
我们看到快速排序，每次划分的结果是把一个元素放到了具体位置，也就是说，最后排好序，这个元素的位置也就是时它划分时返回的位置。归并排序的意思，就是我们先排好左边的元素的和右边的元素，也就是说，左边的元素和右边的元素都是有序的，但是需要让总的元素都有序，这个时候采用一个归并操作就可以。
归并的代码如下：

/**
**例如数组形式如：[23,38,40,15,36,77]
** arr 要排序的数组
** start 数组的开始部分
** m 把数组分成左边有序和右边也是有序的位置
** end 数组的结束位置
**/
public void merge(int [] arr,int start,int m,int end){
	int i,j;
	/**
我们先要形成一个双调序列也就是23，38，40，77，36，15，这样就是一个双调序列前面,前面的序列23，38，40是升序的，后面的77,36,15是降序的，最后从第一个序列的左边开始首元素开始，从第二个序列的右边末元素开始，依次输出最小的元素，从而形成一个总体有序的序列15，23，36，38，40，77，放到一个辅助数组aux里，其大小和原数组大小相等。
**/
	//start-m的数是原来左边有序数，例如23，38，40，77，直接复制到辅助数组里就//可以了，下面这样写有一个技巧，i--到最后正好等于start的值，也就是说第一个
//有序序列的最左端
	for(i=m+1;i>start;i--) aux[i-1]=arr[i-1];
	//把m+1-end的原来右边有序的数15，36，77反序为77，36，15，同样这么写是
//为了把j定位到右边元素的最右端
	for(j=m;j<end;j++) aux[end+m-j]=arr[j+1];
	
	//具体的归并操作如下
	for(int k=start;k<=end;k++){
		if(less(aux[i],aux[j])){
	arr[k]=aux[i++];
}else{
				arr[k]=aux[j--];
}
}
}

有了归并操作后，我们一个递归操作就可以进行归并排序了。

public static void mergeSort(int [] arr,int start,int end){
	if(start>=end) return;
	int mid=(start+end)/2;
	mergeSort(arr,start,mid);
	mergeSort(arr,mid+1,end);
	merge(arr,start,mid,end);
}

和快速排序分析一样，时间复杂度分析为O(nlogn)。
对归并排序的深入分析：1）归并排序若归并操作时稳定的（所谓的稳定性是，比如有两个数，他们以前是由某种排序存在，现在重新进行排序，并不会改变原来排序时他们形成的顺序，比如，我们对一个人，先进行姓名排序，最后再进行年龄排序时），那么整个归并排序的结果就是稳定，也就是说，如果对稳定性有要求，归并排序是最佳选择。2）归并排序需要额外的空间O(n)，我们使用了一个辅助数组。因此对空间要求比较高时，并不会采用归并排序。3）归并排序与要排序的数据形态无关，不管怎样的情况下，都可以保证归并排序在O(nlogn)时间内完成，不像我们使用快速排序时，最坏情况下会退化到O(n^2)。因此，我们需要时间保证的时候的，我们一般会采用归并排序。其实后面讲的堆排序也可以做到的。
再补充一句，在java的类库实现中，对基本数据类型的排序采用的快速排序，对对象的排序采用的归并排序的方式实现的。实际排序过程中，无过多的要求时，我们一般都采用快速排序，因为在实际运行过中，基本来说，快速排序都比归并排序快，要不然，怎么叫“快速”排序呢？快速排序也是20世纪最伟大的十大算法其中之一。
3. 堆排序
这里要介绍一下堆排序的概念：对于一棵树而言，对任意一个节点而言，若它存在子节点。则此节点值都大于或等于它的任意一个子节点的值。其实这是一个最大堆的定义。当然了，也存在最小堆，我想，大家这点转换能力应该有的吧。具体堆的表示，一般都采用一棵完全二叉树表示，具体的底层数据结构就采用一个数组，若父节点的位置为i，若存在子节点的话，其左右节点的位置分别为2i，2i+1。反之知道子节点的位置i，其父节点的位置为i/2。
堆的所有操作基本都依赖于两个最基本的操作，向上堆化siftUp和向下堆化siftDown。向上堆化的意思是，若我们的子节点不满足堆的性质，就是说它比父节点大，我们应该把它上移动适合的位置；向下堆化的意思是，我们一个父节点比大于它的子节点时，我们应该把它下移到适合的位置。

/**
向上堆化
**/
public static void siftUp(int k){
	while(k>1&&less(arr[k/2],arr[k])){
	exch(arr,k/2,k);
	k/=2;
}
}
/**
	向下堆化
	k 要向下堆化的元素
    N 数组的大小，为什么我们这里需要这个参数，这是为了排序时方便
**/
public static void siftDown(int k,int N){
	//2*k得到左节点,判断左子节点是否存在
	while(2*k<=N){
	 int j=2*k;
	//如果存在右子节点，找出左右节点中的最大者
	if(j<N&&less(arr[j],arr[j+1])) j++;
			
			//满足堆的性质时，退出
			if(!less(arr[k],arr[j]) break;

			exch(arr,k,j);
			k=j;
}	
}

有了上面的两个基本操作后，我们可以方便的实现堆上的几个操作：
*insert，将新增元素添加到堆的末尾，再将其siftUp，其复杂度为O(logn);
*decreaseKey，将某个元素的值减小，我们只要siftDown，就可以了，其复杂度为O(logn);
*deleteMax，删除最大的值，其实就是删除根元素，我们只要将堆尾的节点arr[N]移到根的位置，将堆的大小减1，再将此节点siftDown，最后返回原根节点。其复杂度为O(logn)。
好的，我们来看看如何根据一个数组构建成堆，其实我们只要知道一点就ok了，只要下面的元素都形成堆，那么依次向下堆化，其实就是检查是否满足堆的性质，最后形成的就是一个堆了。
/**
形成一个堆，下面操作是线性的O(n)，这是一个好消息。(具体证明就不证明了),当然最笨的方法就是一次取原来的数组里一个元素进行插入操作，最后的结果虽然也是一个堆，但是其时间复杂度是O(nlogn).

**/
for(int k=N/2;k>=1;k--){
	siftDown(k,N);
}

堆排序就简单了，我们执行N次deleteMax操作，即得到按键值升序排序的元素，其复杂度为O(nlogn)。
代码如下

while(N>1){
	exch(arr,1,N);
	siftDown(1,--N);
}

深入分析一下堆排序：1）其实堆一般是用于优先队列的实现，堆排序可以看成是堆的副产品。2)堆排序我们也可以保证在最坏情况时间复杂度为O(nlogn)的实现，且它不需要额外的空间，所以如果我们需要时间操作保证，且对空间要求时，我们可以采用堆排序。
小结：介绍的三种排序方法，快速排序，归并排序，堆排序，都是基于比较操作的方式下最优的排序方法，因为基于比较的排序方法，时间复杂度的最优下限是O(nlogn)。实际情况中，海量数据排序时，没有特殊情况时，我们可以随便选择其中一个排序方法，但是一般情况都采用快速排序。具体的有特殊要求时，可以参考我上面的分析。
到这里大家可能存在疑问，有线性时间内实现排序的方法吗？答案是有！我后面会接着介绍。