精华内容
下载资源
问答
  • 数据结构与算法(11): 一网打尽partition算法及其拓展 Partition(划分)算法在快速排序、TopK问题、三色排序等问题上都能展现其巨大价值,本次文章讲述的是parition算法在这些算法问题上的应用以及partition算法是...

    数据结构与算法(11): 一网打尽partition算法及其拓展

    Partition(划分)算法在快速排序、TopK问题、三色排序等问题上都能展现其巨大价值,本次文章讲述的是parition算法在这些算法问题上的应用以及partition算法是如何实现的,文章包括以下6个算法的实现:

    • 1.partition算法的单指针实现;
    • 2.partition算法的双指针实现;
    • 3.快速排序 基于双指针partition的实现
    • 4.寻找第K个最小的数
    • 5.寻找前K个最小的数
    • 6.荷兰三色旗问题

    算法的IO解释:

    • 1.输入一个数组A,把数组A按枢轴(pivot)划分为两部分,左边小于等于枢轴,右边大于等于枢轴,枢轴在两者中间,但是左右两边不排序,并且返回枢轴的位置(下标).
      例如:[1,2,6,3,4,5] pivot =4 得到 [2,1,3,4,6,5] 下标:3
    • 2.与1一样,不过采用双指针扫描,时间复杂度更低。
    • 3.基于2实现快速排序
    • 4.输入一个数组,输出第K个最小的数,并对数组排序了(A[k-1]为第K个最小的数)
    • 5.输入一个数组,输出前K个最小的数,并对数组排序了(同上)
    • 6.输入一个数组,输出分界点pos_small和pos_big,pos_small左边全是小于target的值,pos_big右边全是大于target的值,两者之间的值等于target,并且数组被排序了。荷兰问题是6的子集中,即输入的数组值只有三种情况,代码完全不变。
    算法的实现如下,解释见注释
    # -*- coding: utf-8 -*-
    # @time :  2019/5/3  22:21
    # @Author: LSayhi
    # @github: https://github.com/LSayhi
    
    """1.一个指针实现划分函数"""
    def partition_OnePoint(array,begin,end):
        pivot = array[begin]#枢轴,可以取数组中任意一个位置的值,这里取第一个,方便说明
        pos = begin #记录分界点(其左边<=pivot,其右边>pivot)
    
        for i in range(begin+1,end):#从左到右遍历数组
            if array[i] <= pivot:#如果i处的值小于枢轴,则把pos向后移移一位
                pos += 1
                if pos != i:# 如果pos<i了(说明pos位置的值大于pivot),则把pos的值与i处的交换
                    temp = array[i]
                    array[i] = array[pos]
                    array[pos] = temp
    
        array[begin] = array[pos]
        array[pos] = pivot  #最后两行是交换pos处与pivot(begin处的值),把pivot放入中间,左边全部<=pivot,右边全部>pivot
        return pos
    
    """2.两个指针实现划分函数"""
    def partition_TwoPoint(array,begin,end):
        pivot = array[begin]#枢轴
    
        while begin < end:#两个指针begin、end
            while(begin < end and array[end] >= pivot):#end从右向左
                end -= 1 # 一直向左移,其它不动
            array[begin] = array[end] #当array[end]<= pivot,将其赋值给begin位置(即小的放左边去)
            while(begin < end and array[begin]<= pivot):
                begin += 1 #一直向右移
            array[end] = array[begin] #当array[begin]> pivot,将其赋值给end位置(即大的放右边去)
    
        pos = begin # 当begin == end,此时的位置即是pivot应放入的位置
        array[pos] = pivot
        return pos
    
    """3.快速排序 双指针版本"""
    def quickSort(array,begin,end):
        if begin>=end :#鲁棒性检测及递归推出
            return
        pos = partition_TwoPoint(array,begin,end)#找到划分点
        quickSort(array,begin,pos)#递归划分左边
        quickSort(array, pos + 1, end)#递归划分右边
    
    """4.寻找第K个小的数字"""
    def kth_Number(array,k):
        begin, end = 0, len(array)-1
        if not array or k<=0 or k > end +1:#鲁棒性检测
            return 0
        kth_num = 0
        while begin< end:
            pos = partition_TwoPoint(array,begin,end)#找到划分点
            if pos == k -1:#刚好是第K小的,则返回
                kth_num = array[pos]
                break
            elif pos > k -1:#说明第k小的在左边
                end = pos
            else:#说明第k小的在右边
                begin = pos + 1
        return kth_num
    
    """5.前K个小的数字"""
    def k_Number(array,k):
        begin, end = 0, len(array)-1
        if not array or k<=0 or k > end +1:
            return []
        k_numlst = []
        while begin< end:
            pos = partition_TwoPoint(array,begin,end)
            if pos == k -1:
                k_numlst = array[0:pos+1] #返回前k个数,其它与kth_number一样
                break
            elif pos > k -1:
                end = pos
            else:
                begin = pos + 1
        return k_numlst
    
    """6.三路划分,荷兰三色旗问题"""
    #根据partition算法改进为三路划分,左边小于target;右边大于target;中间等于target
    def threeway_partition(array,target):
        pos_small, pos_big = 0, len(array)-1
        pos = 0
        while pos <= pos_big:
            if array[pos] < target:
                array[pos],array[pos_small] = array[pos_small],array[pos] #swap
                pos += 1
                pos_small += 1
            elif array[pos] > target:
                array[pos],array[pos_big] = array[pos_big],array[pos] #swap
                pos_big -= 1
            else:
                pos += 1
        return pos_small, pos_big+1
    
    def main():#测试代码
        A = [5,9,2,1,4,7,8,3,6]
        B = [5,9,2,1,4,7,8,3,6]
        C = [5,9,2,1,4,7,8,3,6]
        D = [5,9,2,1,4,7,8,3,6]
        E = [5,9,2,1,4,7,8,3,6]
        F = [0,1,2,1,2,0,1,3,5]
        G = [0,2,2,1,1,0,0,2,1]
    
        a = partition_OnePoint(A,0,len(A)-1)
        b = partition_TwoPoint(B,0,len(B)-1)
        quickSort(C,0,len(C)-1)
        d = kth_Number(D,6)
        e = k_Number(E,6)
        f = threeway_partition(F,2)
        g = threeway_partition(G,1)
    
        print("A after partition_onepoint: " + "divide index =" + str(a), ", array =" + str(A))
        print("B after partition_twopoint: " + "divide index =" + str(b), ", array =" + str(B))
        print("C after quicsort: " + str(C))
        print("Found the kth_number in array D is "+ str(d))
        print("Found smallest k numbers in array E is " + str(e))
        print("F sorted:"+str(F)+",divide indexs:"+str(f)+",three parts:"+ str(F[:f[0]])+str(F[f[0]:f[1]])+str(F[f[1]:]))
        print("G sorted:"+str(G)+",three parts:"+str(G[:g[0]])+str(G[g[0]:g[1]])+str(G[g[1]:])+",Dutch Flag problem solved!")
    
    if __name__ == "__main__":
        main()
    

    测试代码运行结果:
    测试结果

    参考文献:
    https://www.cnblogs.com/zuilehongdou/p/6197716.html
    https://www.jianshu.com/p/583ae17759a8

    数据结构与算法(11):就到这里啦,感谢您的收藏与转发。

    更多精彩,可访问往期文章
    有任何疑问,欢迎后台留言,如果对文章内容有更深或独特的见解,欢迎#投稿#或者到github中PR。本文章所有代码及文档均以上传至github中,感谢您的rp,star and fork.

    github链接:https://github.com/LSayhi
    代码仓库链接:https://github.com/LSayhi/Algorithms

    CSDN链接:https://blog.csdn.net/LSayhi

    微信公众号:AI有点可ai

    AI有点可ai.jpg

    展开全文
  • int mid = partition(nums, left, right); while (mid != target) { if (mid < target) { left = mid + 1; mid = partition(nums, left, right); } else { right = mid - 1; mid = partition(nums, left...
  • Apriori算法: 几个概念: 项目集Item在数据集D上的支持度=包含Item的事务在D中所占的百分比 若项目集Item的支持度大于用户指定的最小支持度min_sup,则Item为频繁项目集。 support(Item) = P(Item)= |{T: Item∈T,T...

    Apriori算法:
    几个概念:

    项目集Item在数据集D上的支持度=包含Item的事务在D中所占的百分比
    若项目集Item的支持度大于用户指定的最小支持度min_sup,则Item为频繁项目集。
    support(Item) = P(Item)= |{T: Item∈T,T∈D}|/|D|×100%
    关联规则的支持度为
    support(X ∈Y) = support(X∪Y)
    关联规则的可信度为
    conf(X ∈Y) =support(X∪Y)/support(X)
    在D上满足最小支持度min-sup和最小可信度min-conf的关联规则称为强关联规则

    Apriori 性质
    如果项目集X是频繁项目集,则它的所有非空子集都是频繁项目集如{I1,I2}频繁,则{I1}频繁。
    如果项目集X不是频繁项目集,则它的所有超集都不是频繁项目集如{I1}不频繁,则{I1,I2}不频繁。
    Apriori算法的主要步骤:1.连接 2.剪枝 3.验证 4.回到1直到没有频繁集生成。

    示例如下:

    在这里插入图片描述

    在这里插入图片描述
    在这里插入图片描述
    Apriori算法存在的问题:多次扫描数据库,如果数据库庞大,算法效率会很低,可能会产生庞大的候选集。
    分区方法(Partition):
    1 如果一个项集X在站点Si上是局部频繁项,则X的所有子集在站点Si上也是局部频繁项。
    2 如果一个项集X是全局频繁项,则至少存在一个站点Si,X在Si上是局部频繁项
    在这里插入图片描述
    散列方法(Hash)
    每对项目最多只能放在一个特定的桶中,对每个桶中的项目子集进行测试,减少候选集生成的代价
    在这里插入图片描述
    在这里插入图片描述
    Hash结构的作用——减少比较次数
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    抽样方法(Sample)
    使用数据库中的一些抽样数据得到一些可能成立的规则,然后用数据库的剩余部分来验证这些规则是否成立。抽样数据的选取结果偏差问题(数据扭曲)
    Close算法——闭合的项集
    如果一个项目集的每个超集的支持度都小于它的支持度,则该项目集是闭合的。
    如果一个项集是频繁项集,而它的每个超集都不是频繁的,则该项集是最大的频繁项集。

    在这里插入图片描述
    Close算法的原理
    频繁(闭合)项目集的所有(闭合)子集一定是频繁的;
    非频繁(闭合)项目集的所有(闭合)超集一定是非频繁的。
    关键步骤:
    – 求产生式(连接、非频繁子集剪枝、利用闭合剪枝)
    – 求闭合(交易项集的交集,同时得出支持度)
    – 验证
    在这里插入图片描述
    在这里插入图片描述
    例如,最小支持数为2时
    FC1.gen={A,B,C,D,E}
    闭合项集:
    FC1.closure={A,B,C,BD,ABE}
    按照Apriori算法,将FC1.gen进行连接,得到
    FCC2 .gen= {AB,AC,AD,AE,BC,BD,BE,CD,CE,DE}
    利用FC1.closure对FCC2.gen剪枝:
    FC1.closure={A,B,C,BD,ABE}
    FCC2 .gen ={AB,AC,AD,BC,CD,CE,DE}
    FC2 .gen ={AB,AC, BC,BD}。
    ……
    最后求所有闭合的并集,再把并集的所有分解都加入集合中即为所有频繁项集

    Close算法的效率体现在:频繁闭合项目集通常比所有的频繁项目集少很多

    展开全文
  • 网络分析优化Graph Partition算法初探

    千次阅读 2011-11-26 21:50:38
    网络分析优化Graph Partition算法初探    By wangsh 2011-11-26   网络分析研究中,Graph Partition具有重要作用(参考1)。随着对最短路径算法研究的深入,研究者先使用Graph Partition方法标记弧段,之后...
                                          网络分析优化Graph Partition算法初探 
    

     

                                                By wangsh 2011-11-26

     

        网络分析研究中,Graph Partition具有重要作用(参考1)。随着对最短路径算法研究的深入,研究者先使用Graph Partition方法标记弧段,之后设计加速技术改进最短路径算法的效率(参考2)。
        目前使用比较广泛的Graph Partition软件包含metis(参考3)、Chaco(参考4)、Scotch(参考5)和jostle(参考6),本博文主要介绍metis处理数据格式及其使用。
        metis的使用方法。
         待后续补充完整。
     

     

    参考资料

    1.     Wiki网址 http://en.wikipedia.org/wiki/Graph_partition

    2.     Partitioning Graphs to Speed Up Dijkstra’s algorithm http://dl.acm.org/citation.cfm?id=1216585  

    3.     Metis网址 http://glaros.dtc.umn.edu/gkhome/views/metis

    4.     Chaco网址 http://www.sandia.gov/~bahendr/chaco.html

    5.     Scotch网址 http://www.labri.fr/perso/pelegrin/scotch/

    6.     jostle网址 http://staffweb.cms.gre.ac.uk/~c.walshaw/jostle/

    7.     其他工具网址 http://staffweb.cms.gre.ac.uk/~wc06/partition/

     

     

     

     

     

    版权所有,未经同意,请勿作他用,转载请注明:http://blog.csdn.net/wsh6759/article/details/7015526

     

     

     

     

     

     

     

     

     

     

     

    展开全文
  • partition算法 取数组中的一个数,将数组分成两部分(比它大和比它小),再接着在子问题中求解。这是一个常用的算法(以后还会补充)。 代码 #include <iostream> #include <string> #include <...

    问题描述

    主元素是一组n个数中出现次数大于n/2的数。
    求一个数组中的主元素。

    partition算法

    取数组中的一个数,将数组分成两部分(比它大和比它小),再接着在子问题中求解。这是一个常用的算法(以后还会补充)。

    代码

    #include <iostream>
    #include <string>
    #include <algorithm>
    using namespace std;
    
    int n;
    
    int mode(int * array,int l,int r,int n){
        if(l>=r)	return array[l];
        int i = l;
        int j = r;
        int m = (l+r)/2;
        int c = 0;
        int pivot = array[m];
    
        while(i < j){
            while(i<j && array[i]<pivot){
                i++;
            }
            while(i<j && array[j]>pivot){
                --j;
            }
            if(i<j){
                if(array[i]==pivot)	++c;
                if(array[j]==pivot)	++c;
                swap(array[i],array[j]);
                ++i;
                --j;            
                }
            }
            if(i == j && array[j] == pivot)
    			++c;//pivot出现次数加1 
            if(i == j && array[j]>pivot){
                --j; 
            }
            if(c >= n/2)	return pivot;
            if(j-l+1>=n/2)  //小于pivot的个数大于等于一半,在左半部分找 
    			return mode(array,l,j,n);
            return mode(array,j+1,r,n);//在右半部分找 
    }
    
    int main(){
    
        int *a;
        cin>>n;
        a = new int[n+1];
    
        for(int i = 0 ; i < n ; i++)
            cin>>a[i];
    
        cout<<mode(a , 0 , n-1 , n)<<endl;
        delete []a;
    	return 0; 
    }
    
    /*
    6
    1 2 2 2 3 2
    */
    
    展开全文
  • int partition(int *array, int start, int end) { int i, spec; int change_pos = start; /* we treat first number as pivot */ spec = array[start]; for(i = start+1; i < end; i++) { /* compare */...
  • STL partition分割算法

    2018-12-12 09:44:10
    这就是 partition() 算法所做的事。 partition 的前两个参数是定义被分区序列范围的正向迭代器,第三个参数是一个谓词。下面展示如何使用 partition() 来重新排列序列中的值,所有小于平均值的元素会被放在所有大于...
  • 分区排序partition sort 算法分区排序partition sort 算法的完整源码(定义,实现,main函数测试) 分区排序partition sort 算法的完整源码(定义,实现,main函数测试) #include <stdio.h> #include <...
  • 一个比较优美的partition算法的写法

    千次阅读 2010-09-03 16:57:00
    private int partition(long[] array, int lo, int hi) { long x = array[hi]; int i = lo - 1; for (int j = lo; j ; j++) { if (array[j] ) { i++; swap(array, i, j);
  • 划分(partition)算法

    千次阅读 2018-06-28 09:44:01
    quicksort中的快速划分 快速排序quicksort的核心是对无序向量进行...算法思想: 1. 取一元素为轴点(pivot),不妨取首元素为轴点,并将轴点的值备份; 2. 从向量的起始(low)和末尾(high)同时进行扫描; 3. 若nums...
  • 算法C语言快速排序

    2021-04-13 14:21:24
    算法C语言快速排序 int partition(int a[],int left,int right){ int first=left; int last=right; int key=a[first];//设置关键数字 if(left>=right) return 0; while(first<last){ //从右往左...
  • 算法+图像处理】2D卷积与快速卷积算法C语言实现

    千次阅读 热门讨论 2017-10-29 14:52:42
    卷积算法在图像处理中有着广泛的应用,通常使用的去噪算法、边缘增强算法等的实现都使用到了2D卷积算法。这里介绍一下2D卷积算法和快速卷积算法C语言实现。
  • 快速排序算法C语言

    2016-07-18 15:53:33
    快速排序算法,附带加快理解快速排序算法思想的视频链接,建议先看视频,再看代码
  • QuickSort 快速排序算法 c语言实现  UicKSort 快速排序算法 ... QUicKSort 快速排序算法 c实现 这里说明一下对QUicKSort的一些看法。 QuicKSort算法是一个分治算法,能够改进的地方就是如何对数据的划
  • //严蔚敏数据结构快速排序算法c语言实现#includetypedef int InfoType; /* 定义其它数据项的类型 *//* c10-1.h 待排记录的数据类型 */#define MAXSIZE 20 /* 一个用作示例的小顺序表的最大长度 */typedef int Key...
  • partition_copy() 算法以和 stable_partition() 相同的方式对序列进行分区,但那些使谓词返回 true 的元素会被复制到一个单独的序列中,使谓词返回 false 的那些元素会被复制到第三个序列中。这个操作不会改变原始...
  • 可以用 partition_point() 算法来获取分区序列中第一个分区的结束迭代器,它的前两个参数定义检查范围的正向迭代器,最后一个参数是用来对序列进行分区的谓词。我们通常不知道每个分区中元素的个数,这个算法使我们...
  • leetcode 561. Array Partition I C语言解析与代码
  • JavaScript实现integerPartition整数划分算法(附完整源码)integerPartition.js完整源代码 integerPartition.js完整源代码 export default function integerPartition(number) { const partitionMatrix = Array...
  • 排序算法c语言描述---快速排序

    千次阅读 多人点赞 2013-08-14 18:15:38
    排序算法系列学习,主要描述冒泡排序,选择排序,直接插入排序,希尔排序,堆排序,归并排序,快速排序等排序进行分析。 文章规划: 一。通过自己对排序算法本身的理解,对每个方法写个小测试程序。 具体思路分析...
  • C++ 贪心算法例题 set partition 数组拆分 题目描述: Given n integers {an}​\{a_n\}​{an​}​. Your task is to divide them into some subsets, each of which has consecutive integers. Let the number of ...
  • int Partition(int A[],int low,int high) { int p=A[low]; while(low<high){ while(low<high&&A[high]>p) high--; A[low]=A[high]; while(low<high&&A[low]<p) low++; A...
  • //严蔚敏数据结构快速排序算法c语言实现 #include typedef int InfoType; /* 定义其它数据项的类型 */ /* c10-1.h 待排记录的数据类型 */ #define MAXSIZE 20 /* 一个用作示例的小顺序表的最大长度 */ typedef int ...
  • 简单的K-means算法C语言实现代码

    万次阅读 2016-05-29 21:43:35
    K-means算法是很典型的基于距离的聚类算法,采用距离作为相似性的评价指标,即认为两个对象的距离越近,其相似度就越大。该算法认为簇是由距离靠近的对象组成的,因此把得到紧凑且独立的簇作为最终目标。 ...
  • C语言实现数组快速排序算法 快速排序算法,顾名思义,是迄今为止发现的速度最快的排序算法。快速排序算法采用分治的思想,首先在要排序的序列{5,8,7,6,4,3,9}中选取一个基准数(一般选取序列的第一个,其实选取哪个是...
  • 将[First, Last)区间中令_Pred(elem)为true的元素向前移动 返回令_Pred为false的第一个元素位置. 将[First, Last)区间中令_Pred(elem)为true的元素向前移动 返回令_Pred为false的第一个...复杂度:partition():线性...
  •  头文件 'partition_point.hpp'包含单个算法partition_point的两种变体。假设给出一个划分好的序列以及一个谓词,该算法将找出序列中划分的位置;比如说,找出序列中的第一不满足谓词的元素 。(注释:比如说我们给...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 40,971
精华内容 16,388
关键字:

partition算法c