平均时间复杂度： O(NLogN)
最好情况时间复杂度： O(NLogN)
最差情况时间复杂度： O（N^2）
所需要额外空间： O(NLogN)
稳定性：不稳定
快速排序采用了分治策略，其基本思想是：
通过一趟排序，将待排记录分割为独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小。
不断重复这个步骤，直到每个部分都只有一个记录为止。
其核心是一个Partition函数，这个函数可以选取一个关键字（称之为Pivot），然后把它放到一个合适的位置，使在它左边的值都比它小，在它右边的值都比它大。
具体实现（In JAVA）
package com.yenghye.sort;
public class Sort {
public static void QuickSort(int[] arr, int low, int high) {
int pivot;
if (low < high) {
pivot = Partition(arr, low, high);
QuickSort(arr, low, pivot - 1);
QuickSort(arr, pivot + 1, high);
}
}
private static int Partition(int[] arr, int low, int high) {
int pivotkey = arr[low];
while (low < high) {
while (low < high && pivotkey <= arr[high])
high--;
arr[low] = arr[high];
while (low < high && pivotkey >= arr[low])
low++;
arr[high] = arr[low];
}
arr[low] = pivotkey;
return low;
}
}
Partition函数除了可以应用在快速排序算法当中，还可以用来实现对数组中第k大的数字的查找。
比如题目
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
容易想到，如果一个数组当中某个元素的个数超过了数组长度的一半，那么如果对这个数组排序，这个数组正中间位置上的数一定是我们要找的那个数字。
那么接下来的事很简单，我们只要用一个现成的函数：Partitan，如果我们得到的pivot刚刚好在数组的正中间，那么我们就找到了这个数，如果没有得到，根据pivot和正中间的位置关系，缩小范围继续查找就可以了。
实现（In JAVA）
public class Solution {
public int MoreThanHalfNum_Solution(int [] array) {
if(array == null || array.length == 0)
return 0;
int middle = array.length >> 1;
int start = 0;
int end = array.length - 1;
int pivot = Partition(array, start, end);
while(pivot != middle)
{
if(pivot > middle)
{
end = pivot - 1;
pivot = Partition(array, start, end);
}
else
{
start = pivot + 1;
pivot = Partition(array, start, end);
}
}
int result = array[middle];
if(CheckMoreThanHalf(array, result)!=0)
return 0;
return result;
}
private int CheckMoreThanHalf(int[] array, int result)
{
int times = 0;
for(int i = 0; i < array.length; i++)
{
if(result == array[i])
times++;
}
if((times << 1) > array.length)
return 0;
return 1;
}
private int Partition(int[] a, int low, int high)
{
int pivotkey = a[low];
while(low < high)
{
while(low < high && a[high] >= pivotkey)
high--;
a[low] = a[high];
while(low < high && a[low] <= pivotkey)
low++;
a[high] = a[low];
}
a[low] = pivotkey;
return low;
}
}
***除了用Partition，这道题还有另一种解法，其解题核心是：数组中的一个数字出现的次数超过数组长度的一半，就意味着它出现的次数比其他所有的数字出现的次数加起来还多。那么我们只要从前往后遍历整个数组，选中一个数字为备选，并记录它的次数，如果接下来出现的数字和备选相等，那么增加次数，不等则减少次数。当次数为0的时候，则说明遍历到此为止，相等和不等的个数相互抵消了，则应当选择一个新的备选，并将次数设置为1.
这个思路很清晰，代码写出来也很简单，就不写了。
接下来再举个用Partition函数解决问题的例子。
输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。
想到用Partition函数来解决问题很容易，一直找直到pivot为k-1就可以了。这样从下标0到下标k-1的k个数，就是最小的k个数了。
但是解决问题之前要知道，Partition会改变输入数组内的元素顺序，以及，这种方法比较适合n的数量较小的情况。
import java.util.*;
public class Solution {
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
if(input == null || input.length == 0 || input.length < k)
return new ArrayList();
int start = 0;
int end = input.length-1;
int pivot = Partition(input, start, end);
while(pivot != k-1){
if(pivot > k-1){
end = pivot - 1;
pivot = Partition(input, start, end);
}
else {
start = pivot + 1;
pivot = Partition(input, start, end);
}
}
ArrayList<Integer> result = new ArrayList();
for(int i = 0; i < k; i++)
result.add(Integer.valueOf(input[i]));
return result;
}
private int Partition(int[] a, int low, int high)
{
int pivotkey = a[low];
while(low < high) {
while(low < high && a[high] >= pivotkey)
high--;
a[low] = a[high];
while(low < high && a[low] <= pivotkey)
low++;
a[high] = a[low];
}
a[low] = pivotkey;
return low;
}
}
网友评论