字符画之画排序

  1. Bubble Sort(冒泡排序)
  2. Selection Sort(选择排序)
  3. Insertion Sort(插入排序)
  4. Merge Sort(归并排序)
  5. Quick Sort(快速排序)
  6. Heap Sort(堆排序)
  7. Shell Sort(希尔排序)
  8. 排序对比

用字符“画”排序算法。

基本约定:

  • 排序的对象为一个数组array
  • 排序的范围为[lo,hi)
  • 同时排序的长度为hi-lo
  • array示意图如下:
               lo            hi
  array: -----[             ]-----
  方括号中的元素为排序区间

Bubble Sort(冒泡排序)

   实现:
    lo            hi
   [            ][          ]
    ------------  ----------
    待排序区间W   已排序区间S

    不断的遍历W,将最大值移到S的最左侧hi处;

   改进:
    lo            hi
   [     k      ][          ]
    ------------  ----------
    待排序区间W   已排序区间S

   不断的遍历W,即[lo,hi)区间,将最大值移到S的最左侧hi处,同时判断W的尾部是否有序;
   若W的[k,hi)已经有序,则下一次对[lo, hi=k)进行遍历;

Selection Sort(选择排序)

    lo            hi
   [    m       ][i          ]
    ------------  -----------
    待排序区间W   已排序区间S

    不断的从W中选出最大者m,放入S的第一个位置i处;

Insertion Sort(插入排序)

    lo            hi
   [       i    ][e          ]
    ------------  -----------
    已排序区间S   待排序区间W

   不断将W中第一个元素e,插入到S中位置i处;
   i为S中元素不大于e的最大元素的位置;

   (1) 基本形式:先search再insert;
   (2) 改进版:因为S是有序的,故从右向左遍历S,与e比较,若比e大,则右移;

Merge Sort(归并排序)

    lo             hi
   [              ]

   分:将排序区间分成左右两部分

   [      ][      ]
    ------  ------
      L       R

   合:同时遍历L和R,按大小依次插入到新区间S中

   [              ]
    --------------
    已排序区间S

    不断的递归,执行“分,合”,直至L、R中只有一个元素。

Quick Sort(快速排序)

    lo             hi
   [         p    ]
    --------- ----
        L       R
   基本原理:在数组中,随机选定元素p,使得 p左侧元素 <= p <= 右侧元素;
             不断的对L、R执行上述过程,直至L、R只有一个元素。

   将p称为轴点,轴点可选取范围为[lo, hi],与基本约定有所不同;
   轴点:左侧元素[lo, mi) <= 轴点元素mi <= 右侧元素(mi, hi]。

   根据轴点的确定过程,可知快速排序前后,可能打乱相同元素间的相对顺序;
   即快速排序是不稳定的。

   (1)基本实现
   [    ][i     j][    ]
    ----           ----
      L              R
   随机选取轴点p,将i和j与轴点p进行比较,从而将i和j不断的归入到L或R中;

   (2)变种实现
   [p][      q][i       ][k----------]
       -------  --------
          L        R
   随机选取轴点p,并对调至最左侧,不断的比较k和候选轴点p,
   p <= k : k归入R中;
   p > k  : k归入L中,即交换i和k,L的长度+1;
   最终交换p和q,q做为最终的轴点。

Heap Sort(堆排序)

       max --------->
      /              \
   [ # --- heap --- ][i             ]
    lo             hi
    ----------------  --------------
         堆区间H        已排序区间S

   不断地将堆顶元素(即最大值),放入S的最左侧i处(有点类似于选择排序)。

Shell Sort(希尔排序)

   (1) 希尔排序过程
   将整个序列视作一个矩阵,逐列各自排序w-sorting (w为矩阵列数)

   排序序列:  8 1 5 6 9 4 3 7 2
   步长序列: [1, 2, 3, 5]
   5-sorting : 8 1 5 6 9  =>  4 1 5 2 9  =>  4 1 5 2 9 8 3 7 6
               4 3 7 2        8 3 7 6

   3-sorting : 4 1 5  =>  2 1 5  =>  2 1 5 3 7 6 4 9 8
               2 9 8      3 7 6
               3 7 6      4 9 8

   2-sorting : 2 1  =>  2 1 => 2 1 4 3 5 6 7 9 8
               5 3      4 3
               7 6      5 6
               4 9      7 9
               8        8

   1-sorting : 1 2 3 4 5 6 7 8 9

   进行w-sort时,使用选择排序:
   因为开始的时候,w更大,列元素个数少,逆序对少,选择排序消耗少;
   等到后面的时候,w更小,列元素个数多,但逆序对少,选择排序消耗少;

   (2) 间隔有序
   h-ordered : 序列s[0,n)对于任何 0<= i < n-h,都有s[i] <= s[i+h];

   任一个序列进行h-sorting后,必定是h-ordered;
   若一个序列同时为g-ordered和g-ordered,则序列也为(mg+nh)-ordered,m和n为自然数;

排序对比

排序对比


转载请注明来源,欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 [ yehuohan@gmail.com ]

文章标题:字符画之画排序

本文作者:Yehuohanxing

发布时间:2018-01-11, 17:33:19

最后更新:2018-04-03, 23:26:42

原始链接:http://yehuohan.github.io/2018/01/11/笔记/字符画之画排序/

版权声明: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

目录