快速排序

快速排序：

采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。

分治法的基本思想是：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。

快速排序的基本思想

设当前待排序的无序区为R[low..high]，利用分治法可将快速排序的基本思想描述为：

（1）分解：

在R[low..high]中任选一个记录作为基准(Pivot)，以此基准将当前无序区划分为左、右两个较小的子区间R[low..pivotpos-1)和R[pivotpos+1..high]，并使左边子区间中所有记录的关键字均小于等于基准记录(不妨记为pivot)的关键字pivot.key，右边的子区间中所有记录的关键字均大于等于pivot.key，而基准记录pivot则位于正确的位置(pivotpos)上，它无须参加后续的排序。其中：low≤pivotpos≤high

（2）求解：

通过递归调用快速排序对左、右子区间R[low..pivotpos-1]和R[pivotpos+1..high]快速排序

Python实现

原理: 先用初始数据，然后对这个数据进行排序使左边的数据小于
该数据，右边的大于该数据，然后用递归的方法对两边的数据进行依次排序。

example1:

 1 from random import randint
 2 
 3 def qsort(a_list):
 4     ll = []        # Left list of pivot
 5     lr = []        # Right list of pivot
 6     if len(a_list) <= 1:
 7         return a_list
 8 
 9     for i in a_list[1:]:
10         if i < a_list[0]:        11             ll.append(i)
12         else:
13             lr.append(i)
14 
15     ll.append(a_list[0])
16 
17     sorted_list = qsort(ll) + qsort(lr)
18     return sorted_list
19 
20 alist = [randint(0, 100) for i in range(10)]
21 print 'alist before', alist
22 
23 blist = qsort(alist)
24 print 'alist after', blist

example2:

 1 from random import randint
 2 
 3 def qsort(alist):
 4     quick_sort(alist, 0, len(alist)-1)
 5     return alist
 6 
 7 
 8 def quick_sort(lst, l, r):
 9 
10     if l >= r:
11         return
12 
13     i = l
14     j = r
15     pivot = lst[i]
16 
17     while i < j:
18         while i < j and lst[j] >= pivot:
19             j -= 1
20         if i < j:
21             lst[i] = lst[j]
22             i += 1
23 
24         while i < j and lst[i] <= pivot:
25             i += 1
26         if i < j:
27             lst[j] = lst[i]
28             j -= 1
29 
30     lst[i] = pivot
31 
32     quick_sort(lst, l, i - 1)
33     quick_sort(lst, i + 1, r)
34 
35 
36 a_list = [randint(0, 100) for i in range(10)]
37 print qsort(a_list)

example3:

 1 def qsort(lst):
 2     quick_sort(lst, 0, len(lst) - 1)
 3     return lst
 4 
 5 
 6 def quick_sort(lst, begin, end):
 7 
 8     if begin >= end:
 9         return
10 
11     i = begin
12     pivot = lst[begin]
13 
14     for j in range(begin + 1, end + 1):
15         if lst[j] < pivot:
16             i += 1
17             lst[i], lst[j] = lst[j], lst[i]
18 
19     lst[begin], lst[i] = lst[i], lst[begin]
20 
21     quick_sort(lst, begin, i - 1)
22     quick_sort(lst, i + 1, end)
23 
24 
25 alst = [4, 34, 23, 78, 6, 2, 9] 
26 
27 print qsort(alst)