算法思想:
略,应该很简单了
int partition(int a[], int left, int right) {
int temp = a[left];
while (left < right) {
while (left < right && a[right] > temp) right--;
a[left] = a[right];
while (left < right && a[left] <= temp) left++;
a[right] = a[left];
}
a[left] = temp;
return left;
}
void quicksort(int a[], int left, int right) {
if (left < right) {
int pos = partition(a, left, right);
quicksort(a, left, pos - 1);
quicksort(a, pos + 1, right);
}
}
优化,随机数算法写快排
learn && wrong:
1、包括库函数<time.h>和<stdlib.h>
2、srand(unsigned)函数和time()函数 + rand()函数
3、rank()函数只能怪【0,rand_max】范围内的整数(rand_max是stdlib.h中一个常数,不同系统有所不同
如果想要给定输出范围的随机数函数,则使用rand() % (b - a + 1),范围是[0,b - a]
再加上a,就是【a,b】
4、生成更大范围的随机数:先用rand()生成一个[0,rand_manx()]范围内的随机数,然后用这个随机数除以rand_max,这样就会得到一个[0,1]范围内的浮点数。
接下来用这个浮点数乘以范围(b - a + 1)即可,再加上aj即可
本质:是生成一个比例,乘以范围,再加上起点
#include <stdlib.h>
#include <time.h>
#include <cstdio>
using namespace std;
int main() {
srand((unsigned)time(NULL));
for (int i = 0;i < 10;++i) { //10000,60000
printf("%d",(int)(round(1.0 * rand() / RAND_MAX) * 50000 + 10000))
}
return 0;
}
5、随机数快排,
1、现在[left,right]内生成一个随机数p,然后以A[P]作为主元来划分。
2、将a[p]与a[left]交换,然后按原先partition函数的写法即可。(其实就是加两句话)
int randpartition(int a[], int left, int right) {
int p = (round(1.0 * rand() / max_rand) * (right - left ) + left;
swap(a[left],a[p]);
int temp = a[left];
while (left < right) {
while (left < right && a[right] > temp) right--;
a[left] = a[right];
while (left < right && a[left] <= temp) left++;
a[right] = a[left];
}
a[left] = temp;
return left;
}
网友评论