梧州市网站建设,天津城乡住房建设厅网站,学ui设计,西安好的网站建设公司目录 快速排序划分快排 随机划分的快速排序 快速排序
快速排序是排序算法中平均时间复杂度为O(nlogn)的一种算法。
划分
快排的实现需要解决划分的问题#xff1a;对于一个序列A[1]、A[2]、……、A[n]#xff0c;从中选取一个枢轴#xff08;或主元#xff09;#xff… 目录 快速排序划分快排 随机划分的快速排序 快速排序
快速排序是排序算法中平均时间复杂度为O(nlogn)的一种算法。
划分
快排的实现需要解决划分的问题对于一个序列A[1]、A[2]、……、A[n]从中选取一个枢轴或主元如取A[1]为枢轴调整序列中元素的位置使得枢轴左侧所有元素都不超过枢轴右侧所有元素都大于枢轴。 双指针思想
先将A[1]存放至某个临时变量temp并令两个下标left、right分别指向序列首尾如令left 1、right n。只要right指向的元素A[right]大于temp就将right不断左移当某个时候A[right] ≤ temp时将元素A[right]挪到left指向的元素A[left]处。只要left指向的元素A[left]不超过temp就将left断右移当某个时候A[left] temp时将元素A[left]挪到right指向的元素A[right]处。重复②③直达left与right相遇把temp也即原A[1]放到相遇的地方。
以A[left]为枢轴写出划分区间代码
// 对区间[left,right]进行划分
int partition(int left, int right, int A[]) {int temp A[left]; // 将A[left]存放至临时变量tempwhile (left right) { // left right,即枢轴位置while (left right temp A[right]) right--; // 反复左移rightA[left] A[right]; // 将A[right]挪到A[left]while (left right A[left] temp) left; // 反复右移leftA[right] A[left]; // 将A[left]挪到A[right]}A[left] temp; // 把temp放到left与right相遇的地方return left; // 返回相遇的下标
}快排
调整序列中的元素使当前序列最左端的元素在调整后满足左侧所有元素均不超过该元素右侧所有元素均大于该元素。对该元素的左侧和右侧分别递归进行①的调整直到当前调整区间的长度不超过1。
// 快速排序,left与right初值为序列首尾下标(如1与n)
void quick_sort(int left, int right, int A[]) {if (left right) { // left right时,区间只有一个元素int pivot partition(left, right, A); // 将[left,right]按A[left]一分为二quick_sort(left, pivot - 1, A); // 对左子区间递归进行快速排序quick_sort(pivot 1, right, A); // 对右子区间递归进行快速排序}
}随机划分的快速排序
当序列中元素接近有序时选取A[left]作为主元快速排序可能会达到最坏时间复杂度O(n2)。采用随机选择主元的方法则对任意输入数据的期望时间复杂度都能达到O(nlogn)。C语言中产生随机数据 需要添加stdlib.h头问题与time.h头文件。生成随机数的种子写上srand((unsigned) time(NULL));记住即可。在需要使用随机数的地方使用rand()函数。生成[left, right]范围内的随机数 1. rand()函数生成[0RAND_MAX]范围内的随机数。 2. 用这个随机数除以RAND_MAX得到一个[01]范围内的浮点数。 3. 用这个浮点数乘以(right - left)加上left。 4. 再用round()函数需要math.h头文件四舍五入后得到[leftright]范围内的随机数。 5. 这个浮点数相当于[leftright]范围内的比例位置。 6. 例rand()生成的随机数经过处理得到浮点数为0.5left 2right 5right - left 33 * 0.5 1.51.5 2 3.5round(3.5) 4得到[25]范围内的随机数4。
#include stdlib.h
#include time.h
#include math.h// 交换两个数的值
void swap(int *a, int *b) {int temp *a;*a *b;*b temp;
}// 选取随机主元,对区间[left,right]进行划分
int randPartition(int left, int right, int A[]) {// 生成随机数种子srand((unsigned) time(NULL));// 生成[left,right]范围内的随机数pint p (int) round((1.0) * rand() / RAND_MAX * (right - left) left);// 交换A[left]和A[p]swap(A[left], A[p]);// 以下为原先partition函数的划分过程,不需要改变任何东西int temp A[left]; // 将A[left]存放至临时变量tempwhile (left right) { // left right,即枢轴位置while (left right temp A[right]) right--; // 反复左移rightA[left] A[right]; // 将A[right]挪到A[left]while (left right A[left] temp) left; // 反复右移leftA[right] A[left]; // 将A[left]挪到A[right]}A[left] temp; // 把temp放到left与right相遇的地方return left; // 返回相遇的下标
}// 快速排序,left与right初值为序列首尾下标(如1与n)
void quick_sort(int left, int right, int A[]) {if (left right) { // left right时,区间只有一个元素int pivot randPartition(left, right, A); // 将[left,right]按A[left]一分为二quick_sort(left, pivot - 1, A); // 对左子区间递归进行快速排序quick_sort(pivot 1, right, A); // 对右子区间递归进行快速排序}
}
