数据结构-Python实现「选择类排序」

运行环境：python 2.7.12
学习课程来源：算法与数据结构C++精解

---

分类：

• 1.简单选择排序
• 2.堆排序

---

1. 简单选择排序

# _*_ coding:utf-8 _*_

def selection_sort(arr, n):
    for i in xrange(0, n):
        # 寻找[i, n)区间里最小值
        minIndex = i
        for j in xrange(i+1, n):
            if arr[j] < arr[minIndex]:
                minIndex = j
        arr[minIndex], arr[i] = arr[i], arr[minIndex]

if __name__ == '__main__':
    arr = [2,4,5,10,3,8,7,6,9,1]
    len_arr = len(arr)
    SelectionSort(arr, len_arr)
    print arr

2. 堆排序

# _*_ coding:utf-8 _*_
def __adjust(a, root, n):
    k = arr[root-1]
    c = root * 2

    while c <= n:
        if c + 1 <= n and arr[c] > arr[c-1]:
            c += 1

        if arr[c-1] <= k:
            break

        arr[c/2-1] = arr[c-1]
        c *= 2
    arr[c/2-1] = k

def heapSort(arr, n):
    for i in xrange(n / 2, 0, -1):
        __adjust(arr, i, n)

    for i in xrange(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        __adjust(arr, 1, i)