快速排序

quick_sort.py

#!/usr/bin/env python
# -*- #coding:utf-8
'''
Created on 2013-9-10

@author: mingdong.li
'''

def sort(arr, left, right):
    '''
    原地分区（in-place）
    平均空间复杂度：O(log n)
    平均时间复杂度：O(n log n)
    '''
    pivot = arr[(left + right) >> 1]
    l, r = left, right
    
    while l <= r:
        while arr[l] < pivot:
            l = l + 1
        while arr[r] > pivot:
            r = r - 1
        if l <= r:
            arr[l], arr[r] = arr[r], arr[l]
            l = l + 1
            r = r - 1
    if left < l-1:
        sort(arr, left, l-1)
    if l < right:
        sort(arr, l, right)

def quickSort(arr):
    if not (arr and isinstance(arr, list)):
        return "the arr is %s" % str(arr)
    
    left = 0
    right = len(arr)
    if left > right:
        return -1
    sort(arr, left, right-1)
    return arr

quick_sort2.py

def quickSort2(arr):
    if len(arr) < 1:
        return arr
    #pivot = arr.pop() # pivot is last element
    pivot = arr.pop(0) # pivot is first element
    left = [i for i in arr if i < pivot]
    right = [i for i in arr if i >= pivot]
    
    return quickSort2(left) + [pivot] + quickSort2(right)
    
def test():
    print quickSort2([1, 12, 5, 26, 7, 14, 3, 7, 2])
    
if __name__ == '__main__':
    test()

test_quick_sort.py

'''
Created on 2013-9-10

@author: mingdong.li
'''
import unittest
from sort_algorithm.quick_sort import quickSort

class TestQuickSort(unittest.TestCase):

    def template_test(self, test_list, test_result, method):
        for content, result in zip(test_list, test_result):
            self.assertEqual(method(content), result, msg="%s test failed, produced '%s', should've produced '%s'" % (method, result, method(content)))

    def testQuickSort(self):
        test_list = ((), [], {1212: '1'}, [1], [3, 2, 1], [1, 12, 5, 26, 7, 14, 3, 7, 2])
        test_result = ('the arr is ()', 'the arr is []', "the arr is {1212: '1'}", [1], [1, 2, 3], [1, 2, 3, 5, 7, 7, 12, 14, 26])
        self.template_test(test_list, test_result, quickSort)

if __name__ == "__main__":
    unittest.main()