标签：排序

深入理解java快速排序的正确性

    说起快速排序，很多人都能够写出一个正确的快速排序，但就快速排序的正确性，就无从探究了。为什么说写出来的快速排序就是正确的。在快速排序中间的关键几步，以什么样的数据组织来保障快速排序的正确性。本文以《数据结构与算法 Java语言描述》中所描述的快速排序来进行理解，以查看其中的正确性。

    首先查看排序的整体伪代码：

public static void quicksort(int[] a, int left, int right) {
                //第1步
		if(left + CUTOFF > right) {
			insertsort(a, left, right);
			return;
		}
                //第2步
		int pivot = med(a, left, right);
                //第3步
		int i = left, j = right - 1;
		while(true) {
			while(a[++i] < pivot)
				;
			while(a[--j] > pivot)
				;
                        //第4步
			if(i < j)
				swap(a, i, j);
			else
				break;
		}
                //第5步
		swap(a, i, right - 1);
                //第6步
		quicksort(a, left, i - 1);
		quicksort(a, i + 1, right);
	}

    其中，中间所涉及的med算法如下所示：

private static int med(int[] a, int left, int right) {
		int center = (left + right) / 2;
		if(a[center] < a[left])
			swap(a, left, center);
		if(a[right] < a[left])
			swap(a, left, right);
		if(a[right] < a[center])
			swap(a, center, right);
		swap(a, center, right - 1);
		return a[right - 1];
	}

    以上即整个快速排序算法以及相对应的获取pivot的算法。
    那么我们首先从源码上分析整个排序算法的正确性，以及在特殊的控制点上是如何取得正确的（在后续的说明中 小于的意思为小于或等于 大于的意思为大于或等于，即不对=pivot的数进行特殊处理）。

继续阅读“深入理解java快速排序的正确性”

理解合并排序，java中使用的标准排序方法

    所谓合并排序，就是将两个部分的数组合并在一起，但是有个前提就是两个数组本身就是已经排好序的。它包括两个问题，一个合并，一是排序。
    基本思想就是将一个数组从中间分为两个部分，先对左边排序，再对右边排序，最后将两边再合并出来即可了。采用递归手段，我们可以递归的对左边排序，对右边排序，最后合并。

    由于要将两个子数组合并为一个新的数组，因此需要一个额外的空间来存储这些数据信息。因此，我们需要建立一个与原数组大小相同的数组，用于合并过程。合并完了之后，再将额外空间中的数据copy回原来的空间，即完成整个排序工作。

    现在来看程序逻辑，程序逻辑已按照先分面两个部分，再分别递归排序，然后再合并的思路，具体代码如下：

	/** 归并排序，ints为要排序的数组 */
	public static void guibingSort(int[] ints) {
		int[] temp = new int[ints.length];
		guibingSort(ints, temp, 0, ints.length - 1);
	}

	/** 归并排序,ints为要进行排序的数组，temp为临时数组,start为排序起点,end为排序终点,排序范围为[start,end] */
	private static void guibingSort(int[] ints, int[] temp, int start, int end) {
		if(start >= end)
			return;
		int middle = (start + end) / 2;//中间点
		int left = start;//左边起点
		int right = middle + 1;//右边起点
		guibingSort(ints, temp, left, middle);//左边排序
		guibingSort(ints, temp, right, end);//右边排序
		//将两边的数组进行合并
		int i;
		for(i = start;  left <=  middle && right <= end;) {
			if(ints[left] > ints[right])
				temp[i++] = ints[right++];
			else
				temp[i++] = ints[left++];
		}
		//将左边没有合并完的添加到temp中
		while(left <= middle)
			temp[i++] = ints[left++];
		//将右边没有合并完的添加到temp中
		while(right <= end)
			temp[i++] = ints[right++];
		//最后将这些数字转回到ints
		System.arraycopy(temp, start, ints, start, end - start + 1);
	}

    代码的主要部分在于合并，合并的思路即对两个数组从开头分别比较，将比较小的那个加入到额外数组中去，这个过程一直持续到其中有一个数组完成，最后将剩下数组的剩余部分全部copy至额外数组即可（因为，两个数组是排好序的，在copy过程中可以保证排序的正确性）。

    合并排序与快速排序的最大一个区别在于，合并排序需要使用额外的空间，而且数据在排序过程中需要进行不断的进行数据之间的复制，并且用于比较的次数较小；而快速排序则需要对数据进行不断的移动，而不需要进行数据复制，却需要进行大量的比较操作。因为在java中，所有的数据都是按引用进行排序，数据移动和复制都是走引用，因此，花费较小，并且进行对象间的比较花费较大，因此在进行对象比较时，都是使用的合并排序算法。而其它语言，如c++，则是使用快速排序来进行排序，他们依赖的即是对象的大小比较。

理解快速排序，最常用的排序

    快速排序，用c++语法中用得最多的排序算法。一般情况下，它的算法时间为NlogN，相比插入排序，希尔排序来说，它在处理大数据量上具有相当的优势。
    快速排序使用了递归的思想，即将其中的一部分再交由算法本身进行处理。它的基本原理如下：

  1. 当数组长度只有1时，即结束排序
  2. 当数组长度大于1时，随机的取一个数（记为中数）对数组进行分割，即将整个数组分为三个部分，一是所有小于等于中数的数据，二是中数本身，三为所有大于等于中数的数据。在三部分数据中，允许数据长度为0,即有可能所有的数据都比中数小或大。

    所以，快速排序的基本实现步骤，即首先判断结束条件，在满足条件1时，直接结束；接下来，取中数，即取一个适合当作中间数的元素；再接着就是分割数组了，将所有小于中数的数据，放到数组左边，将所有大于中数的数据放到数组右边；最后再对所有左边的数据进行递归排序，对所有右边的数据进行递归排序。
    因此，算法的重点在于如何进行数组分割，即要满足一个数据比较关系，即数组[left]<=中数<数组[right]。同时，又要保证不要进行无谓的替换，即在处理过程中中不对所有左边（或右边）的数据进行交换。因此，采取一个算法，即是只需要将左边>=中数的数据和右边<=中数的数据进行交换即可，当左边或者右边已没有数据可交换时，即结束分割。
    具体的做法，即是采取从两边向中间靠的方式，即使用left和right变量分别从两边向中间靠，当left碰到比中数大的数时停止，right碰到比中数小的数时停止，然后交换left和right的数据，然后再继续，走到left>right，即表示整个数组实际上已经完成了遍历，而且left变量左边的数据均比中数小，而右边的数则均比中数大，当然left所处的位置也比中数大。最后将left与路数交换，left所在的位置，即是中数所在的位置。接下来，重复对start-left排序，left+1至end排序，即完成递归排序。

继续阅读“理解快速排序，最常用的排序”

理解希尔排序，缩减增量排序

    话说使用冒泡排序，选择排序和插入排序，都是平均使用了On2的时间，因为它们都是只能一次移动一个位置。如果对于这种情况，即最小的数在最后一位，那么就需要根据具体地算法将数据从最后慢慢地往前移了。对于冒泡排序，时间不会减少；对于选择排序时间也不会减少，因为每次都将第二大的数又再一次放到最后一位了；对于插入排序，会稍微地提高一次效率，因为只能最后一次才需要移动数组。

    那有没有可以一次性移动多个位置的算法呢，那就是希尔排序，它是对于插入排序的地种改进。即使得要进行排序的数，在进行位置移动的时候，可以一次性地移动 多个位置，再不用一位一位地移动了。因为需要一次性移动多个位置，那就需要有一个移动的位置数，即gap。同时，它有一个要求，是必须要满足的，就是对于 数组中的每个数i，在进行移动之后，必须满足Array[i]<=Array[i+gap]。即前面的数必须要比后面的数小（按从小到大排序的 话）。因为每次移动是超过一个位置的移动，因为在移动之后，不能保证前一个数必须比后一个数小，因为还需要进行第二次移动，同时最后必须要有一个 gap=1情况，即最后有一个类似插入排序的动作。只不过到最后进行插入排序时，因为前面的移动已使得数组已相对排序，所以最后一次插入排序速度很快。

    因为有gap的存在，希尔排序实际上就是一个先将数组按照gap大小进行分组，然后对每一个分组进行插入排序的过程。对分组进行插入排序，以保证每个分组都是已经排好序的。这样一直到gap=1时，实际上就是一个将一个大组进行插入排序了。
    这几个主要有两个需要注意的，一就是分组的概念，即gap的概念，使用gap将数组按照一定的间隔进行排序；二就是插入排序的概念，在每个分组中是使用插入排序进行排序的。主要弄清楚这两个部分，那么在理解希尔排序的程序算法时，就能很好地理解了。

    使用gap一般是按照从大到小的顺序，同时也有一个如何使用gap的问题。不同的gap会使得最终的排序效率会不一样，因为这影响实际的分组，以及在多次分组之后，是否存在重复排序的问题。具体的选择这里就直接省略了，直接使用wikipedia中的一个gap数组进行处理。

private static void shellSort(int[] ints) {
		int[] gaps = {1, 5, 13, 43, 113};
		//首先确定gap大小
		int i = 0;
		while(gaps[i] < ints.length)
			i++;
		//进行分组再排序了
		while(i >= 0) {
			//使用当前对应的gap进行分组排序
			int gap = gaps[i];
			//以下就是一个插入排序的过程，以gap为排序间隔进行插入排序
			for(int j = gap;j < ints.length;j++) {
				//初始即从当前排序数开始进行
				int k = j;
				int temp = ints[k];
				//使用temp和k-gap之间进行比较,这里k-gap>=0因此k >= gap
				while(k >= gap && temp < ints[k - gap]) {
					ints[k] = ints[k - gap];
					k -= gap;
				}
				ints[k] = temp;
			}
			//gap往下减1,即使用下一个比较小的gap
			i--;
		}
	}

    希尔排序的效率很高，一般情况下为On3/2，但好的gap数组可以达到On5/4，以致On7/6，这样的效率足够和快速排序相比了。并且，这个理解起来简单。只需要记住以下几点即可：
    插入排序在数组已经接近排好序的情况下，效率很高，可以达到On
    使用希尔选择gap可以将数组从快速的方式组织成接近排好序的情况，使用增量式移位比单个移位更快
    希尔排序的内部始终是插入排序，并且最后一次肯定是一个最原始的插入排序