快速排序算法的实现及相关测试算法的原理与实现

   <h2><strong>快速排序简介</strong></h2>    <p>快速排序是一种分治的排序算法，是实践中最快的排序算法，理论上的时间复杂度为O(N*lgN)，最差情况的时间复杂度为O(N^2)，但稍加努力就可避免这种情况。</p>    <p>理论时间复杂度为O(N*lgN)还有堆排序、插入排序等，但这些算法因为需要动态的分配内存或合并内存，在实践中的性能不如快速排序。</p>    <p>快速排序的步骤</p>    <ol>     <li>如果列表中的元素为0或1个，则返回</li>     <li>选取标记值p</li>     <li>将列表分为两部分s1、s2，需满足条件：s1中的元素均小于或等于p，s2中的元素均大于等于p，得到s1+p+s2</li>     <li>对s1、s2重复2、3步骤，最终得到排序结果</li>    </ol>    <p>从上面的步骤可以看出，快速排序需要递归运算。</p>    <h2><strong>Python实现</strong></h2>    <p>采用三值取中间值的方法选取标记值，从而避免最差情况。</p>    <pre>  <code class="language-python">def median3(L,a,b,c):      if L[a] >= L[b] and L[b] >= L[c]:          mid = L[b]          i = b      elif L[a] <= L[b] and L[b] <= L[c]:          mid = L[b]          i = b      elif L[b] >= L[a] and L[a] >= L[c]:          mid = L[a]          i = a      elif L[b] <= L[a] and L[a] <= L[c]:          mid = L[a]          i = a      else:          mid = L[c]          i = c      return [mid,i]      def swap(L, i, j):      tmp = L[i]      L[i] = L[j]      L[j] = tmp    def quickSort(L, low, high):      if low < high:          i = low          j = high          meta = median3(L, i, (i+j)/2, j)          pivot = meta[0]          pivotPos = meta[1]          # move pivot to the right end          swap(L, pivotPos, high)             while i < j:              # pivot on the right end, starting from left              while i < j and L[i] <= pivot:                  i = i+1              while j > i and L[j] >= pivot:                  j = j-1              swap(L, i, j)          # move pivot to right position          swap(L, i, high)            quickSort(L, low, i-1)          quickSort(L, i+1, high)</code></pre>    <h2><strong>测试算法</strong></h2>    <p>测试排序结果是否正确，需满足条件</p>    <ol>     <li>列表除元素顺序变化外，没有别的变化</li>     <li>列表中的元素是有序的</li>    </ol>    <p>条件2容易实现，重点关注条件1</p>    <p>如何确保列表除元素顺序变化外，没有别的变化？</p>    <p>列表L1、L2满足以下三个条件即可</p>    <ol>     <li>L1、L2中的元素数量相同</li>     <li>L1、L2的元素组成的集合相同（L1中的元素都在L2中，反之也成立）</li>     <li>L1、L2中元素的和相同</li>    </ol>    <p>例如，列表L1=[2,3,2,2,3]，顺序打乱后得到L2=[2,2,3,3,2]，此时L1、L2满足以上三个条件。如果对L2进行以下操作，均会使其中的一个或多个条件不成立。</p>    <ul>     <li>添加/删除元素</li>     <li>修改元素值</li>    </ul>    <h2><strong>测试算法实现</strong></h2>    <pre>  <code class="language-python">import sys  import random  import copy    # condition 2  def diff2List(l1,l2):      diff = [val for val in l1 if val not in l2]      for v in [val for val in l2 if val not in l1]:          diff.append(v)      return diff    def isListSorted(L):      i = 0      while i < len(L) - 2:          if L[i] <= L[i+1]:              i = i+1          else:              return [i, L[i], L[i+1]]      return True    # condition 3  def sumList(L):      sum = 0      for i in L:          sum = sum + i      return sum    def randomList(length, maximum):      l = []      i = 0      while i < length:          l.append(random.randint(0, maximum))          i = i+1      return l    #  # Test usage: python <script_path> <test_times> <min_list_length> <max_list_length> <max_list_element_value>  #    testTimes = int(sys.argv[1])  minLength = int(sys.argv[2])  maxLength = int(sys.argv[3])  maxValue = int(sys.argv[4])    for i in range(testTimes):      L = randomList(random.randint(minLength, maxLength), maxValue)      print 'Test round #' + str(i)      # original      print L      # deep copy for test      tmpList = copy.deepcopy(L)      quickSort(L, 0, len(L) - 1)      if len(L) != len(tmpList) or diff2List(L, tmpList) != [] or sumList(L) != sumList(tmpList):          print 'Bad #not coherent'          break      else:          sorted = isListSorted(L)          if sorted != True:              print 'Bad #not sorted'              print sorted      # after sort      print L</code></pre>    <p> </p>    <p>来自：http://www.jianshu.com/p/0aef1e132b9b</p>    <p> </p>