Python实现排序（冒泡、快排、归并）

浏览数：22 / 时间：2015年06月08日

　　Thomas H.Cormen 的《算法导论》上介绍的几个经典排序算法的Python实现。

1、冒泡排序：

　　简单的两重循环遍历，使最小（最大）的值不断地往上升（下沉）而实现的排序，算法时间为O(n²)。

　　代码如下：

 1 def up_sort(a):
 2         # 冒泡排序
 3 
 4         a_length = len(a)
 5         while True:
 6                 i = 0
 7                 j = 1
 8 
 9                 while True:
10                         if a[i] > a[j]:
11                                 a[i], a[j] = a[j], a[i]
12                                 i += 1
13                                 j = i+1
14                         else:
15                             i += 1
16                             j = i+1
17                         if j >= a_length:
18                                 break
19                 a_length -= 1
20                 if a_length == 1:
21                         break

2、快速排序

　　快排是一种使用较多的一种排序算法，对于包含n个数输入数组，最坏情况运行时间为Θ(n²)，期望运行时间为Θ(nlgn),而且常数因子较小，不容易出现最坏情况，所以快排常是进行排序的最佳选择。

　　其主要包括三个步骤(对子数组A[p...r])：

　　分解:数组A[p...r]被划分成两个子数组A[p..q-1]和A[q+1..r],使得A[p..q-1]中的元素都小于等于A[q]，而A[q+1..r]中的都大于A[q]

　　解决：通过递归调用快排，对数组A[p..q-1]和A[q+1..r]进行排序

　　合并：因为两个子数组是就地排序的，将他们的合并不需要操作：整个数组A[p..r]已排序

代码如下：

　　为排序一个完整的数组A，需调用quicksort(A,0,len[A]-1),partition()函数就是对子数组进行就地重排.

def partition(a, p, r):
    x = a[r]
    i = p-1
    for j in range(p, r-1):
        if a[j] <= x:

           i += 1
           a[i], a[j] = a[j], a[i]
    a[i+1], a[r] = a[r], a[i+1]
    return i+1


def quicksort(a, p, r):
    ‘快排‘
    if p < r:
        q = partition(a, p, r)
        quicksort(a, p, q-1)
        quicksort(a, q+1, r)
        # print a

3、归并排序

　　归并排序是利用的分治的思想，讲一个要解决的问题划分为多个子问题，分别对每个子问题进行求解，算法直观的操作如下：

　　分解：将n个元素分解成各含n/2个元素的子序列；

　　解决：用合并排序法对两个子序列递归的排序

　　合并：合并两个已排序的子序列得到排序结果

代码如下：

归并排序的时间复杂度为Θ(nlgn)

 1 def merge_sort(a, p, r):
 2     ‘归并排序‘
 3     if p < r:
 4         q = (p+r)//2
 5         merge_sort(a, p, q)
 6         merge_sort(a, q+1, r)
 7 
 8         merge(a, p, q, r)
 9 
10 
11 def merge(a, p, q, r):
12     n1 = q - p + 1
13     n2 = r - q
14     left = []
15     right = []
16     for i1 in range(0, n1):
17         left.append(a[p+i1])
18     for j1 in range(0, n2):
19         right.append(a[q+j1+1])
20 
21     left.append(float(‘inf‘))
22     right.append(float(‘inf‘))
23     i = 0
24     j = 0
25     for k in range(p, r+1):
26         if left[i] <= right[j]:
27             a[k] = left[i]
28             i += 1
29         else:
30             a[k] = right[j]
31             j += 1

4、完整代码：

　　包括实验的测试代码如下：

  1 # -*- coding: utf-8 -*-
  2 
  3 # !/usr/bin/env python
  4 
  5 
  6 __author__ = ‘you‘
  7 
  8 import random
  9 import time
 10 
 11 
 12 def up_sort(a):
 13         # 冒泡排序
 14 
 15         a_length = len(a)
 16         while True:
 17                 i = 0
 18                 j = 1
 19 
 20                 while True:
 21                         if a[i] > a[j]:
 22                                 a[i], a[j] = a[j], a[i]
 23                                 i += 1
 24                                 j = i+1
 25                         else:
 26                             i += 1
 27                             j = i+1
 28                         if j >= a_length:
 29                                 break
 30                 a_length -= 1
 31                 if a_length == 1:
 32                         # print a
 33                         break
 34 
 35 
 36 def partition(a, p, r):
 37     x = a[r]
 38     i = p-1
 39     for j in range(p, r-1):
 40         if a[j] <= x:
 41 
 42            i += 1
 43            a[i], a[j] = a[j], a[i]
 44     a[i+1], a[r] = a[r], a[i+1]
 45     return i+1
 46 
 47 
 48 def quicksort(a, p, r):
 49     ‘快排‘
 50     if p < r:
 51         q = partition(a, p, r)
 52         quicksort(a, p, q-1)
 53         quicksort(a, q+1, r)
 54         # print a
 55 
 56 
 57 def merge(a, p, q, r):
 58     n1 = q - p + 1
 59     n2 = r - q
 60     left = []
 61     right = []
 62     for i1 in range(0, n1):
 63         left.append(a[p+i1])
 64     for j1 in range(0, n2):
 65         right.append(a[q+j1+1])
 66 
 67     left.append(float(‘inf‘))
 68     right.append(float(‘inf‘))
 69     i = 0
 70     j = 0
 71     for k in range(p, r+1):
 72         if left[i] <= right[j]:
 73             a[k] = left[i]
 74             i += 1
 75         else:
 76             a[k] = right[j]
 77             j += 1
 78 
 79 
 80 def merge_sort(a, p, r):
 81     ‘归并排序‘
 82     if p < r:
 83         q = (p+r)//2
 84         merge_sort(a, p, q)
 85         merge_sort(a, q+1, r)
 86 
 87         merge(a, p, q, r)
 88         # print a
 89 
 90 
 91 if __name__ == ‘__main__‘:
 92         in_len = int(raw_input(‘输入排序个数：‘))
 93         begin_num = int(raw_input(‘输入随机产生序列的范围：‘))
 94         end_num = int(raw_input())
 95 
 96         A = []
 97         for i in range(0, in_len):
 98             A.append(random.randrange(begin_num, end_num))
 99             # print(A)
100         while True:
101             print ‘-‘*10+‘算法性能比较‘+‘-‘*10
102             print ‘‘‘
103             1、冒泡排序
104             2、快排
105             3、归并排序
106             0、退出
107             ‘‘‘
108             print ‘-‘*30
109             select=int(raw_input(‘输入选择‘))
110             if select == 1:
111                 begin_time=time.time()
112 
113 
114                 up_sort(A)
115                 # print A
116                 end_time=time.time()
117             elif select == 0:
118                 break
119             elif select == 2:
120                 begin_time=time.time()
121                 quicksort(A, 0, len(A)-1)
122                 end_time=time.time()
123             else:
124                 begin_time=time.time()
125                 merge_sort(A, 0, len(A)-1)
126                 end_time=time.time()
127             print ‘该算法的耗时为:‘+str((end_time-begin_time)*1000)+‘ms‘