标签：数据结构

选择数问题，最坏情况下时间为O(n)的算法实现参考

在前一篇讲选择数问题时，使用了一种类似于快速排序的算法来解决选择数问题，见:http://www.iflym.com/index.php/code/201108240001.html。
而根据算法导论上的一种最坏时间为O(n)的一种解法，其详细的步骤如下所示：

  1.     将数组s按5个为一组，划分成不同的小组,小组数
  2.     对每个小组，进行插入排序，并选择其中的中位数
  3.     将每个小组的中位数，组成一个新的数组，并递归的选择出最终的中位数m
  4.     以m作为参照数，将数组s划分成两个部分，使得m所处的位置数比左侧的数目大1
  5.     如果左侧的数目数恰好为寻找的第k位数，则m即为我们要找的数，否则继续在左侧或者右侧进行查找

有了几个的思路，具体算法就很简单了。参考代码如下所示：

private static int find2(int[] ints, int k, int start, int end) {
//如果k为1,则寻找最小数，如果k为end-start+1则寻找最大数
		//总长度小于5,直接插入排序并查找
......
		//寻找到中位数
		int z = findMiddle(ints, start, end);
		//按中位数分割数组，其中ints[divide]=z
		int divide = divide(ints, z, start, end);
		//判断在哪个部分
		int frontNum = divide - start;
		//恰好为中位数
		if(frontNum == k - 1)
			return ints[divide];
		//高部分
		if(frontNum < k)
			return find2(ints, (k - frontNum), divide + 1, end);
		//低部分
		return find2(ints, k, start, divide - 1);
	}

继续阅读“选择数问题，最坏情况下时间为O(n)的算法实现参考”

解决1分2分5分硬币组合的数学问题

    本文部分信息来源于 http://topic.csdn.net/u/20110913/21/54ef3c9d-6e86-4a4e-8359-cc8f0d728770.html
    问题的提出如下：1分2分5分的硬币，组成1角，共有多少种组合，如果是组成1块，又有多少种组合。

    这个问题看似很简单，答案为10种。但如果要真正去算，或者写程序来实现。想必大多数的人都会使用3层for循环来实现。即分别令i=0（表示1分),j=0(表示2分),k=0(表示5分），然后循环条件为3者之和小于10,得出的结果为三者之和大于10。即实现算术 x+2y+5z=10，然后求x,y,z的组合。
    然而，问题在于提出的问题并没有问具体的组合方式，而是只问了究竟有多少种，那么如果再使用这种算法就有点得不偿失了。

    文中有一个叫tsx86的解法，将此题变成了纯粹的数学题，如下所示：

如果这个和越大，那相应的复杂度会很高。所以
因此，本题目组合总数为10以内的偶数+5以内的奇数+0以内的偶数，

某个偶数m以内的偶数个数（包括0）可以表示为m/2+1=(m+2)/2
某个奇数m以内的奇数个数也可以表示为(m+2)/2

所以，求总的组合次数可以编程为：
number=0;
for (int m=0;m<=10;m+=5){
number+=(m+2)/2;
}

这样程序简单太多了。

    以上文的原理就在于，将x+y*2+5*z=10转换成为10-5z=x+y*2，当z从0到2时，就转换成了求1和2的组合了，实际上就变成了10-5z中，可以有多少个偶数。故产生的结果就如上所示了。

继续阅读“解决1分2分5分硬币组合的数学问题”

理解合并排序，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可以将数组从快速的方式组织成接近排好序的情况，使用增量式移位比单个移位更快
    希尔排序的内部始终是插入排序，并且最后一次肯定是一个最原始的插入排序