寻找数组中第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++语法中用得最多的排序算法。一般情况下,它的算法时间为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排序,即完成递归排序。

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