寻找数组中第K个大小的数的快速排序变种解法

    有一个数组,其大小已知,现在要找出其中第K个大小的数。作为最基本的算法,我们可以先对整个数组进行排序,然后直接找出第K个最小的数即可,但这种解法必须要有一个排序的过程,且排序的结果对于所要求的结果没有直接关系。现在我们通过一个快速排序的变种算法来解决这个问题。
    同样是采取分治法,我们将整个数组一分为二,将小的放到左边,将大的放到右边,并判断K和这两边的子数组长度的大小。如果K的left数组小,则K所在的数必定在left数组之中,否则则在right数组当中。这样就直接去掉接近于一半的数组。然后使用递归再在剩余的left数组中来查找。
    整个过程可以描述成以下过程:

  1. 使用快速排序的pivot分割过程,将数组分割成left数组和right数组以及pivot三个部分
  2. 如果left数组长度大于K,则继续在left数组中查找,否则在right数组中查找

    在上述的描述过程中,有几个特殊点是我们需要考虑的:

  1.     如果K=1,则表示要找的数即整个数组中最小的数,那么直接查找最小的数即可
  2.     如果K=数组长度,则表示要找的数即整个数组中最大的数,那么直接查找最大的数即可
  3.     在数组分割之后,如果K=left数组长度+1,即pivot即是我们所要找的数,直接返回即可

    有了以上的描述,那么整个实现过程就不再复杂了。整个实现过程如下所示

继续阅读“寻找数组中第K个大小的数的快速排序变种解法”

深入理解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快速排序的正确性”

冒泡,选择,插入排序的简单理解和实现

    最近关注了一下c++,又想到很久没有碰的数据结构又快忘完了。又开始从简单的排序开始温习了。作为排序的最经典也是最简单的方法,冒泡,选择,插入这三种排序方法是最让人能够理解的。当然,三种方法的效率也是差不多的,都是O(n2)时间。以下就3种实现,根据自己的理解,简单的描述一番。以下实现均以由小到大的顺序进行实现。

    冒泡排序:

/**
	 * 演示冒泡排序算法
	 * 实质在于通过每次循环的冒泡将最小的放到第一位,因此从整个未排序的数组中,从后将最小的位往前推
	 */
	private static void maopaoSort(int[] ints) {
		for(int i = 0;i < ints.length;i++) {
			for(int j = ints.length - 1;j > i;j--) {//从后面往前开始冒
				if(ints[j] < ints[j - 1])
					swap(ints, j, j - 1);//将小的往前冒,即做一次转换操作
			}
		}
	}

    由上可知,冒泡就是一个将整个数组当中最小的数字,从最后面慢慢地往前冒的过程。假设最小的数在第N位,那么在冒泡的过程中,就是首先通过N冒泡,将N冒到N-1位上,再冒到N-2上(由N-1与N-2比较),最后一直冒到数组的第0位。这样一次子循环下来,最小的数就冒好了。接下来,就开始冒第二小的数了,那么这个数自然就放到i+1即第1位上了。

    选择排序:

/**
	 * 演示选择排序算法
	 * 选择排序的实质在于每次循环从后面的数中选择一个最小的数,放到数组的最前面
	 * 因此每次的比较在于将当前最小的数与当前数相比较,比较之后将小的放到正确的位置上
	 */
	private static void xuanzeSort(int[] ints) {
		for(int i = 0;i < ints.length;i++) {
			int m = i;//假设当前最小的数的下标即为i
			for(int j = i + 1;j < ints.length;j++) {
				if(ints[m] > ints[j]) {//与最小的数比,即与下标为m的数比
					m = j;//重置最小的数的下标
				}
			}
			swap(ints, i, m);//交换两个数,将最小的数放到当前位置上
		}
	}

    由代码可以看出,选择排序和冒泡排序差不多,区别在于在选择排序当中,不再需要两两对比和交换,而是将最小的数与循环中的数进行比较,而且只需要记录最小的数的下标即可。最后将最小的数的下标和当前正在处理的数下标交换即可。如当前正确排到第3位了,前2位自然是已经排好序的了。假设第5位数是最小的,那么最后,就是交换第3位和第5位,然后又从第4位数进行处理了。

    插入排序:

/**
	 * 演示插入排序
	 * <p/>
	 * 实质在于将当前位置上的数插入到前面已经排好序的数组当中,即在进行排序时,当前位置之前的数组实际上是已
	 * 经排好序了的
	 */
	private static void charuSort(int[] ints) {
		for(int i = 1;i < ints.length;i++) {
			int j = i;//记录当前操作的数的下标,即从当前下票开始
			int temp = ints[j];//记录当前要操作的数
			while(j > 0 && temp < ints[j - 1]) {//只有当操作的数小于前面的数时才往前移位置
				ints[j] = ints[j - 1];//将前面的一个数往后移,即将前一个数的值放到后一个下标当中
				j--;
			}
			//找到最终的一个下标,当前数比下标前一个数小,下标后面的数在比较过程中均往后移了一位
			ints[j] = temp;
		}
	}

    插入排序是和前面两个排序最不相同的排序方法了。前面两种方法即是将已经处理且不会再进行二次处理的的数放到一边,再处理剩余的数。而插入是假设前面的数是排好序的,并不关心没有排序的数是否就一定要比排好序的数小。它所做的即是将当前正在处理的数放到前面处理好排好序的数的中间。即原来处理好的数的长度为5,当增加当前处理数之后,长度就变为6了。且数根据一定的规则放到6位长度的数中的其中一个位置上。
    插入核心的地方就是处理将数往前面的数组里面插入的过程,在这里,当然可以使用swap,将当前处理的数和前面比较的数进行调换位置,但考虑到效率上的原因。这里直接将前面比较的数往后放,等到找到一个可以放当前处理数的一标时,再将此数放到正确的位置上即可。

    总结:

    在实现中,前面三个算法在实现的过程当中,肯定有很多的陷阱。如何更好地实现一个排序,并考虑到效率和理解程序上。一个简单的程序也可以写得很长。但简单的算法肯定要考虑到很多种情况,并且要在大多数的场景下都可以很好地工作。重在理解,理解好了,程序就好写了。