快速排序和寻找第k小元素

搞了一晚上寻找第k小元素，终于弄出来了，下面的代码，我测试的是没有问题的。这思想完美体现了快速排序的思想，分治，又有点像二分，每次partition完了如果没找到只在某一半继续寻找，丢弃另一半。注意，i < k - 1的时候下一次的递归不需要变成k - i - 1，毕竟start的下标没变，仍然按照原始数组下标来执行的。

    private int findKth(int k, int[] nums, int start, int end) {
        int i = start, j = end;
        int pivot = nums[start];
        while (i < j) {
            while (i < j && nums[j] >= pivot)
                j--;
            if (i < j)
                nums[i] = nums[j];
            while (i < j && nums[i] <= pivot)
                i++;
            if (i < j)
                nums[j] = nums[i];
        }
        nums[i] = pivot;
        if (i == k - 1)
            return nums[i];
        else if (i > k - 1)
            return findKth(k, nums, start, i - 1);
        else
            return findKth(k, nums, i + 1, end);
    }

下面是快速排序，快速排序有很多种实现，这里就只选取nums[0]当做pivot了，我感觉这样做没什么不好（当然最好是用三数取中之类的方法取pivot），除非nums[0]每次都恰好是最大或最小。注意在进行nums比较的时候我都加上了>=或者<=，结果是没问题的，我感觉这样可以减少一些递归次数。还有，有的人把代码写成: nums[i--] = nums[j];这样，这么做唯一的好处就是，省去了下一次while里的比对，效果是一样的。还有，注意这么写的时候要从尾部往前搞(先j--)，不能从头往后搞。

  private static void quickSort(int[] a, int low, int high) {
        //递归的出口
        if (low > high) {
            return;
        }
        int i = low;
        int j = high;
        int pivot = a[low];
        //完成一趟排序
        while (i < j) {
            //[从右往左]找到第一个小于pivot的数
            while (i < j && a[j] > pivot) {
                j--;
            }
            //从左往右找到第一个大于pivot的数
            while (i < j && a[i] <= pivot) {
                i++;
            }
            //a[i]和a[j]交换
            if (i < j) {
                int temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
        }
        //a[i]和a[low]交换
        int temp = a[i];
        a[i] = a[low];
        a[low] = temp;
        quickSort(a, low, i - 1);
        quickSort(a, i + 1, high);
    }

--

ref:
http://wangleide414.iteye.com/blog/1672424
http://www.jianshu.com/p/2cc8fc1c878