精华内容
下载资源
问答
  • 针对短文本特征极度稀疏、上下文依赖性强等特点,以自顶向下的策略,提出一种基于核心词项平均划分相似度的短文本聚类算法CTMPS。该方法首先在整个短文本语料库中计算词项之间的概率相关性,以此为基础对短文本中词项...
  • css技巧:table-cell的自动平均划分元素 在进入正题之前,我们先来热热身。利用你所会的css,实现如下图宽度相等的水平排列元素。 你可能已经想到了最直接的方法,定义5个div,定义相同的width、height,再让他们水平...

    css技巧:table-cell的自动平均划分元素

    在进入正题之前,我们先来热热身。利用你所会的css,实现如下图宽度相等的水平排列元素。

    在这里插入图片描述

    你可能已经想到了最直接的方法,定义5个div,定义相同的width、height,再让他们水平排列。

    至于怎么水平排列,方法很多,我是用的flex:

     <div class="flex-box">
            <div>1</div>
            <div>2</div>
            <div>3</div>
            <div>4</div>
            <div>5</div>
      </div>
    
    	*{
                padding:0;
                margin:0;
            }
        .flex-box{
            width:300px;
            display:flex;
            flex-direction:row;
        }
        .flex-box div{
            width:20%;
            height:30px;
            line-height: 30px;
            text-align: center;
            color:white;
        }
        .flex-box div:nth-child(1){
            background:red;
        }
        .flex-box div:nth-child(2){
            background:orange;
        }
        .flex-box div:nth-child(3){
            background:blue;
        }
        .flex-box div:nth-child(4){
            background:green;
        }
        .flex-box div:nth-child(5){
            background:purple;
        }
    

    效果截图:

    在这里插入图片描述

    有的朋友已经想到,可以直接用ul列表呀。

    这里,我们在上面的题的基础上加大一下难度,要求定义父元素的宽度固定,子元素自动均分宽度。没事嘛,我还是可以用ul啊,float一下,再计算一下每个li的宽度不就好了嘛。

    比如我是这样的:

    <ul id="ul-row">
            <li>1</li>
            <li>2</li>
            <li>3</li>
            <li>4</li>
            <li>5</li>
        </ul>
    
    *{
                padding:0;
                margin:0;
            }
            #ul-row{
                list-style-type: none;
            }
            #ul-row li{
                float:left;
                width:50px;
                height:30px;
                line-height:30px;
                text-align: center;
                color:white;
            }
            ul li:nth-child(1){
                background:red;
            }
            ul li:nth-child(2){
                background:orange;
            }
            ul li:nth-child(3){
                background:blue;
            }
            ul li:nth-child(4){
                background:green;
            }
            ul li:nth-child(5){
                background:purple;
            }
    

    效果截图:

    在这里插入图片描述

    除了上面的两个方法,机智的小伙伴已经想到啦,可以直接用table啊!!!直接排成一排,而且td自己平均划分,占满table元素。

    上代码:

     <table>
            <td>1</td>
            <td>2</td>
            <td>3</td>
            <td>4</td>
            <td>5</td>
        </table>
    
        *{
                padding:0;
                margin:0;
            }
        table{
            width:300px;
            border-collapse: collapse;/*注意清除td元素间的间距哦*/
        }
        td{
            height:30px;
            line-height:30px;
            text-align: center;
            color:white;
        }
        table td:nth-child(1){
            background:red;
        }
        table td:nth-child(2){
            background:orange;
        }
        table td:nth-child(3){
            background:yellow;
        }
        table td:nth-child(4){
            background:green;
        }
        table td:nth-child(5){
            background:blue;
        }
    

    效果截图:

    在这里插入图片描述

    差不多了,是时候上出今天的大招,那就是我们的题目上写道的:使用table-cell自动平均划分元素!

    先来讲讲它的实现原理吧!原理就是:

    当父元素定义“display:table”而子元素定义“display:table-cell”时,如果给父元素
    一定的宽度,父元素宽度就会根据子元素的个数进行自动平均划分。

    其实和最后一个方法很相似,只不过是用display将元素变形成table,table-cell了,但我们不用定义table,td元素了,是不是又感觉get了一个新的知识点。好了,不废话了,一起看看代码是如何实现的吧:

    <ul>
            <li>1</li>
            <li>2</li>
            <li>3</li>
            <li>4</li>
            <li>5</li>
        </ul>
    
            *{
                padding:0;
                margin:0;
            }
            ul{
                list-style-type: none;
                display:table;/*注意是table,不是table-row*/
                width:300px;
            }
            li{
               display:table-cell;
               height:30px;
               line-height:30px;
               text-align:center;/*使文本水平垂直居中*/
               color:white;
            }
            ul li:nth-child(1){
                background:red;
            }
            ul li:nth-child(2){
                background:orange;
            }
            ul li:nth-child(3){
                background:blue;
            }
            ul li:nth-child(4){
                background:green;
            }
            ul li:nth-child(5){
                background:purple;
            }
    

    效果截图:

    在这里插入图片描述

    怎么样?代码比上面的其他的方法都要简洁吧,而且,ul 元素宽度自动根据 li 元素个数进行平均划分,并不需要我们指定每一个 li 元素的宽度。是不是感觉又get了一个实用的css技巧了呢ε≡٩(๑>₃<)۶

    demo:https://github.com/yangyuqing123/css-auto-divided

    展开全文
  • 有时候我们在cdr软件里面绘制好一个圆形,想要把它平均划分为几等分的,比如三等分,怎么办呢?下面我们来看看吧!1、在cdr软件左侧的工具栏里面选择椭圆形工具,按住键盘上的ctrl键,在页面上绘制一个大圆2、使用...

    有时候我们在cdr软件里面绘制好一个圆形,想要把它平均划分为几等分的,比如三等分,怎么办呢?下面我们来看看吧!

    1、在cdr软件左侧的工具栏里面选择椭圆形工具,按住键盘上的ctrl键,在页面上绘制一个大圆

    2、使用鼠标单击一下大圆上方的“饼图”,页面上的图形即变成了如图所示的图形

    3、要把一个圆划分多少部分,最重要的就是在起始角度和结束角度栏设置好正确的角度数值

    4、一个圆为360°,那么三等分的,也就是一个圆的三分之一,有120°。设置起始角度0°,结束角度120°,再按下键盘上的enter键,即可以得到三分之一的圆

    5、通过ctrl+C,ctrl+V,复制一个三分之一的圆,然后把起始角度120°,结束角度240°,再按下键盘上的enter键,就可以得到第二部分的三分之一的圆了

    6、同样的,通过ctrl+C,ctrl+V,复制刚才制作出的三分之一的圆,然后把起始角度240°,结束角度360°,再按下键盘上的enter键,就可以得到最后一部分的三分之一的圆了

    7、再把鼠标在页面的空白位置单击一下,就可以得到一个完整的三等分的圆了。其他的几等分,只要计算好每部分的角度数值,按照这个办法,设置相应的起始角度和结束角度即可。

    教程结束,以上就是cdr怎样将一个圆形平均划分为三等分方法介绍,操作很简单的,大家学会了吗?希望能对大家有所帮助!

    展开全文
  • 快速排序 三平均划分

    2017-11-12 22:16:00
    一 原理 快速排序的基本思想如下: 对数组进行随机化。...如上图所示快速排序的一个重要步骤是对序列进行以中轴数进行划分,左边都小于这个中轴数,右边都大于该中轴数,然后对左右的子序列继续这一...

    一 原理

    Sorting_quicksort_anim

    快速排序的基本思想如下:

    1. 对数组进行随机化。
    2. 从数列中取出一个数作为中轴数(pivot)。
    3. 将比这个数大的数放到它的右边,小于或等于它的数放到它的左边。
    4. 再对左右区间重复第三步,直到各区间只有一个数。

    Basic Step of Quick Sort

    如上图所示快速排序的一个重要步骤是对序列进行以中轴数进行划分,左边都小于这个中轴数,右边都大于该中轴数,然后对左右的子序列继续这一步骤直到子序列长度为1。

    下面来看某一次划分的步骤,如下图:

    Partition trace in Quick Sort

    上图中的划分操作可以分为以下5个步骤:

    1. 获取中轴元素
    2. i从左至右扫描,如果小于基准元素,则i自增,否则记下a[i]
    3. j从右至左扫描,如果大于基准元素,则i自减,否则记下a[j]
    4. 交换a[i]和a[j]
    5. 重复这一步骤直至i和j交错,然后和基准元素比较,然后交换。

    划分过程的代码实现如下:

    /// <summary>
    /// 快速排序中的划分过程
    /// </summary>
    /// <param name="array">待划分的数组</param>
    /// <param name="lo">最左侧位置</param>
    /// <param name="hi">最右侧位置</param>
    /// <returns>中间元素位置</returns>
    private static int Partition(T[] array, int lo, int hi)
    {
        int i = lo, j = hi + 1;
        while (true)
        {
            //从左至右扫描,如果碰到比基准元素array[lo]小,则该元素已经位于正确的分区,i自增,继续比较i+1;
            //否则,退出循环,准备交换
            while (array[++i].CompareTo(array[lo]) < 0)
            {
                //如果扫描到了最右端,退出循环
                if (i == hi) break;
            }
    
            //从右自左扫描,如果碰到比基准元素array[lo]大,则该元素已经位于正确的分区,j自减,继续比较j-1
            //否则,退出循环,准备交换
            while (array[--j].CompareTo(array[lo]) > 0)
            {
                //如果扫描到了最左端,退出循环
                if (j == lo) break;
            }
    
            //如果相遇,退出循环
            if (i >= j) break;
    
            //交换左a[i],a[j]右两个元素,交换完后他们都位于正确的分区
            Swap(array, i, j);
        }
        //经过相遇后,最后一次a[i]和a[j]的交换
        //a[j]比a[lo]小,a[i]比a[lo]大,所以将基准元素与a[j]交换
        Swap(array, lo, j);
        //返回扫描相遇的位置点
        return j;
    }

    划分前后,元素在序列中的分布如下图:

    before and after partition

    二 实现

    与合并算法基于合并这一过程一样,快速排序基于分割(Partition)这一过程。只需要递归调用Partition这一操作,每一次以Partition返回的元素位置来划分为左右两个子序列,然后继续这一过程直到子序列长度为1,代码的实现如下:

    public class QuickSort<T> where T : IComparable<T>
    {
        public static void Sort(T[] array)
        {
            Sort(array, 0, array.Length - 1);
        }
    
        private static void Sort(T[] array, int lo, int hi)
        {
            //如果子序列为1,则直接返回
            if (lo >= hi) return;
            //划分,划分完成之后,分为左右序列,左边所有元素小于array[index],右边所有元素大于array[index]
            int index = Partition(array, lo, hi);
    
           //对左右子序列进行排序完成之后,整个序列就有序了
            //对左边序列进行递归排序
            Sort(array, lo, index - 1);
            //对右边序列进行递归排序
            Sort(array, index + 1, hi);
        }
    }

    下图说明了快速排序中,每一次划分之后的结果:

    the two part sorted

    一般快速排序的动画如下:

    quicksort

    三 分析

    1. 在最好的情况下,快速排序只需要大约nlgn次比较操作,在最坏的情况下需要大约1/2 n次比较操作。

      在最好的情况下,每次的划分都会恰好从中间将序列划分开来,那么只需要lgn次划分即可划分完成,是一个标准的分治算法Cn=2Cn/2+N,每一次划分都需要比较N次,大家可以回想下我们是如何证明合并排序的时间复杂度的。

      the compare complexity in  quick sort at the bese case

      在最坏的情况下,即序列已经排好序的情况下,每次划分都恰好把数组划分成了0,n两部分,那么需要n次划分,但是比较的次数则变成了n, n-1, n-2,….1, 所以整个比较次数约为n(n-1)/2~n2/2.

      the compare complexity in  quick sort at the worst case

    2. 快速排序平均需要大约2NlnN次比较,来对长度为n的排序关键字唯一的序列进行排序。 证明也比较简单:假设CN为快速排序平均花在比较上的时间,初始C0=C1=0,对于N>1的情况,有:

      image

      其中N+1是分割时的比较次数,image 表示将序列分割为0,和N-1左右两部分的概率为1/N, 划分为1,N-2左右两部分的概率也为1/N,都是等概率的。

      然后对上式左右两边同时乘以N,整理得到:

      image

      然后,对于N为N-1的情况:

      image

      两式相减,然后整理得到:

      image

      然后左右两边同时除以N(N+1),得到:

      image

      可以看到,这是一个递归式,我们将image 递归展开得到:

      image

      然后处理一下得到:

      image

    3. 平均情况下,快速排序需要大约1.39NlgN次比较,这比合并排序多了39%的比较,但是由于涉及了较少的数据交换和移动操作,他要比合并排序更快。
    4. 为了避免出现最坏的情况,导致序列划分不均,我们可以首先对序列进行随机化排列然后再进行排序就可以避免这一情况的出现。
    5. 快速排序是一种就地(in-place)排序算法。在分割操作中只需要常数个额外的空间。在递归中,也只需要对数个额外空间。
    6. 另外,快速排序是非稳定性排序。

    Quick Sort is not Stable

    四 改进

    对一般快速排序进行一些改进可以提高其效率。

    1. 当划分到较小的子序列时,通常可以使用插入排序替代快速排序

    对于较小的子序列(通常序列元素个数为10个左右),我们就可以采用插入排序直接进行排序而不用继续递归,算法改造如下:

    private const int CUTTOFF = 10;
    private static void Sort(T[] array, int lo, int hi)
    {
        //如果子序列为1,则直接返回
        if (lo >= hi) return;
        //对于小序列,直接采用插入排序替代
        if (hi - lo <= CUTTOFF - 1) 
        {
            Sort<int>.InsertionSort(array, lo, hi);
            return;
        }
        //划分,划分完成之后,分为左右序列,左边所有元素小于array[index],右边所有元素大于array[index]
        int index = Partition(array, lo, hi);
    
        //对左右子序列进行排序完成之后,整个序列就有序了
    
        //对左边序列进行递归排序
        Sort(array, lo, index - 1);
        //对右边序列进行递归排序
        Sort(array, index + 1, hi);
    }

    2. 三平均分区法(Median of three partitioning)

    在一般的的快速排序中,选择的是第一个元素作为中轴(pivot),这会出现某些分区严重不均的极端情况,比如划分为了1和n-1两个序列,从而导致出现最坏的情况。三平均分区法与一般的快速排序方法不同,它并不是选择待排数组的第一个数作为中轴,而是选用待排数组最左边、最右边和最中间的三个元素的中间值作为中轴。这一改进对于原来的快速排序算法来说,主要有两点优势:

    (1) 首先,它使得最坏情况发生的几率减小了。

    (2) 其次,未改进的快速排序算法为了防止比较时数组越界,在最后要设置一个哨点。如果在分区排序时,中间的这个元素(也即中轴)是与最右边数过来第二个元素进行交换的话,那么就可以省略与这一哨点值的比较。

    对于三平均分区法还可以进一步扩展,在选取中轴值时,可以从由左中右三个中选取扩大到五个元素中或者更多元素中选取,一般的,会有(2t+1)平均分区法(median-of-(2t+1)。常用的一个改进是,当序列元素小于某个阈值N时,采用三平均分区,当大于时采用5平均分区。

    采用三平均分区法对快速排序的改进如下:

    private static void Sort(T[] array, int lo, int hi)
    {
        //对于小序列,直接采用插入排序替代
        if (hi - lo <= CUTTOFF - 1) 
        {
            //Sort<int>.InsertionSort(array, lo, hi);
            return;
        }
        //采用三平均分区法查找中轴
        int m = MedianOf3(array, lo, lo + (hi - lo) / 2, hi);
        Swap(array, lo, m);
        //划分,划分完成之后,分为左右序列,左边所有元素小于array[index],右边所有元素大于array[index]
        int index = Partition(array, lo, hi);
    
        //对左右子序列进行排序完成之后,整个序列就有序了
    
        //对左边序列进行递归排序
        Sort(array, lo, index - 1);
        //对右边序列进行递归排序
        Sort(array, index + 1, hi);
    }
    
    /// <summary>
    /// 查找三个元素中位于中间的那个元素
    /// </summary>
    /// <param name="array"></param>
    /// <param name="lo"></param>
    /// <param name="center"></param>
    /// <param name="hi"></param>
    /// <returns></returns>
    private static int MedianOf3(T[] array, int lo, int center, int hi)
    {
        return (Less(array[lo], array[center]) ?
               (Less(array[center], array[hi]) ? center : Less(array[lo], array[hi]) ? hi : lo) :
               (Less(array[hi], array[center]) ? center : Less(array[hi], array[lo]) ? hi : lo));
    }
    
    private static bool Less(T t1, T t2)
    {
        return t1.CompareTo(t2) < 0;
    }

    使用插入排序对小序列进行排序以及使用三平均分区法对一般快速排序进行改进后运行结果示意图如下:

    Improvement using Insertsort and 3 mediation partition

    3. 三分区(3-way partitioning) 快速排序

    通常,我们的待排序的序列关键字中会有很多重复的值,比如我们想对所有的学生按照年龄进行排序,按照性别进行排序等,这样每一类别中会有很多的重复的值。理论上,这些重复的值只需要处理一次就行了。但是一般的快速排序会递归进行划分,因为一般的快速排序只是将序列划分为了两部分,小于或者大于等于这两部分。

    既然要利用连续、相等的元素不需要再参与排序这个事实,一个直接的想法就是通过划分让相等的元素连续地摆放:

     3-way partition quick sort

    然后只对左侧小于V的序列和右侧大于V对的序列进行排序。这种三路划分与计算机科学中无处不在,它与Dijkstra提出的“荷兰国旗问题”(The Dutch National Flag Problem)非常相似。

    Dijkstra的方法如上图:

    从左至右扫描数组,维护一个指针lt使得[lo…lt-1]中的元素都比v小,一个指针gt使得所有[gt+1….hi]的元素都大于v,以及一个指针i,使得所有[lt…i-1]的元素都和v相等。元素[i…gt]之间是还没有处理到的元素,i从lo开始,从左至右开始扫描:

    · 如果a[i]<v: 交换a[lt]和a[i],lt和i自增

    · 如果a[i]>v:交换a[i]和a[gt], gt自减

    · 如果a[i]=v: i自增

    下面是使用Dijkstra的三分区快速排序代码:

    private static void Sort(T[] array, int lo, int hi)
    {
        //对于小序列,直接采用插入排序替代
        if (hi - lo <= CUTTOFF - 1)
        {
            Sort<int>.InsertionSort(array, lo, hi);
            return;
        }
        //三分区
        int lt = lo, i = lo + 1, gt = hi;
        T v = array[lo];
        while (i<=gt)
        {
            int cmp = array[i].CompareTo(v);
            if (cmp < 0) Swap(array, lt++, i++);
            else if (cmp > 0) Swap(array, i, gt--);
            else i++;
        }
    
        //对左边序列进行递归排序
        Sort(array, lo, lt - 1);
        //对右边序列进行递归排序
        Sort(array, gt + 1, hi);
    }

    三分区快速排序的每一步如下图所示:

    3-way partitioning trace

    三分区快速排序的示意图如下:

    3 way quick sort visual trace

    Dijkstra的三分区快速排序虽然在快速排序发现不久后就提出来了,但是对于序列中重复值不多的情况下,它比传统的2分区快速排序需要更多的交换次数。

    Bentley 和D. McIlroy在普通的三分区快速排序的基础上,对一般的快速排序进行了改进。在划分过程中,i遇到的与v相等的元素交换到最左边,j遇到的与v相等的元素交换到最右边,i与j相遇后再把数组两端与v相等的元素交换到中间

    Bentley  McIlroy 3 way partition 

    这个方法不能完全满足只扫描一次的要求,但它有两个好处:首先,如果数据中没有重复的值,那么该方法几乎没有额外的开销;其次,如果有重复值,那么这些重复的值不会参与下一趟排序,减少了无用的划分。

    下面是采用 Bentley&D. McIlroy 三分区快速排序的算法改进:

    private static void Sort(T[] array, int lo, int hi)
    {
        //对于小序列,直接采用插入排序替代
        if (hi - lo <= CUTTOFF - 1)
        {
            Sort<int>.InsertionSort(array, lo, hi);
            return;
        }
        // Bentley-McIlroy 3-way partitioning
        int i = lo, j = hi + 1;
        int p = lo, q = hi + 1;
        T v = array[lo];
        while (true)
        {
            while (Less(array[++i], v))
                if (i == hi) break;
            while (Less(v, array[--j]))
                if (j == lo) break;
    
            // pointers cross
            if (i == j && Equal(array[i], v))
                Swap(array, ++p, i);
            if (i >= j) break;
    
            Swap(array, i, j);
            if (Equal(array[i], v)) Swap(array, ++p, i);
            if (Equal(array[j], v)) Swap(array, --q, j);
        }
    
        //将相等的元素交换到中间
        i = j + 1;
        for (int k = lo; k <= p; k++) Swap(array, k, j--);
        for (int k = hi; k >= q; k--) Swap(array, k, i++);
    
        Sort(array, lo, j);
        Sort(array, i, hi);
    }

    三分区快速排序的动画如下:

    3wayquick sort

    4.并行化

    和前面讨论对合并排序的改进一样,对所有使用分治法解决问题的算法其实都可以进行并行化,快速排序的并行化改进我在之前的浅谈并发与并行这篇文章中已经有过介绍,这里不再赘述。

    五 .NET 中元素排序的内部实现

    快速排序作为一种优秀的排序算法,在很多编程语言的元素内部排序中均有实现,比如Java中对基本数据类型(primitive type)的排序,C++,Matlab,Python,FireFox JavaScript等语言中均将快速排序作为其内部元素排序的算法。同样.NET中亦是如此。

    .NET这种对List<T>数组元素进行排序是通过调用Sort方法实现的,其内部则又是通过Array.Sort实现,MSDN上说在.NET 4.0及之前的版本,Array.Sort采用的是快速排序,然而在.NET 4.5中,则对这一算法进行了改进,采用了名为Introspective sort 的算法,即保证在一般情况下达到最快排序速度,又能保证能够在出现最差情况是进行优化。他其实是一种混合算法:

    • 当待分区的元素个数小于16个时,采用插入排序
    • 当分区次数超过2*logN,N是输入数组的区间大小,则使用堆排序(Heapsort)
    • 否则,使用快速排序。

    有了Reflector这一神器,我们可以查看.NET中的ArraySort的具体实现:

    Array.Sort这一方法在mscorlib这一程序集中,具体的实现方法有分别针对泛型和普通类型的SortedGenericArray和SortedObjectArray,里面的实现大同小异,我们以SortedGenericArray这个类来作为例子看:

    ArraySort implementation in .NET_1

    首先要看的是Sort方法,其实现如下:

    ArraySort implementation in .NET_2

    该方法中,首先判断运行的.NET对的版本,如果是4.5及以上版本,则用IntrospectiveSort算法,否则采用限定深度的快速排序算法DepthLimitedQuickSort。先看IntrospectiveSort:

    ArraySort implementation in .NET_3

    该方法第一个元素为数组的最左边元素位置,第二个参数为最右边元素位置,第三个参数为2*log2N,继续看方法内部:

    ArraySort implementation in .NET_4

    可以看到,当num<=16时,如果元素个数为1,2,3,则直接调用SwapIfGreaterWithItem进行排序了。否则直接调用InsertSort进行插入排序。

    这里面也是一个循环,每循环一下depthLimit就减小1个,如果为0表示划分的次数超过了2logN,则直接调用基排序(HeapSort),这里面的划分方法PickPivortAndPartitin的实现如下:

    ArraySort implementation in .NET_5

    它其实是一个标准的三平均快速排序。可以看到在.NET 4.5中对Quick进行优化的部分主要是在元素个数比较少的时候采用选择插入,并且在递归深度超过2logN的时候,采用基排序。

    下面再来看下在.NET 4.0及以下平台下排序DepthLimitedQuickSort方法的实现:

    从名称中可以看出这是限定深度的快速排序,在第三个参数传进去的是0x20,也就是32。

    DepthLimitedQuickSort

    可以看到,当划分的次数大于固定的32次的时候,采用了基排序,其他的部分是普通的快速排序。

    六 总结

    由于快速排序在排序算法中具有排序速度快,而且是就地排序等优点,使得在许多编程语言的内部元素排序实现中采用的就是快速排序,本问首先介绍了一般的快速排序,分析了快速排序的时间复杂度,然后就分析了对快速排序的几点改进,包括对小序列采用插入排序替代,三平均划分,三分区划分等改进方法。最后介绍了.NET不同版本下的对元素内部排序的实现。

    快速排序很重要,希望本文对您了解快速排序有所帮助。

    本文转自莫水千流博客园博客,原文链接:http://www.cnblogs.com/zhoug2020/p/6780604.html,如需转载请自行联系原作者
    展开全文
  • int Median3(int lt, int rt) {//三平均划分法 int Middle = (lt + rt) / 2; if (sz[lt] > sz[Middle]) {//满足中间的要比左边的大 swap(sz[lt], sz[Middle]); } if (sz[lt] > sz[rt]) {//满足右边的要比左边的大 ...

    题目信息

    要求根据给定输入,按照课堂给定的快速排序算法进行排序,输出排序结果和median3的返回值。

    1 cutoff值为5,不足cutoff使用插入排序。
    2 输入、输出格式参见测试用例。

    测试样例

    测试样例1

    41
    17
    34
    0
    19
    #
    
    After Sorting:
    0 17 19 34 41 
    Median3 Value:
    none
    

    测试样例2

    61
    59
    82
    -10
    31
    -2
    -3
    10
    2
    108
    12
    80
    -21
    127
    12
    #
    
    After Sorting:
    -21 -10 -3 -2 2 10 12 12 31 59 61 80 82 108 127 
    Median3 Value:
    12 -3 61 
    

    解答

    #include<iostream>
    #include<algorithm>
    
    using namespace std;
    
    int sz[100], median[100];
    int mNum = 0;
    
    int Median3(int lt, int rt)
    {//三平均划分法
        int Middle = (lt + rt) / 2;
        if (sz[lt] > sz[Middle])
        {//满足中间的要比左边的大
            swap(sz[lt], sz[Middle]);
        }
        if (sz[lt] > sz[rt])
        {//满足右边的要比左边的大
            swap(sz[lt], sz[rt]);
        }
        if (sz[Middle] > sz[rt])
        {//满足右边的比中间的大
            swap(sz[Middle], sz[rt]);
        }
        swap(sz[Middle], sz[rt - 1]);//将中间的放置在倒数第二个的位置
        median[mNum++] = sz[rt - 1];//将中间值存在median数组中
        return sz[rt - 1];
    }//实际上是我们抓取了三个数,第一个中间的最后一个按照大小排序后,取出中间的那个
    
    void InsertSort(int lt, int rt)
    {
        for (int i = lt + 1; i <= rt; i++)
        {
            int temp = sz[i];
            if (sz[i] < sz[i - 1])
            {
                int j = lt;
                while (sz[j] < temp)
                {
                    j++;
                }
                for (int k = i; k > j; k--)
                {//后移
                    sz[k] = sz[k - 1];
                }
                sz[j] = temp;
            }
        }
    }
    
    void QuickSort(int lt, int rt)
    {
        if (rt - lt < 5)
        {//个数小于5的时候使用插入排序的方法
            InsertSort(lt, rt);
        }
        else if (lt < rt)
        {
            int pivot = Median3(lt, rt);//得到了中间的那个数
            int L = lt, R = rt - 1; //从左到右的扫描从第一个元素开始,从右到左的扫描从倒数第二个元素开始
            while (L < R)
            {//找到左边的比中数大,右边的比中数小,然后交换之
                while (L < R && sz[++L] < pivot);
                while (L < R && sz[--R] > pivot);
                swap(sz[L], sz[R]);
            }
            swap(sz[L], sz[rt - 1]);//将中数放置在中间的位置
    
            int Middle = L; // 中轴
            if (Middle)
            {//递归下去
                QuickSort(lt, Middle - 1);
                QuickSort(Middle + 1, rt);
            }
        }
    }
    
    int main()
    {
        //freopen("/Users/zhj/Downloads/test.txt", "r", stdin);
        string s;
        int len = 0;
        while (true)
        {
            cin >> s;
            if (s[0] == '#')
            {
                break;
            }
            sz[len] = atoi(s.c_str());
            ++len;
        }
        QuickSort(0, len - 1);
    
        cout << "After Sorting:" << endl;
        for (int i = 0; i < len; ++i)
        {
            cout << sz[i] << " ";
        }
        cout << endl;
    
        cout << "Median3 Value:" << endl;
        if (len > 5)
        {
            for (int i = 0; i < mNum; ++i)
            {
                cout << median[i] << " ";
            }
        }
        else
        {
            cout << "none";
        }
        cout << endl;
    }
    

    想法

    1. 本题考察的就是快速排序的三平均划分法,实现一种分治的思想。
    2. 首先选出三个值,第一个数,中间的数,最后一个数,将这三个数按大小排好序,A < B < C
    3. 对剩余的数字,将小于B的数放置在左边,大于B的数放置在右边。
    4. 对左右两堆数实现递归,不断循环上述过程。
    5. 如果剩余的数小于等于5个的时候就是用插入排序的方式。
    展开全文
  • 平均分区法(Median of three partitioning) 在一般的的快速排序中,选择的是第一个元素作为中轴(pivot),这会出现某些分区严重不均的极端情况,比如划分为了1和n-1两个序列,从而导致出现最坏的情况。三平均分区法...
  • Knapsack在并行CI节点之间平均分配测试,以运行快速CI并节省您的时间。 背包宝石 knapsack_pro宝石 免费 ✓是 ✓是的, 常规模式-静态测试拆分 ✓是 ✓是 队列模式-动态测试拆分( ) 没有 ✓是 在并行CI节点之间...
  • <!DOCTYPE html> <html lang="en"> <head> ...meta charset="UTF-8">...根据平均分来划分等级</title> </head> <body> <script> // 得到小明同学的各科...
  • 基于平均坡印亭矢量的基本电振子远区划分分析
  • 划分大型网络的子网,不应该按建筑物,或者物理位置平均划分。 要按如下步骤:1、统计各个部分的主机数 2、按从多到少排列,然后从最多的主机数网络开始划分。 > 用户模式 # 特权模式 (config)#全局...
  • 算出总成绩/平均成绩按照等级划分(0~60:差)优良中差四个等级 计算变量 平均值计算同理 等级划分
  • 划分层次聚类 图示 基于层次的聚类方法 切割点选取 族间距离 概念 族间距离 使用到的变量 族间距离 最小距离 族间距离 最大距离 族间距离 中心点距离 族间距离 平均距离 基于层次聚类 ( 聚合层次聚类 ) 步骤 基于...
  • 2012年5月比特币价格I am trying to find out the top conferences that have the largest average number of citations in the last 5 years on the Internet but fail to find one. However, there are many ...
  • raid划分

    2020-07-01 23:01:13
    raid划分: raid0 至少两块: 平均存储信息,挂一块整个数据就崩溃,无法恢复,利用效率高。 raid1 至少2块: 数据盘互相备份,随便挂一个,不影响数据。资源利用率最低。 raid5 至少3块 数据分布式存放,坏一块磁盘,...
  •  printf("\n平均成绩是:%f\n",avg);  for(i=0;i;i++)  {   if(stu[i].score>avg)   stu[i].rank= 'A';   else   if(avg-stu[i].score)   stu[i].rank= 'B';   else   stu[i].rank= ...
  • 划分算法

    千次阅读 2008-04-16 10:51:00
    划分是快速排序的一个根本机制,在介绍快速排序之前,先了解一下划分划分数据就是把数据分为两组,使所有关键字大于特定值的数据项在一组,使...或者学校管理者想要把学生分成年级平均成绩高于60分和低于60分的两组
  • IP子网划分

    2020-08-05 10:59:52
    2.某单位分配一个B类地址,为130.25.0.0,该单位共6000台机器,平均分布在12个不同地点,写出子网掩码、每一个子网的网络地址、可使用的最大最小值,广播地址。 IP地址分类 A类:1.0.0.0-127.255.255.255/255.0.0.0...
  • 单次使用留出法得到的估计结果往往不够稳定可靠,在使用留出法时,一般要采用若干次随机划分、重复进行模型评估后取平均值作为留出法的评估结果。import random import csv import pandas as...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,355
精华内容 942
关键字:

平均划分