精华内容
下载资源
问答
  • 常见排序算法:随机化快速排序算法
    千次阅读
    2019-07-03 17:11:07

    基本思想:在快速排序的思想上,对基数的选择采用了一个随机化的选择。

    1.对于递归到某一层的数组中,在该数组中随机化选择一个数字,把数组中的数字分为两部分,比该数字小的数据都放在它的左边,比该数字大的数据都放在它的右边。

    2.适用递归的思路对每次选出来的数字的左右两边进行排序。

    代码:

    #include <iostream>
    #include<time.h>
    using namespace std;
    
    int RandomInRange(int start, int end)
    {
    	srand((unsigned)time(NULL));
    	return rand() % (end - start + 1) + start;//产生随机数
    }
    int Partition(int data[], int start, int end)
    {
    	int index = RandomInRange(start, end);//随机选择一个位置
    	swap(data[index], data[end]);//将选取的数字放到最后
    
    	int small = start - 1;//small是一个移动指针,在它位置前的数据都是比它小的
    	for (index = start; index < end; index++)
    	{
    		if (data[index] < data[end])//从start开始跟选择出来的数字进行比较
    		{
    			++small;
    			if (small!=index)//不等的情况表示上一次small没有移动即上一次的data[small]>data[end]
    				swap(data[index], data[small]);//交换两个位置的数据
    		}
    	}
    	++small;
    	swap(data[small], data[end]);//将选出来的数字放在合适的位置
    	return small;
    }
    void Random_QuickSort(int data[], int start, int end)
    {
    	if (start == end) return;	//递归中止条件是待排序数组长度为1
    	int index = Partition(data, start, end);	//选出来的数,左边都比它小,右边都比它大
    	if (index > start)	 Random_QuickSort(data, start, index - 1);//左半部分继续排序
    	if (index < end)	 Random_QuickSort(data, index + 1, end);//右半部分继续排序
    }
    
    int main()
    {
    	int list[] = { 12, 5, 4, 6, 7, 6, 1 };
     
    	Random_QuickSort(list,0, sizeof(list) / sizeof(int)-1);
     
    	for (int i = 0; i < sizeof(list) / sizeof(int); i++)
    	{
    		cout << list[i] << endl;
    	}
    }
    

     

    更多相关内容
  • 随机化快速排序

    2020-03-18 10:27:11
    使用Java或C++等语言中内置的随机函数实现随机化快速排序,在数组中随机选择一个元素作为分区的主元(Pivot)。 输入 多组样例输入,每组由一个一维整型数组组成。 输出 随机化快速排序之后的一维整型数组(升序排列)...

    题目描述

    使用Java或C++等语言中内置的随机函数实现随机化快速排序,在数组中随机选择一个元素作为分区的主元(Pivot)。

    输入

    多组样例输入,每组由一个一维整型数组组成。

    输出

    随机化快速排序之后的一维整型数组(升序排列)。

    样例输入
    
    6 1 8 6 5 3 4
    5 12 42 2 5 8
    
    样例输出
    
    1 3 4 5 6 8
    2 5 8 12 42
    
    import java.util.Random;
    import java.util.Scanner;
    
    public class Main {
    	public static int Random_Partition(int a[],int p,int q) {
    		//随机选取基准
    		Random random = new Random();
            int i = random.nextInt(q)%(q-p+1) + p;
    		swap(a,q,i);
    		return partition(a, p, q);
    	}
    	
    
    	public static void swap(int a[],int i,int j) {
    		//交换函数
    		int t;
    		t = a[i];
    		a[i] = a[j];
    		a[j] = t;
    	}
    	
    	public static int partition(int a[],int p,int q) {
    		//分区函数,数据分区
    		int x=a[p];
    		int i=p;
    		for(int j=p+1;j<=q;j++) {
    			if(a[j]<=x) {
    					i = i+1;
    					swap(a,i,j);
    				}
    			}
    		swap(a,p,i);
    		return i;
    	}
    	
    	public static void QuickSort(int a[],int p,int q) {
    		//排序函数,递归排序
    		if(p<q) {
    			int r = Random_Partition(a, p, q);
    			//基准随机产生
    			QuickSort(a, p, r-1);
    			QuickSort(a, r+1, q);
    		}
    	}
    	
    	
    	public static void main(String[] args) {
    		Scanner sc = new Scanner(System.in);
    		int n;
    		while(sc.hasNext()) {
    			n = sc.nextInt();
    			int a[] = new int[n];
    			for(int i=0;i<n;i++) {
    				a[i] = sc.nextInt();
    			}
    			QuickSort(a, 0, n-1);
    			for(int i=0;i<n;i++) {
    				if(i==n-1)
    					System.out.printf("%d\n",a[i]);
    				else
    					System.out.printf("%d ",a[i]);
    			}
    		}
    		sc.close();
    	}
    }
    

    在快速排序的基础上进行随机选取基准,确保不会出现最坏情况,使方法更加快速,是快速排序的改进操作。

    展开全文
  • 算法的平均时间复杂度为O(nlogn)。但是当输入是已经排序的数组...引入这一步来修正原先的快速排序,可得到下面所示的随机化快速排序。新算法只是在区间[low…high]中一致随机地选择一个索引v,并将A[v]和A[low]交换,然
  • 在输入序列个数、排序情况不同的情况下对确定性快速排序与随机化快速排序的比较。比较他们的运行时间,验证是否与理论相符。
  • 使用Java或C++等语言中内置的随机函数实现随机化快速排序,在数组中随机选择一个元素作为分区的主元(Pivot)。 输入 多组样例输入,每组由一个一维整型数组组成。 输出 随机化快速排序之后的一维整型数组(升序排列...

    问题导入:

    使用Java或C++等语言中内置的随机函数实现随机化快速排序,在数组中随机选择一个元素作为分区的主元(Pivot)。
    输入
    多组样例输入,每组由一个一维整型数组组成。
    输出
    随机化快速排序之后的一维整型数组(升序排列)。

    样例输入

    6 1 8 6 5 3 4
    5 12 42 2 5 8

    样例输出
    1 3 4 5 6 8
    2 5 8 12 42

    个人分析:
    首先还是得了解一下快速排序:
    https://blog.csdn.net/weixin_42429718/article/details/88830096
    随机化快速排序只是在快排基础上将主元通过随机函数选取一下了。

    //随机产生一个k
    int Chocolate_randomswap(vector<int> & v,int p,int q)
    {
        int k=(rand() % (q-p+1))+ q;
        Chocolate_swap(v,k,p);
        return Chocolate_partition(v,p,q);
    }
    
    #include<iostream>
    #include<vector>
    using namespace std;
    vector<int> vec;
    void Chocolate_swap(vector<int> &v,int a,int b)
    {
        int temp=v[a];
        v[a]=v[b];
        v[b]=temp;
    }
    
    int Chocolate_partition(vector<int> & v,int p,int q)
    {
        int i=p;
        int x=v[p];
        int j;
        for(j=p+1;j<=q;j++)
        {
            if(v[j]<=x)
            {
                ++i;
                Chocolate_swap(v,i,j);
            }
        }
        Chocolate_swap(v,i,p);
        return i;
    }
    
    //随机产生一个k
    int Chocolate_randomswap(vector<int> & v,int p,int q)
    {
        int k=(rand() % (q-p+1))+ q;
        Chocolate_swap(v,k,p);
        return Chocolate_partition(v,p,q);
    }
    
    
    void Chocolate_QuickSort(vector<int>& v,int p,int q)
    {
        if(p<q)
        {
            int k=Chocolate_partition(v,p,q);
            Chocolate_QuickSort(v,p,k-1);//对左边进行递归调用
            Chocolate_QuickSort(v,k+1,q);//对右边部分进行递归调用
        }
    }
    
    
    
    
    int main()
    {
        int n;
        while(cin>>n)
        {
            vec.clear();
            for(int i=0;i<n;i++)
            {
                int x;
                cin>>x;
                vec.push_back(x);
            }
            Chocolate_QuickSort(vec,0,n-1);
            int len=vec.size();
            for(int i=0;i<vec.size();i++)
            {
                cout<<vec[i];
                if(len)
                {
                    len--;
                    cout<<" ";
                }
    
            }
            cout<<endl;
            //vec.clear();
        }
    
    
        return 0;
    }
    
    

    =============== 2020 3月31日更新代码==========================

    #include<bits/stdc++.h>
    using namespace std;
    vector<int> vec;
    const int maxn=1000+8;
    int a[maxn];
    int n;
    int quick_partition(int p,int q){
        int i=p;
        int x=a[p];
        for(int j=p+1;j<=q;j++){
            if(a[j]<=x){
                ++i;
                swap(a[i],a[j]);
            }
        }
        swap(a[i],a[p]);
        return i;
    }
    int rand(int p,int q){
        int k=rand()%(q-p+1)+p;
        swap(a[k],a[p]);
        return quick_partition(p,q);
    }
    void qsort(int p,int q){
        if(p<q){
            int k=rand(p,q);
            qsort(p,k-1);
            qsort(k+1,q);
        }
    }
    int main()
    {
        while(cin>>n){
            for(int i=0;i<n;i++)
                cin>>a[i];
            qsort(0,n-1);
            for(int i=0;i<n;i++)
                cout<<a[i]<<" ";
            cout<<endl;
        }
        return 0;
    }
    
    学如逆水行舟,不进则退
    
    展开全文
  • 快速排序的三种写法及随机主元快速排序时间复杂度是nlgn,
  • 最省时间的是确定型算法,其次是随机基准快速排序算法,最后是随机化输入快速排序算法;后面两个算法较之确定型算法要费时的原因是:(1)随机选取基准花费了一些时间,(2)随机化输入是将原来数组打乱花费了一些时间。...
  • 分治算法三(随机化快速排序

    千次阅读 2013-05-11 18:03:35
    1、快速排序对于输入数据的顺序比较敏感。主要在于每次划分对主元的选择。基本的快速排序选取第一个元素作为主元。这样在数组已经有序的情况下,每次划分将得到最坏的结果。这个时候,时间复杂度...实际上,随机化快速

    1、快速排序对于输入数据的顺序比较敏感。主要在于每次划分对主元的选择。基本的快速排序选取第一个元素作为主元。这样在数组已经有序的情况下,每次划分将得到最坏的结果。这个时候,时间复杂度将会退化到O(n^2)。
    2、一种比较常见的优化方法是随机化算法,即随机选取一个元素作为主元。这种情况下虽然最坏情况仍然是O(n^2),但最坏情况不再依赖于输入数据,而是取决于随机函数随机数的选取。实际上,随机化快速排序得到理论最坏情况的可能性仅为1/(2^n)。所以随机化快速排序可以对于绝大多数输入数据达到O(n*logn)的期望时间复杂度。
    3、随机化快速排序的唯一缺点在于,一旦输入数据中有很多的相同数据,随机化的效果将直接减弱。对于极限情况,即对于n个相同的数排序,随机化快速排序的时间复杂度将毫无疑问的降低到O(n^2)。解决方法是用一种方法进行扫描,使没有交换的情况下主元保留在原位置。


    /* file: random_quick_sort					*/
    /* 1、find the pivot of the Array by using 
    	  random algorithm						*/
    /* 2、divide the Array into two subarrays	*/
    /* 3、conquer the two subarrays				*/
    /* 4、the Array is sorted,when conquer ended*/
    
    #include<stdio.h>
    #include <stdlib.h>
    
    /*=====================================
      swap:swap two numbers a and b
    =======================================*/
    inline void swap(int* a,int* b)
    {
    	int tmp;
    	tmp  = *a;
    	*a   = *b;
    	*b   = tmp;
    }
    /*=====================================
      Partition:Partition the Array from start
    			to end into two subarrays.
    			Return the pivot of the element
    			Array[start]
    =======================================*/
    int Partition(int* Array, int start, int end)
    {
    	//choose Array[start] as the pivot element 
    	//divide the array into two subarrays.
    	//left of the Array's elements <= Array[start]
    	//right of the array's elements > Array[start]
    	int pivot = start,j;
    	for(j = start + 1; j <= end; j++)
    		if(Array[j] <= Array[start])
    		{
    			pivot++;
    			swap(&Array[pivot], &Array[j]);
    		}
    	swap(&Array[start], &Array[pivot]);
    	return pivot;
    }
    /*=====================================
      RandomPartition:using random algorithm.partition the
    				  Array into two subarrays.Return the 
    				  pivot of the element Array[start] which
    				  is already swaped
    =======================================*/
    int RandomPartition(int* Array, int start, int end)
    {
    	//generate the random index of the pivot
    	int random_index = start + rand() % (end - start + 1);
    	//swap the pivot with the random_index element
    	swap(&Array[start], &Array[random_index]);
    	//now random_index element act as the start element
    	return Partition(Array,start,end);
    }
    
    /*=====================================
      RandomQuickSort:Sort the Array using QuickSort
    				  algorithm.By partition an Array
    				  into two subarrays and then 
    				  conquer the two subarrays.
    =======================================*/
    void RandomQuickSort(int* Array, int start,int end)
    {
    	int pivot;
    	if(start < end)
    	{
    		//find the pivot of the array
    		pivot = RandomPartition(Array, start, end);
    		//conquer the left subarray
    		RandomQuickSort(Array, start, pivot - 1);
    		//conquer the right subarray
    		RandomQuickSort(Array, pivot + 1, end);
    	}
    }
    
    void main()
    {
    	int n,i;
    
    	printf("Please input the length of Array<0:exit>:\n");
    	while(scanf("%d",&n),n)
    	{	
    		//create an arrays of length n
    		int* Array = new int[n];
    		//get the input integers
    		printf("Please input %d integers:\n",n);
    		for(i = 0; i < n; i++)
    			scanf("%d",&Array[i]);
    		//use QuickSort algorithom
    		RandomQuickSort(Array,0,n-1);
    		//print the sorted array
    		printf("Sorted Array:\n");
    		for(i = 0; i < n; i++)
    			printf("%d ",Array[i]);
    		system("pause");
    		system("cls");
    		//delete the array
    		delete[] Array;
    		printf("Please input the length of Array<0:exit>:\n");
    	}
    }


    展开全文
  • Java实现的快排排序,包含随机快排,还有两种快速排序的时间对比..
  • 快速排序算法是基于分治策略的另一个排序算法。它的基本思想是、:(1)分解(divide):以数组a[p,r ]中的某一个数a[q]将数组分成三部分:a[1...q-1] a[q] a[q+1...r]。其中a[1...q-1]中的任何一个数都比a[q]小,而...
  • C++随机化快速排序

    千次阅读 2011-10-29 00:08:42
    C++随机化快速排序 // 随机化快速排序.cpp : Defines the entry point for the console application. // #include "stdafx.h" #include #include using namespace std; double a[100]; int random(int m,int...
  • 使用Java或C++等语言中内置的随机函数实现随机化快速排序,在数组中随机选择一个元素作为分区的主元(Pivot)。 输入 多组样例输入,每组由一个一维整型数组组成。 输出 随机化快速排序之后的一维整型数组(升序...
  • 快速排序随机快速排序

    万次阅读 2015-06-16 21:10:47
    原创作品 转载请注明出处http://blog.csdn.net/always2015/article/details/46523531一、问题描述实现对数组的普通快速排序随机快速排序 (1)实现上述两个算法 (2)统计算法的运行时间 (3)分析性能差异,...
  • 随机化快速排序算法

    2013-08-06 19:56:28
    Quicksort是一个很好的排序算法,但是其最坏情况运行时间是O(n^2), 还不如Mergesort的O(nlgn), 如何改进Quicksort? 引进随机化思想 一种方法: 对给定的待排序序列,随机地重排列另一种方法:随机选取
  • Java 算法:随机化快速排序

    千次阅读 2019-04-22 16:31:21
    也就是快速排序法的最差情况下,每次选定的都是最左边的元素,而我们又希望能选择整个数组中间的位置元素,如果不能准确的定位中间位置的元素,我们可以利用随机选择一个元素,此时的利用随机选取的快速排序的期望值...
  • 算法导论(一):快速排序随机化快排

    万次阅读 多人点赞 2015-03-20 19:51:23
    快速排序用到了分治思想,同样的还有归并排序。乍看起来快速排序和归并排序非常相似,都是将问题变小,先排序子串,最后合并。不同的是快速排序在划分子问题的时候经过多一步处理,将划分的两组数据划分为一大一小,...
  • 如何随机排列数列? 用这个 random_shuffle() 可以得到一个随即排序: 先用数组构造一个 vector 容器, 然后给 random_shuffle() 算法传递容易的首尾迭代器即可
  • java实现快速排序随机快速排序

    千次阅读 2016-05-12 16:31:56
    快速排序快速排序随机化版本性能分析 随机序列10w100w1000w有序序列10w1w1000w 排序算法是算法学习的第一步,想当初我学的第一个算法就是选择排序,不过当时很长一段时间我都不清楚我到底用的是...
  • 快速排序的运行时间是根据输入序列顺序来决定的,但是我们选择了随机化算法,将运行时间独立于输入序列顺序,收随机生成器的影响
  • 1.1 快速排序 快速排序(Quicksort)是对冒泡排序的一种改进。它由C. A. R. Hoare在1960年提出,也是一种交换排序。它采用了分冶法,基本思路如下: 先从数列中取出一个数作为主元。 分区过程:把比这个数大的数全...
  • 随机快速排序C++实现

    2017-11-27 13:31:28
    传统的随机快速排序,是选定一个数,然后以这个数为标杆,分为小于等于(标杆)区和大于(标杆)区。 改进的快速排序,分为,小于区,等于区和大于区。这个划分的过程用partition函数实现。 具体请看代码。 #ifndef ...
  • python实现快速排序

    2019-03-25 20:52:12
    利用python代码实现数据结构的经典算法——快速排序算法。
  • 快速排序与随机化快速排序. 2 快速排序. 2 随机化快速排序. 3 快排与随机化快排性能分析. 4 不同配置的计算机运算效果. 4 不同初始序列对快速排序的影响. 7 数据相对于其多运算的平均值的波动. 11 ...
  • C++ 快速排序 记录 都是网上的资源,侵删。 今天学习了快速排序算法,它们的时间以及空间复杂度表格: 快速排序(Quicksort)是对冒泡排序的一种改进。 快速排序由C. A. R. Hoare在1960年提出。它的基本思想是:...
  • 快速排序随机快排

    千次阅读 2020-12-09 13:13:56
    快速排序大家应该都比较了解了,利用分治法的思想,将原有的数据分成两个部分,递归分治排序。大致有 4 个步骤: 首先设定一个分界值,通过该分界值将数组分成左右两部分。 将大于或等于分界值的数据集中到数组右边...
  • 我们在讨论快速排序平均性能时,前提假设是:输入数据的所有排练都是等概率的,但在实际工程中这种情况不总是成立的,所以引入随机化,随机选取一个元素作为主元,因为主元是随机选取的,我们期望在平均情况对输入...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 98,086
精华内容 39,234
关键字:

随机化快速排序