编程珠玑笔记(13)-排序

插入排序
  直观的插入排序isort1:

  for i = [1, n)
      for (j=i; j > 0 && x[j-1] > x[j]; j--)
          swap(j-1, j)

  将swap展开后得到isort2,展开代码为:

  t = x[j] ;  x[j] = x[j-1];  x[j-1] = t

  考虑到t总是被赋予同样的值,将其挪到循环外面得到isort3:

  for i = [1, n)
      t = x[j]
      for (j = i; j > 0 && x[j-1] > t; j--)
          x[j] = x[j-1]
      x[j] = t

因为内循环最后一次执行x[j] = x[j-1] 后又执行了j–,所以此时的j就是彼时的j-1。
  以上三种排序算法的运行时间各自为:

程序 代码行数 纳秒(ns)
isort1 3 11.9n2
isort2 5 3.8n2
isort3 5 3.2n2

简单的快速排序
  快速排序算法于1962年发表,其中用到了分治法:将数组分成两个小部分,然后对它们递归排序。
  简单的快速排序围绕数组的第一个元素进行划分。

  void qsort1(l, u)
      if (l >= u)
          return
      m = l
      for i = [l+1, u]
          /* invariant: x[l+1..m] < x[l] &&
                        x[m+1..i-1] >= x[l] */
          if (x[i] < x[l])
              swap(++m, i)
      swap(l, m)
      qsort1(l, m-1)
      qsort1(m+1, u)

  利用x[l]作为哨兵可以减少比较的次数,从而得到改进的qsort2。主循环改为下面的代码可以去掉主循环之后的swap操作:

  m = u+1
  for (i = u; i >= l; i--)
      if x[i] >= t
           swap(--m, i)

改为while循环则还可以省去内循环中的一次测试:

  m = i = u+1
  do
      while x[--i] < t
          ;
      swap(--m, i)
  while i != l

更好的快速排序
  对于n个相同元素的数组,qsort1函数的性能很差。改进的函数qsort3可以解决这个问题,找到划分值t后,从左右两端同时向中间扫描,分别以i和j标记下标。对元素相同的情况,会停止扫描,交换i和j指向的元素的值。这样虽然使交换次数增加了,但却改进了最坏情况的时间复杂度。

  void qsort3(l, u)
      if l >= u
          return
      t = x[l]; i = l; j = u+1
      loop
          do i++ while i <= u && x[i] < t
          do j-- while x[j] > t
          if i > j
              break
          swap(i, j)
      swap(l, j)
      qsort3(l, j-1)
      qsort3(j+1, u)

  进一步优化的代码qsort4主要改进了两点。一是保证随机选取划分值;二是借助于插入排序,在将数组划分为足够小的子数组后就返回,最后调用插入排序完成最后的排序。这样做排序算法的速度得到了进一步提高。

  void qsort4(l, u)
      if u - l < cutoff
          return
      swap(l, randint(l, u))
      t = x[l]; i = l; j = u+1
      loop
          do i++ while i <= u && x[i] < t
          do j-- while x[j] > t
          if i > j
              break
          temp = x[i]; x[i] = x[j]; x[j] = temp
      swap(l, j)
      qsort4(l, j-1)
      qsort4(j+1, u)

  调用下述代码完成一次排序:

  qsort4(0, n-1)
  isort3()

  几种快速排序的效率:

程序 代码行数 纳秒(ns)
C库函数qsort 3 137n lgn
qsort1 9 60n lgn
qsort2 9 56n lgn
qsort3 14 44n lgn
qsort4 15+5 36n lgn
C++库函数sort 1 30n lgn

原理总结
  C语言中的qsort函数和C++库函数sort排序速度都很快。如果系统中的排序能够满足我们的需求,那么就不用考虑自己编写代码了。
  插入排序的代码很容易编写,且对于小型的排序任务速度很快。
  
  借用快速排序的思想,可以在O(n)的时间内找出数组中第k个最小的元素。

发表评论

电子邮件地址不会被公开。 必填项已用*标注