189 8069 5689

经典排序之快速排序-创新互联

一、概述         快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值， 按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。快速排序的关键点在于如何按照基准值划分区间。快速排序递归实现的框架（本文以升序排序为基础）：   
// 按照升序对a数组中[left, right)区间中的元素进行排序
void QuickSort(int* a, int left, int right) {
	if (left+1>=right) {
		return;
	}
    // 按照基准值对a数组的 [left, right)区间中的元素进行划分
	int div = partion(a, left, right);
    //以div为边界递归左右区间
	QuickSort(a, left, div - 1);
	QuickSort(a, div+1, right);
}

站在用户的角度思考问题，与客户深入沟通，找到河东网站设计与河东网站推广的解决方案，凭借多年的经验，让设计与互联网技术结合，创造个性化、用户体验好的作品，建站类型包括：网站建设、成都网站制作、企业官网、英文网站、手机端网站、网站推广、域名注册、虚拟空间、企业邮箱。业务覆盖河东地区。   二、按基准值划分区间  1.hoare版本

74ee7452d4e74d599ae4c16c4a60ef2a.gif

首先选取一个key值，一般选取最左或最右。当选最左为key值时需要R先移动，当R所在位置的数值小于key值时停下，L移动找到比key值大的位置，然后交换L和R的数值，重复以上操作直到L和R相遇。一趟排序完成后key值被放在了正确的位置即左子序列均小于key值，右子序列均大于key值。这里值得注意的是当key值选取最左端时需要R先移动，选取最右端时需要L先移动。这是因为相遇时的数值与后移动的一方有关，如果key值选左而L先移动那么就会将比key值大的数字交换到最左边，这不符合规则。hoare版本划分区间代码：

int Partion(int* a, int left, int right) {
	int key = left;
	while (left< right) {
		while (left< right && a[right] >= a[key]) {
			right--;
		}
		while (left< right && a[left]<= a[key]) {
			left++;
		}
		swap(&a[left], &a[right]);
	}
	swap(&a[key], &a[left]);

	return left;
}
2.挖坑法

93cd6bb281484f7097675990dab91ea3.gif

挖坑法是hore法的一种变形 ，先将第一个数据存放在临时变量key中，形成一个坑位。R移动找到比key值小的就停下与坑位交换，L再移动找到比key值大的与坑位交换。相遇时将key值填入坑位。挖坑法划分区间代码：

int partion(int* a, int left, int right) {
	int key = a[left];
	int pivot = left;
	while (left< right) {
		while (left< right && a[right] >= key) {
			right--;
		}
		a[pivot] = a[right];
		pivot = right;
		while (left< right && a[left]<= key) {
			left++;
		}
		a[pivot] = a[left];
		pivot = left;
	}
	a[pivot] = key;
	return pivot;
}
3.前后指针法

f67123fc8ea34abca11392728ac954d6.gif

初始时pre指向序列起始位置，cur指向其后。cur移动找到比key值小的时停下，交换cur的值和pre后一位置的值。cur继续移动重复操作直到越界。

int partion(int* a, int left, int right) {
	int pre = left;
	int key = left;
	int cur = pre + 1;
	while (cur<= right) {
		if (a[cur]< a[key] && ++pre != cur) {
			swap(&a[pre], &a[cur]);
		}
		cur++;
	}
	swap(&a[key], &a[pre]);
	return pre;
}
三、快速排序非递归实现

  递归版本中每个创建的栈帧都保存了当前区间的left和right值，我们也可以利用栈这种数据结构存入待处理的区间，每次取出区间后按key值划分区间，并将形成的两个新区间压入栈中，当划分的区间内没有值时停止压栈，重复操作直到栈空。

//写的栈的代码就不列出
void QuickSortNonR(int* a, int left, int right) {
	ST st;//创建栈
	StackInit(&st);//初始化栈
    //将左右区间值压入栈中
	StackPush(&st, right);
	StackPush(&st, left);
	while (!StackEmpty(&st)) {
        //取出栈中存放的左右区间值
		int left=StackTop(&st);
		StackPop(&st);
		int right=StackTop(&st);
		StackPop(&st);
        //划分区间，前面已讲
		int div = partion(a, left, right);
        //区间内有值继续压入栈中
		if (div + 1< right) {
			StackPush(&st, right);
			StackPush(&st, div+1);
		}
		if (left + 1< div) {
			StackPush(&st, div-1);
			StackPush(&st, left);
		}
	}	
	StackDestroy(&st);//销毁栈
}
四、优化 1.三数取中法选key值

  理想情况下快速排序的时间复杂度为O(n*logn),但是如果待排序的序列是有序的，每次划分区间时选择左值为key值，划分后左子区间都是是不存在的，此时时间复杂度变成了O(n^2).

a515ade2462d4f96ba99ebdd3625eea6.png

解决方法：

（1）.随机选择key值，不推荐

（2）.三数取中，选择left、right、left+（right-left)/2,这三个位置的中间大小的数值做key值。

2.递归到小的子区间时，考虑使用插入排序

  与二叉树结构类似，当递归到最后几层时，大量的小区间调用了函数，代价较大。于是就有了小区间优化的概念。当区间的序列个数小于一定数时（这里取十），采用插入排序。

快速排序优化版本完整代码：

int FindMiddle(int* a, int left, int right) {
	int middle = left+(right-left)/2;
	if (a[right] >a[middle]) {
		if (a[middle] >a[left]) {
			return middle;
		}
		else {
			return left;
		}
	}
	else {
		if (a[right] >a[left]) {
			return right;
		}
		else {
			return left;
		}
	}
}
//前后指针法划分区间
int partion(int* a, int left, int right) {
	int mid = FindMiddle(a,left,right);//取中
    swap(&a[left],&a[mid);//交换mid位置的值和left的值
    int pre = left;
    int key=left;
	int cur = pre + 1;
	while (cur<= right) {
		if (a[cur]< a[key] && ++pre != cur) {
			swap(&a[pre], &a[cur]);
		}
		cur++;
	}
	swap(&a[key], &a[pre]);
	return pre;
}

void QuickSort(int* a, int left, int right) {
	if (left+1>=right) {
		return;
	}
    //小区间优化，区间内的个数小于10时采用插入排序
    if(right-left<10){
        InsertSort(a,right-left+1);
    }else{
	int div = partion(a, left, right);
	QuickSort(a, left, div - 1);
	QuickSort(a, div+1, right);
    }    
}

特殊情况：当待排序序列为同一个值或者大量相同数值时，优化也不能解决此类问题，此时不建议采用快速排序。

          

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧


网站标题：经典排序之快速排序-创新互联
分享路径：http://jkwzsj.com/article/dphghe.html

其他资讯