美文网首页
归并+快排+随机数+随机数快排->two points

归并+快排+随机数+随机数快排->two points

作者: km15 | 来源:发表于2020-02-06 13:02 被阅读0次

    算法思想:
    略,应该很简单了

    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;
    }

    相关文章

      网友评论

          本文标题:归并+快排+随机数+随机数快排->two points

          本文链接:https://www.haomeiwen.com/subject/kqbyxhtx.html