排序7-快速排序
快速排序的核心思想也是分治法。它的实现方式是每次从序列中选出一个基准值,其他数依次和基准值做比较,比基准值大的放右边,比基准值小的放左边,然后再对左边和右边的两组数分别选出一个基准值,进行同样的比较移动,重复步骤,直到最后都变成单个元素,整个数组就成了有序的序列.
1. 动图演示:
排序过程分解图: 以[8,2,5,0,7,4,6,1]为例
首先,我们随机选择一个基准值4:
与其他元素依次比较,大的放右边,小的放左边:
再以同样的方式排左边的数据
继续排序左边的子序列0和1:
由于只剩下一个数,所以就不用排了,现在的数组序列是下图这个样子,4左边的序列已经排序成功:
4右边的子序列以同样的操作进行,即可排序完成.
2. java实现: 快速排序的关键之处在于切分,切分的同时要进行比较和移动,
1) 单边扫描
首先我们来看一种叫做单边扫描的做法。
我们随意抽取一个数作为基准值,同时设定一个标记mark代表左边序列最右侧的下标位置,当然初始为0,接下来遍历数组,如果元素大于基准值,无操作,继续遍历,如果元素小于基准值,则把mark+1,再将mark所在位置的元素和遍历到的元素交换位置,mark这个位置存储的是比基准值小的数据,当遍历结束后,将基准值与mark所在元素交换位置即可。
public static void sort(int[] arr) {
sort(arr, 0, arr.length - 1);
}
private static void sort(int[] arr, int startIndex, int endIndex) {
if (endIndex <= startIndex) {
return;
}
//切分
int pivotIndex = partitionV2(arr, startIndex, endIndex);
sort(arr, startIndex, pivotIndex-1);
sort(arr, pivotIndex+1, endIndex);
}
private static int partition(int[] arr, int startIndex, int endIndex) {
int pivot = arr[startIndex];//取基准值
int mark = startIndex;//Mark初始化为起始下标
for(int i=startIndex+1; i<=endIndex; i++){
if(arr[i]<pivot){
//小于基准值 则mark+1,并交换位置。
mark ++;
int p = arr[mark];
arr[mark] = arr[i];
arr[i] = p;
}
}
//基准值与mark对应元素调换位置
arr[startIndex] = arr[mark];
arr[mark] = pivot;
return mark;
}
2) 双边扫描
随意抽取一个数作为基准值,然后从数组左右两边进行扫描,先从左往右找到一个大于基准值的元素,将下标指针记录下来,然后转到从右往左扫描,找到一个小于基准值的元素,交换这两个元素的位置,重复步骤,直到左右两个指针相遇,再将基准值与左侧最右边的元素交换.
public static void sort(int[] arr) {
sort(arr, 0, arr.length - 1);
}
private static void sort(int[] arr, int startIndex, int endIndex) {
if (endIndex <= startIndex) {
return;
}
//切分
int pivotIndex = partition(arr, startIndex, endIndex);
sort(arr, startIndex, pivotIndex-1);
sort(arr, pivotIndex+1, endIndex);
}
//只有这个方法是不同的.
private static int partition(int[] arr, int startIndex, int endIndex) {
int left = startIndex;
int right = endIndex;
int pivot = arr[startIndex];//取第一个元素为基准值
while (true) {
//从左往右扫描
while (arr[left] <= pivot) {
left++;
if (left == right) {
break;
}
}
//从右往左扫描
while (pivot < arr[right]) {
right--;
if (left == right) {
break;
}
}
//左右指针相遇
if (left >= right) {
break;
}
//交换左右数据
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}
//将基准值插入序列
int temp = arr[startIndex];
arr[startIndex] = arr[right];
arr[right] = temp;
return right;
}
3. 分析:
快速排序的时间复杂度和归并排序一样,O(n log n),但这是建立在每次切分都能把数组一刀切两半差不多大的前提下,如果出现极端情况,比如排一个有序的序列,如[9,8,7,6,5,4,3,2,1],选取基准值9,那么需要切分n-1次才能完成整个快速排序的过程,这种情况下,时间复杂度就退化成了O(n^2).
所以说,快速排序的时间复杂度是O(nlogn),极端情况下会退化成O(n^2),为了避免极端情况的发生,选取基准值应该做到随机选取,或者是打乱一下数组再选取。