add Sort python code

wuchong · wuchong · commit 3d548cc4521c · 2014-02-09T16:47:11.000+08:00
diff --git a/Sort/python/BubbleSort.py b/Sort/python/BubbleSort.py
@@ -0,0 +1,49 @@
+# -*- coding: utf-8 -*- 
+
+#---------------------------------------  
+#   程序：冒泡排序
+#   版本：0.1
+#   作者：WuChong
+#   日期：2014-01-28
+#   语言：Python 3.3 
+#   说明：冒泡排序，从小到大排序，以及加了两种优化
+#---------------------------------------
+
+def bubble_sort(arry):
+    n = len(arry)                   #获得数组的长度
+    for i in range(n):
+        for j in range(1,n-i):
+            if  arry[j-1] > arry[j] :       #如果前者比后者大
+                arry[j-1],arry[j] = arry[j],arry[j-1]       #则交换两者
+    return arry
+
+
+#优化1：某一趟遍历如果没有数据交换，则说明已经排好序了，因此不用再进行迭代了。
+#用一个标记记录这个状态即可。
+def bubble_sort2(arry):
+    n = len(arry)
+    for i in range(n):
+        flag = 1                    #标记
+        for j in range(1,n-i):
+            if  arry[j-1] > arry[j] :
+                arry[j-1],arry[j] = arry[j],arry[j-1]
+                flag = 0
+        if flag :                   #全排好序了，直接跳出
+            break
+    return arry
+
+#优化2：记录某次遍历时最后发生数据交换的位置，这个位置之后的数据显然已经有序了。
+# 因此通过记录最后发生数据交换的位置就可以确定下次循环的范围了。
+def bubble_sort3(arry):
+    n = len(arry)
+    k = n                           #k为循环的范围，初始值n
+    for i in range(n):
+        flag = 1
+        for j in range(1,k):        #只遍历到最后交换的位置即可
+            if  arry[j-1] > arry[j] :
+                arry[j-1],arry[j] = arry[j],arry[j-1]
+                k = j               #记录最后交换的位置
+                flag = 0
+        if flag :
+            break
+    return arry
diff --git a/Sort/python/HeapSort.py b/Sort/python/HeapSort.py
@@ -0,0 +1,36 @@
+# -*- coding: utf-8 -*- 
+
+#---------------------------------------  
+#   程序：堆排序
+#   版本：
+#   作者：WuChong
+#   日期：2014-02-09
+#   语言：Python 3.3 
+#   说明：
+#---------------------------------------
+
+def heap_sort(ary) :
+    n = len(ary)
+    first = int((n-2)/2)       #最后一个非叶子节点
+    for start in range(first,-1,-1) :     #构造大根堆
+        max_heapify(ary,start,n-1)
+    for end in range(n-1,0,-1):           #堆排，将大根堆转换成有序数组
+        ary[end],ary[0] = ary[0],ary[end]
+        max_heapify(ary,0,end-1)
+    return ary
+
+
+#最大堆调整：将堆的末端子节点作调整，使得子节点永远小于父节点
+#start为当前需要调整最大堆的位置，end为调整边界
+def max_heapify(ary,start,end):
+    root = start
+    while True :
+        child = root*2 +1               #调整节点的子节点
+        if child > end : break
+        if child+1 <= end and ary[child] < ary[child+1] :
+            child = child+1             #取较大的子节点
+        if ary[root] < ary[child] :     #较大的子节点成为父节点
+            ary[root],ary[child] = ary[child],ary[root]     #交换
+            root = child
+        else :
+            break
diff --git a/Sort/python/InsertionSort.py b/Sort/python/InsertionSort.py
@@ -0,0 +1,25 @@
+# -*- coding: utf-8 -*- 
+
+#---------------------------------------  
+#   程序：直接插入排序
+#   版本：0.1
+#   作者：WuChong
+#   日期：2014-01-29
+#   语言：Python 3.3 
+#   说明：  
+#---------------------------------------
+
+def insert_sort(ary):
+    n = len(ary)
+    for i in range(1,n):
+        if ary[i] < ary[i-1]:
+            temp = ary[i]
+            index = i           #待插入的下标
+            for j in range(i-1,-1,-1):  #从i-1 循环到 0 (包括0)
+                if ary[j] > temp :
+                    ary[j+1] = ary[j]
+                    index = j   #记录待插入下标
+                else :
+                    break
+            ary[index] = temp
+    return ary
diff --git a/Sort/python/MergeSort.py b/Sort/python/MergeSort.py
@@ -0,0 +1,33 @@
+# -*- coding: utf-8 -*- 
+
+#---------------------------------------  
+#   程序：归并排序
+#   版本：
+#   作者：WuChong
+#   日期：2014-02-08
+#   语言：Python 3.3 
+#   说明：归并的思想就是先递归分解，再合并数组
+#---------------------------------------
+
+def merge_sort(ary):
+    if len(ary) <= 1 : return ary
+    num = int(len(ary)/2)       #二分分解
+    left = merge_sort(ary[:num])
+    right = merge_sort(ary[num:])
+    return merge(left,right)    #合并数组
+
+def merge(left,right):
+    '''合并操作，
+    将两个有序数组left[]和right[]合并成一个大的有序数组'''
+    l,r = 0,0
+    result = []
+    while l<len(left) and r<len(right) :
+        if left[l] < right[r]:
+            result.append(left[l])
+            l += 1
+        else:
+            result.append(right[r])
+            r += 1
+    result += left[l:]
+    result += right[r:]
+    return result
diff --git a/Sort/python/QuickSort.py b/Sort/python/QuickSort.py
@@ -0,0 +1,30 @@
+# -*- coding: utf-8 -*-
+
+#---------------------------------------
+#   程序：快速排序
+#   版本：
+#   作者：WuChong
+#   日期：2014-02-08
+#   语言：Python 3.3
+#   说明：
+#---------------------------------------
+
+def quick_sort(ary):
+    return qsort(ary,0,len(ary)-1)
+
+def qsort(ary,left,right):
+    #快排函数，ary为待排序数组，left为待排序的左边界，right为右边界
+    if left >= right : return ary
+    key = ary[left]     #取最左边的为基准数
+    lp = left           #左指针
+    rp = right          #右指针
+    while lp < rp :
+        while ary[rp] >= key and lp < rp :
+            rp -= 1
+        while ary[lp] <= key and lp < rp :
+            lp += 1
+        ary[lp],ary[rp] = ary[rp],ary[lp]
+    ary[left],ary[lp] = ary[lp],ary[left]
+    qsort(ary,left,lp-1)
+    qsort(ary,rp+1,right)
+    return ary
diff --git a/Sort/python/SelectionSort.py b/Sort/python/SelectionSort.py
@@ -0,0 +1,22 @@
+# -*- coding: utf-8 -*- 
+
+#---------------------------------------  
+#   程序：选择排序
+#   版本：
+#   作者：WuChong
+#   日期：2014-02-08
+#   语言：Python 3.3 
+#   说明：
+#---------------------------------------
+
+def select_sort(ary):
+    n = len(ary)
+    for i in range(0,n):
+        min = i                         #找到最小值的下标
+        for j in range(i+1,n):
+            if ary[j] < ary[min] :
+                min = j
+        ary[min],ary[i] = ary[i],ary[min]   #交换两者
+    return ary
+
+
diff --git a/Sort/python/ShellSort.py b/Sort/python/ShellSort.py
@@ -0,0 +1,24 @@
+# -*- coding: utf-8 -*- 
+
+#---------------------------------------  
+#   程序：希尔排序
+#   版本： 0.1
+#   作者：WuChong
+#   日期：2014-02-08
+#   语言：Python 3.3 
+#   说明：
+#---------------------------------------
+
+def shell_sort(ary):
+    n = len(ary)
+    gap = round(n/2)       #初始步长 , 用round四舍五入取整
+    while gap > 0 :
+        for i in range(gap,n):        #每一列进行插入排序 , 从gap 到 n-1
+            temp = ary[i]
+            j = i
+            while ( j >= gap and ary[j-gap] > temp ):    #插入排序
+                ary[j] = ary[j-gap]
+                j = j - gap
+            ary[j] = temp
+        gap = round(gap/2)                     #重新设置步长
+    return ary
diff --git a/Sort/python/__init__.py b/Sort/python/__init__.py
@@ -0,0 +1,10 @@
+# -*- coding: utf-8 -*- 
+
+#---------------------------------------  
+#   程序：
+#   版本： 
+#   作者：WuChong
+#   日期：2014-01-28
+#   语言：Python 3.3 
+#   说明：  
+#---------------------------------------
diff --git a/Sort/python/main.py b/Sort/python/main.py
@@ -0,0 +1,27 @@
+# -*- coding: utf-8 -*- 
+
+#---------------------------------------  
+#   程序：排序总控程序
+#   版本： 
+#   作者：WuChong
+#   日期：2014-01-28
+#   语言：Python 3.3 
+#   说明：自动随机50个1-99之间数，并调用排序算法进行排序
+#---------------------------------------
+
+import random
+import Sort.BubbleSort
+import Sort.InsertionSort
+import Sort.ShellSort
+import Sort.SelectionSort
+import Sort.MergeSort
+import Sort.QuickSort
+import Sort.HeapSort
+
+arry = [random.randint(1,99) for i in range(20)]
+
+print("排序前："+str(arry))
+
+sorted_arry = Sort.HeapSort.heap_sort(arry)
+
+print("排序后："+str(sorted_arry))
