精华内容
下载资源
问答
  • 又叫线性选择算法,这是一种平均情况下时间复杂度为O(n)的快速选择算法,用到的是快速排序中的第一步,将第一个作为中枢,使大于它的所有放到它右边,小于它的所有放到它左边。下面是具体的算法步骤: 1,选择...

    又叫线性选择算法,这是一种平均情况下时间复杂度为O(n)的快速选择算法,用到的是快速排序中的第一步,将第一个数作为中枢,使大于它的所有数放到它右边,小于它的所有数放到它左边。之后比较该中枢的最后位置i与k的大小,若i比k小,说明第k小的元素在i的右半段,之后对i的右半段进行快速选择;若i比k大,说明第k小的元素在i的左半段,之后对i的左半段进行快速选择;若i正好等于k,则直接返回......。

    下面是具体的算法步骤:

    1,选择中枢:如下,为了提高快速选择的效率,最好尽可能的选择数值居中的数作为中枢。如1 7 2 8 4 3,则取头尾以及中间位置,然后选择(1, 2, 3)中的2

    int median3(int nums[], int left, int right){
    	int center = (left + right) / 2;
    	if(nums[left] > nums[center])
    		swap(nums[left], nums[center]);
    	if(nums[left] > nums[right])
    		swap(nums[left], nums[right]);
    	if(nums[center] > nums[right])
    		swap(nums[center], nums[right]);//此时nums[left] <= nums[center] <= nums[right]
    	swap(nums[center], nums[right-1]);//交换中枢和a[right-1],此时上面三个值的居中的数在下标right-1处,然后返回中枢,由于a[right]必定比中枢大,故只需对区间[left, right-1]以中枢a[right-1]进行一次快速排序即可。
    	return nums[right-1];
    }

    2,对区间[left, right-1]以中枢nums[right-1]进行一次快速排序,之后大于nums[right-1]的数全在它的右边,小于nums[right-1]的数全在它的左边

    int pivot = nums[right-1], i = left, j = right-1;
    while(i < j){
    	while(nums[i] < pivot && i < j) ++i;
    	nums[j] = nums[i];
    	while(nums[j] >= pivot && i < j) --j;
    	nums[i] = nums[j];
    }
    nums[i] = pivot;

    3,比较i和k的大小:若求序列中的第k大的数,现在由步骤2已经知道一次选择排序后的中枢下标为i,说明前面i个数比pivot大,后面right-i个数比pivot大。
    如果k < i,说明第k大的数在前面i个数中;如果k > i,说明第k大的数在后面的right-i中;如果i==k,直接返回答案。对于前两种情况只需要对pivot的左半段或者右半段中寻找即可,即:

    if(k < i)
    	QuickSelect(nums, k, 0, i-1);
    else if(k > i)
    	QuickSelect(nums, k, i+1, right);
    else
    	return nums[i];

    完整代码如下:

    #include <iostream>
    using namespace std;
    int median3(int nums[], int left, int right){
    	int center = (left + right) / 2;
    	if(nums[left] > nums[center])
    		swap(nums[left], nums[center]);
    	if(nums[left] > nums[right])
    		swap(nums[left], nums[right]);
    	if(nums[center] > nums[right])
    		swap(nums[center], nums[right]);//此时nums[left] <= nums[center] <= nums[right]
    	swap(nums[center], nums[right-1]);//交换中枢和a[right-1],此时上面三个值的居中的数在下标right-1处,然后返回中枢,由于a[right]必定比中枢大,故只需对区间[left, right-1]以中枢a[right-1]进行一次快速排序即可。
    	return nums[right-1];
    }
    
    int QuickSelect(int nums[], int k, int left, int right){
    	int pivot = median3(nums, left, right), i = left, j = right-1;
    	while(i < j){
    		while(nums[i] < pivot && i < j) ++i;
    		nums[j] = nums[i];
    		while(nums[j] >= pivot && i < j) --j;
    		nums[i] = nums[j];
    	}
    	nums[i] = pivot;
    	if(k < i)
    		QuickSelect(nums, k, 0, i-1);
    	else if(k > i)
    		QuickSelect(nums, k, i+1, right);
    	else
    		return nums[i];
    }
    
    int main(){
    	int k, nums[12] = {4, 5, 23, 12, 89, 20, 14, 23, 54, 66, 47, 23};
    	while(cin >> k)
    		cout << QuickSelect(nums, k-1, 0, 11) << endl;//第k大的数下标应为k-1
    	return 0;
    }

    运行结果如下:



    时间复杂度:每次尽可能的遍历数组的一半,故平均情况下的时间复杂度为O(n/2) + O(n/4) + O(n/8) + ... +O(1) = O(n)

    展开全文
  • 基于平均值为枢轴的快速排序算法

    千次阅读 热门讨论 2019-09-08 10:06:23
    但是各种博客以及论文中对于基于平均值的快速排序的具体都闭口不谈,后来我用了大概两三个小时通过修改现有的快速排序代码得到了基于平均值的快速排序代码。这也是我的第一篇博客,希望大家支持,这也是我继续写下去...

    题目来源

    这是我在2019年研究生入学考试中遇到的一道题目,之前我们所认识的快速排序无外乎是以第一个元素或中位数作为枢轴。但是使用的第一个元素作为枢轴存在一个问题,我在接下来的分析中将进行阐述。但是各种博客以及论文中对于基于平均值的快速排序的具体都闭口不谈,后来我用了大概两三个小时通过修改现有的快速排序代码得到了基于平均值的快速排序代码。这也是我的第一篇博客,希望大家支持,这也是我继续写下去的动力。

    原有快速排序算法

    假设排序的数组是A[0]…A[n-1],首选任意选取一个数据,但是通常都是选择A[0]元素作为关键数据,然后将所有比他小的元素都放到他的左边,所有比他大的元素都放到他的右边,这一过程称为一趟快速排序。值得注意的是,快速排序不是一种稳定的快速排序。

    一趟快速排序的算法是
    1).设置两个变量i,j,排序开始的时候:i=0,j=N-1;
    2). 一般以第一个数字元素作为关键元素,赋值给key,即key=A[0];
    3). 从j开始向前搜索,即由后向前进行搜索(j–),扎到第一个小于key的值,将A[j]与A[i]的值交换;
    4). 从i开始向后搜索,即由前开始向后搜索(i++),找到第一个大于key的A[i],将A[i]和A[j]的值交换;
    5). 重复第3、4步,直到i=j; (3,4步中,没找到符合条件的值,即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值,使得j=j-1,i=i+1,直至找到为止。找到符合条件的值,进行交换的时候i, j指针位置不变。另外,i==j这一过程一定正好是i+或j-完成的时候,此时令循环结束)。
    这一部分的分析我就不多进行解释了,因为网上的各种博客都已经写的很清楚的,代码也很成熟了。

    原有算法的缺陷

    1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
    如果这个是使用第一个元素进行分割的话,那么将分割9次,这样就将快速排序的时间复杂度从O(nlog2n)增加到了O(n2。对于快速排序来说,最优的方式就是平均分割,但是当原有序列基本有序或者基本逆序的情况下,以第一个元素分割的结果就会十分不平衡。所以我们应该选择一个最平均的分割方式,这个方式就是基于平均值为枢轴的快速排序。

    代码

    #include<stdio.h>
    void quicksort(int A[],int low,int high){
    	if(low<=high) {
    		int i,j,temp,sum=0,ave,t;
    		for(i=low;i<=high;i++){
    		sum+=A[i];
    		}
    		i = low;
    		j = high;
    		ave = sum/(high-low+1);
    		while(i<j){
    			while(A[i]<ave&&i<=j)  ++i;
    			while(A[j]>ave&&i<=j)  --j;
    			if(i<j){
    				temp = A[i];
    				A[i] = A[j];
    				A[j] = temp;
    				i++;
    				j--;
    			}
    		}
    
    		if(i<high&&j>low){
    			quicksort(A,low,j);
    			quicksort(A,i,high);
    		}
    		else return;
    	}
    }
    
    展开全文
  • 快速排序算法

    千次阅读 2019-01-12 13:50:17
    快速排序时间复杂度在最好的情况下是O(n log n),在平均情况下是O(n log n),在最坏的情况下是O(n ^ 2)...快速排序算法是分治策略的一种应用,其核心思想是把输入的数组从左向右的大于基准的元素 与 从右...

    快速排序时间复杂度在最好的情况下是O(n log n),在平均情况下是O(n log n),在最坏的情况下是O(n ^ 2)。但是因为它在大多数输入的平均情况下具有最佳性能,所以快速排序通常被认为是“ 最快 ”的排序算法。另外,快速排序算法是不稳定的,即如果两个元素数值相同,快排结果后位置可能不同。

    快速排序算法是分治策略的一种应用,其核心思想是把输入的数组从左向右数的大于基准数的元素 从右往左的小于基准数的元素 交换(以第一个元素为基准数pivot),然后递归地将左右两区域进一步排序,直到 left 不再 < right。

    快速排序(c++代码示例已运行通过)

    #include <iostream>
    using namespace std;
    int partation(int a[], int left, int right);
    void quickSort(int a[],int left, int right) {
    	if(left < right) {
    		int anchor = partation(a, left, right);
    		quickSort(a, left, anchor - 1);
    		quickSort(a, anchor + 1, right);
    	}
    }
    
    int partation(int a[], int left, int right){
    	int i = left, j = right + 1;
    	int pivot = a[left];
    	//把小于pivot的元素交换到左边,大于pivot的元素到右边 
    	while(true){
    		//即当a[i]小于pivot时且i<j时,下标i不断右移(直到a[i]>=pivot)时,交换a[i],a[j] 
    		while(a[++i] < pivot && i < j);
    		while(a[--j] > pivot);
    		if (i >= j)
    			break;
    		swap(a[i], a[j]); 
    	}
    	a[left] = a[j];
    	a[j] = pivot;
    	//返回下标j为划分点 
    	return j;
    }
     
    int main(){
    	int a[] = {13, 22, 45, 11, 73, 26, 38};
    	int n = 7;
    	quickSort(a, 0, n - 1);
    	for(int i = 0; i < n; i++)
    		cout << a[i] << ' ';
    	return 0;
    }

    以上代码我解释一下:

    partation的作用主要是将小于pivot的元素放在数组左半边,将大于pivot的元素放在右半边。然后quickSort将以anchor划分开的左右区域进一步进行排序,如此一直递归地调用,直到下标left跟right相撞。

    这里注意一个,int pivot =a[left],基准数的选择是任意的。它可以是数组的第一个元素,数组的最后一个元素,甚至是随机元素!

    快排性能取决于划分的对称性,分治法的性能经大量经验表明当划分为接近对称时,性能最优,所以快速排序的基准数有时会用一个random函数特意的挑选随机元素以求该元素是接近元素中间值的。但其实我觉得没什么卵用,因为如果数组元素真的是无序的,那么不管是哪里的元素应该效果都是一样的。所以除非在数据显现出一定的规律让你觉得最左最右的元素会使划分严重不对称时,可以考虑用随机函数。

     

    展开全文
  • 同样地,它在实际应用是一种高效的算法,具有很好的平均时间复杂度,然而最坏时间复杂度则不理想。快速选择及其变种是实际应用中最常使用的高效选择算法快速选择的总体思路与快速排序一致,选择一

    部分内容转载:https://blog.csdn.net/dacixie/article/details/79477421
    感谢博主的整理

    快速选择:

    快速选择(英语:Quickselect)是一种从无序列表找到第k小元素的选择算法。它从原理上来说与快速排序有关。与快速排序一样都由托尼·霍尔提出的,因而也被称为霍尔选择算法。同样地,它在实际应用是一种高效的算法,具有很好的平均时间复杂度,然而最坏时间复杂度则不理想。快速选择及其变种是实际应用中最常使用的高效选择算法。

    快速选择的总体思路与快速排序一致,选择一个元素作为基准来对元素进行分区,将小于和大于基准的元素分在基准左边和右边的两个区域。不同的是,快速选择并不递归访问双边,而是只递归进入一边的元素中继续寻找。这降低了平均时间复杂度,从O(n log n)至O(n),不过最坏情况仍然是O(n2)。

    快速排序一样,快速选择一般是以原地算法的方式实现,除了选出第k小的元素,数据也得到了部分地排序。

    如果不理解快速选择的过程,因为快速选择和快速排序的过程可以说是很相近,所以建议大家先看一个短短10分钟由北京大学陈斌老师的快速排序算法讲解视频:

    快速排序算法讲解
    在这里插入图片描述

    快速选择的总体思路与快速排序一致,选择一个元素作为基准来对元素进行分区,将小于和大于基准的元素分在基准左边和右边的两个区域。不同的是,快速选择并不递归访问双边,而是只递归进入一边的元素中继续寻找。这降低了平均时间复杂度,从O(n log n)至O(n),不过最坏情况仍然是O(n2)。

    与快速排序一样,快速选择一般是以原地算法的方式实现,除了选出第k小的元素,数据也得到了部分地排序。

    Quick Select的目标是找出第k大元素,所以

    若切分后的左子数组的长度 > k,则第k大元素必出现在左子数组中;
    若切分后的左子数组的长度 = k-1,则第k大元素为pivot;
    若上述两个条件均不满足,则第k大元素必出现在右子数组中。

    代码函数如下:

    def qselect(A,k):    
        if len(A)<=k:return A    #若数组长度小于k,则输出前k个最小数构成的数组
        pivot = A[0]    #中位数
        left = [pivot] + [x for x in A[1:] if x<=pivot]  #中位数左边的数组
        llen = len(left)    #中位数左边数组的长度,全是比中位数小的数
        if llen==k:    #如果刚好为k个,则第k个是第k个最小数
            return left    #输出数组
        if llen > k:    #如果比k大,则需要对这个数组进一步切分
            return qselect(left, k)    #递归继续划分
        else:    
            right = [x for x in A[1:] if x > pivot] #如果长度小于k,那肯定在中位数右边的数组,也就是比中位数大
            return left + [pivot] + qselect(right, k-llen-1) #返回左边+中位数+右边划分
    #所以划分一共有三种情况,恰好k个,比k个少,比k个多,分别对应左、中、右;
    # 划分函数需要两个参数:k/k-llen,以及被划分的数组。
    

    刚好leetcode有一道题:
    设计一个算法,找出数组中最小的k个数。以任意顺序返回这k个数均可。

    示例:
    输入: arr = [1,3,5,7,2,4,6,8], k = 4
    输出: [1,2,3,4]

    class Solution:
        def smallestK(self, arr: List[int], k: int) -> List[int]:
            def helper(arr, k):
            	if k == 0:#个人感觉很有必要
            		return []
                if len(arr) <= k:
                    return arr
                # 快速选择
                midnum = arr[0]  # 中位数取数组第一位
                left = [e for e in arr[1:] if e <= midnum]
                len_left = len(left)  # 左数组的长度
                if len_left == k:
                    return left
                elif len_left > k:
                    return helper(left, k)  # 继续分
                else:  # 长度比k还小,只能把中位数右边的也加进来了
                    right = [e for e in arr[1:] if e > midnum]
                    return left + [midnum] + helper(right, k - len_left-1)  # left已经被算进里面了,所以只需要在right里面找k-lenleft-1就好
            return helper(arr,k)
    

    如果要找出最大的K个数呢?魔改一下代码

    def helper(arr, k):
        if k == 0:#个人感觉很有必要
            return []
        if len(arr) <= k:
            return arr
        # 快速选择
        midnum = arr[0]  # 中位数取数组第一位
        right = [e for e in arr[1:] if e >= midnum]
        len_right = len(right)  # 右数组的长度
        if len_right == k:
            return right
        elif len_right > k:
            return helper(right, k)  # 继续分
        else:  # 长度比k还小,只能把中位数左边的也加进来了
            left = [e for e in arr[1:] if e < midnum]
            return right + [midnum] + helper(left, k-len_right-1)  # left已经被算进里面了,所以只需要在right里面找k-lenleft-1就好
    
    展开全文
  • 快速选择算法

    千次阅读 2019-10-23 10:28:00
    简介 在构造kd-tree中,我们需要对方差最大维度上的中位进行计算。中位计算方法的好坏一定程度上影响了树的构造时间...所以有了选择算法,其平均时间复杂度为O(n),最坏时间复杂度为O(n2)。在Rob Hess 的s...
  • 快速排序算法 快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n log n)次比较。...快速排序是对冒泡排序的改进,它使用分治法的思想,每次循环根据指定的基准,将...
  • 快速排序算法总结C++

    2019-10-16 20:21:47
    快速排序的时间复杂度最坏为,平均时间复杂度为,采用了分而治之思想,是不稳定算法(一趟排序后,数列中原来前后位置顺序不变)。具体实现原理如下: a1 从数列中任意选取一个作为基准(枢轴,pivot) a2 ...
  • 时间复杂度为O(nlogn) n为元素个 1. 快速排序的三个步骤: 1.1. 找到序列中用于划分序列的元素 1.2. 用元素划分序列 1.3. 对划分后的两个序列重复1,2两个步骤指导序列无法再划分 所以对于n个元素其排序时间为 T...
  • 排序之快速排序算法 使用分治策略的快速排序,是一种很好的内排序,经常出现在面试题中,所以如果你想成为一名有优秀的程序员,理解并熟练掌握快速排序是你必须要学会的基本技能之一。 快速排序的时间复杂度: ...
  • 快速排序是实际运用中用的最多的算法,虽然它在最坏的情况下会达到n^2,但它的平均性能非常好,期望时间复杂度为nlgn,而且隐含的常数因子非常小,并且是原址排序。 快速排序原理:从一组中任意选出一个,将...
  • 快速排序算法分析

    2019-10-07 13:57:29
    关于快速排序算法,由于其有着很好的平均时间复杂度而得到了广泛的应用。 快排的思想:每次从数组中取出一个元素出来,然后将该元素放置到一个合适的位置,使得该元素前面的都小于或等于该元素,其后面的都大于...
  • 快速排序算法的思想/特点 1.选取一个数字作为基准,(基数可以随机取,也可选取首位数字) ...快速排序算法的时间复杂度:平均时间:O(nlog2n) (n倍的以2为底n的对数), 最坏情况:O(n2) ; 对于大...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 865
精华内容 346
关键字:

平均数快速算法