本文主要是介绍快速排序之随机化，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
快速排序的思想就是选择一个基准数，让每个数与它比较，找到它在所有这些数排好序后应该在的位置。
而快速排序对大体应经排好序的数执行效率是n^2，所以对基准数随机化，以下代码
#include <iostream>
#include <cstdlib>using namespace std;//产生m到n的随机数
int Random(int m, int n)
{int pos, dis;if(m == n){return m;}else if(m > n){pos = n;dis = m - n + 1;return rand() % dis + pos;}else{pos = m;dis = n - m + 1;return rand() % dis + pos;}
}void randomizedPartition(int *a,int left, int right)
{int i = Random(left,right);int temp = a[i];a[left] = a[i];a[i] = temp;
}//该快速排序由于是默认以数组第一个数作为基准数，存在很大偶然性
//最好情况nlogn,最坏情况n^2
void quickSort(int *p,int left,int right)
{if(left < right){randomizedPartition(p,left,right); //让基准数是数组中的一个随机位置的数 int cut = p[left]; //以第一个数为基准数，将该基准数放在切确的位置以至于把整个数组分割成两半 int i = left;int j = right;while(i < j){while(i < j && p[j] > cut) //从右往左，作比较 {j--;}if(i < j){p[i++] = p[j]; //这里算编程中技巧,用i那个位置存储一下j的数，而i的数已经保存在临时变量cur。或者另一种选择就是把i，j都找到再做交换 } while(i < j && p[i] < cut) //从左往右，做比较 {i++;}if(i < j){p[j--] = p[i];}}p[i] = cut; //i就是cur这个基准数的确切位置 quickSort(p,left,i-1);quickSort(p,i+1,right);}
}int main()
{int a[10] = {2,5,8,4,6,8,25,1,3,5};quickSort(a,0,10-1);for(int i = 0; i<10; i++)cout<<a[i]<<" ";
}这篇关于快速排序之随机化的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
