Coding~

快速排序--python

快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。

该方法的基本思想是：

1．先从数列中取出一个数作为基准数。

2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。

3．再对左右区间重复第二步，直到各区间只有一个数。

其中Partion算法是算法的核心，可以从左右两端同时开始，这样快一些，示例图如下：

然后将选中的主元素放到中间：

算法代码如下：

    
    def quickSort(alist):
       quickSortHelper(alist,0,len(alist)-1)
      
    def quickSortHelper(alist,first,last):
       if first<last:
      
           splitpoint = partition(alist,first,last)
      
           quickSortHelper(alist,first,splitpoint-1)
           quickSortHelper(alist,splitpoint+1,last)
      
      
    def partition(alist,first,last):
       pivotvalue = alist[first]
      
       leftmark = first+1
       rightmark = last
      
       done = False
       while not done:
      
           while leftmark <= rightmark and \
                   alist[leftmark] <= pivotvalue:
               leftmark = leftmark + 1
      
           while alist[rightmark] >= pivotvalue and \
                   rightmark >= leftmark:
               rightmark = rightmark -1
      
           if rightmark < leftmark:
               done = True
           else:
               temp = alist[leftmark]
               alist[leftmark] = alist[rightmark]
               alist[rightmark] = temp
      
       temp = alist[first]
       alist[first] = alist[rightmark]
       alist[rightmark] = temp
      
      
       return rightmark
      
    alist = [54,26,93,17,77,31,44,55,20]
    quickSort(alist)
    print(alist)
blog comments powered by Disqus

Published

10 February 2014

Tags