首页 > 基础算法 > 排序 > 快速排序的随机化和非递归实现
2014
05-18

快速排序的随机化和非递归实现

前面一讲介绍的朴素的快速排序的实现,也对其复杂度进行了分析。如果基准(支点 pivot)元素选取的不当,复杂度最坏为O(n^2)。一般有下面的几个优化方法:

1)以上实现使用最后一个元素作为支点。如果输入是已排序的数组,这是一种最坏的情况。解决这种情况,主要在于怎么选取支点。可以随机的选取一个元素作为支点进行划分,或者直接选择最中间的元素,或者选择 第一个元素first、中间元素middle和最后一个元素last 的 中位数。比较常用的是随机化方法。

2)为了减少递归深度,首先对数组更小的一半进行递归,并使用尾调用递归另一半。

3)在数组长度较小时使用插入排序是个不错的选择。例如这个库 的实现是当数组长度小于7时用插入排序。

随机化的实现也比较简单,划分的操作可以继续以最后一个元素为支点,只是先随机的选取一个元素,然后和最后一个元素交换。另外可以把递归的调用,可以改成非递归的,以减少开销。这里直接用数据模拟栈来实现。

完整代码如下:

//============================================================================
// Name        : QuikSort-Iterative.cpp
// Author      : GaoTong
// Version     :
// Copyright   : www.acmerblog.com
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;

//打印数组
void printArr(int arr[], int n){
	for(int i=0; i<n; i++)
		printf("%d ",arr[i]);
	puts("");
}
//普通划分操作。以最后一个元素 arr[e]作为基准
int partition(int arr[], int s, int e){
	int i = s-1;
	for(int j = s; j<e; j++){
		if(arr[j] <= arr[e]){
			i++;
			swap(arr[i], arr[j]);
		}
	}
	swap(arr[e], arr[i+1]);
	return i+1;
}

//随机化的划分操作。已最后一个元素 arr[e]作为基准
int partitionRandom(int arr[], int s, int e){
	//取得一个随机的下标
	int randomIndex = rand() % (e-s+1) + s;
	swap(arr[e], arr[randomIndex]);
	int i = s-1;
	for(int j = s; j<e; j++){
		if(arr[j] <= arr[e]){
			i++;
			swap(arr[i], arr[j]);
		}
	}
	swap(arr[e], arr[i+1]);
	return i+1;
}

/* 递归的实现。A[] -->要排序的数组, s  --> 开始位置, e  --> 结束位置 */
void quickSort(int arr[], int s, int e)
{
    if (s < e)
    {
        int p = partition(arr, s, e); /* Partitioning index */
        quickSort(arr, s, p - 1);
        quickSort(arr, p + 1, e);
    }
}

//划分操作的 第二种实现
int partition2(int * arr, int start, int end) {
	int i = start;//指向开头
	int j = end + 1;//指向结尾
	int pivot = arr[start];
	while(true){
		while( i<end && arr[++i] < pivot);//从前到后  第一个比 基准(x)大的数。 j指向该数
		while(j>start && arr[--j] > pivot);//从后向前找到第一个比 基准(x)小的数。i指向该数
		if(i >= j)
			break;
		swap(arr[i], arr[j]);
	}
	arr[start] = arr[j];
	arr[j] = pivot;
	return j;
}

//快速排序的非递归实现
void quicksortIterative(int arr[],int s, int e){
	int stack[e-s+1];//用数组模拟栈
	stack[0] = s;
	stack[1] = e;
	int len = 2; //栈的大小
	while(len > 0){
		//取得时候是反着的
		int end = stack[--len];
		int start = stack[--len];
		int mid = partitionRandom(arr, start, end);
		//只有元素个数大于1的时候,才放入栈中
		if(mid-1 > start){
			stack[len++] = start;
			stack[len++] = mid-1;
		}
		if(end > mid+1){
			stack[len++] = mid+1;
			stack[len++] = end;
		}
	}
}

//测试
int main() {
	int arr[] = {2,5,2,1,8,3,6,4,9,7};
	int n = sizeof(arr) / sizeof(arr[0]);
	quicksortIterative(arr, 0 ,n-1);
	printArr(arr,n);
	return 0;
}

参考:http://www.geeksforgeeks.org/iterative-quick-sort/


  1. 如果两个序列的最后字符不匹配(即X [M-1]!= Y [N-1])
    L(X [0 .. M-1],Y [0 .. N-1])= MAX(L(X [0 .. M-2],Y [0 .. N-1]),L(X [0 .. M-1],Y [0 .. N-1])
    这里写错了吧。