一、排序

在待排序的文件中，若存在多个关键字相同的记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变，该排序方法是稳定的；若具有相同关键字的记录之间的相对次序发生改变，则称这种排序方法是不稳定的。即所有相等的数经过某种排序方法后，仍能保持它们在排序之前的相对次序，则说这种排序算法是稳定的，反之，就是不稳定的。

1. 稳定的排序算法

稳定的排序	时间复杂度	空间复杂度
冒泡排序(bubble sort)	最差、平均都是O(n^2)，最好是O(n)	1
插入排序(insertion sort)	最差、平均都是O(n^2)，最好是O(n)	1
归并排序(merge sort)	最差、平均、最好都是O(n log n)	O(n)
桶排序(bucket sort)	O(n)	O(k)
基数排序(Radix sort)	O(dn)（d是常数）	O(n)
二叉树排序(Binary tree sort)	O(n log n)	O(n)

1.1 冒泡排序的实现

使用双重for循环，内层变量为i，外层为j，在内层循环中不断的比较相邻的两个值（i, i+1）的大小，如果i+1的值大于i的值，交换两者位置，每循环一次，外层的j增加1，等到j等于n-1的时候，结束循环

def bubble_sort(arr):
    n = len(arr)
    for j in range(0, n - 1):
        for i in range(0, n - 1 - j): # i每循环一次都能把最大的值以此从右边排起
            if arr[i] > arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]

arr = [7, 4, 3, 67, 34, 1, 8]
bubble_sort(arr)
print(arr)  # [1, 3, 4, 7, 8, 34, 67]

1.2 插入排序的实现

排序以从小到大排序为例，元素0为第一个元素，插入排序是从元素1开始，尽可能插到前面。插入时分插入位置和试探位置，元素i的初始插入位置为i，试探位置为i-1，在插入元素i时，依次与i-1,i-2······元素比较，如果被试探位置的元素比插入元素大，那么被试探元素后移一位，元素i插入位置前移1位，直到被试探元素小于插入元素或者插入元素位于第一位。

def insertSort(arr):
    length = len(arr)
    for i in range(1,length):
        x = arr[i] # 考虑插入的数
        for j in range(i,-1,-1):
            # j为当前位置，试探j-1位置
            if x < arr[j-1]:
                arr[j] = arr[j-1]
            else:
                # 位置确定为j
                break
        arr[j] = x

def printArr(arr):
    for item in arr:
        print(item)
arr = [4, 7 ,8 ,2 ,3 ,5]
insertSort(arr)
printArr(arr)

1.3 归并排序的实现

数据结构 6.排序

def merge_sort( li ):
    #不断递归调用自己一直到拆分成成单个元素的时候就返回这个元素，不再拆分了
    if len(li) == 1:
        return li
    #取拆分的中间位置
    mid = len(li) // 2
    #拆分过后左右两侧子串
    left = li[:mid]
    right = li[mid:]

    #对拆分过后的左右再拆分 一直到只有一个元素为止
    #最后一次递归时候ll和lr都会接到一个元素的列表
    # 最后一次递归之前的ll和rl会接收到排好序的子序列
    ll = merge_sort( left )
    rl =merge_sort( right )

    # 我们对返回的两个拆分结果进行排序后合并再返回正确顺序的子列表
    # 这里我们调用拎一个函数帮助我们按顺序合并ll和lr
    return merge(ll , rl)

#这里接收两个列表
def merge( left , right ):
    # 从两个有顺序的列表里边依次取数据比较后放入result
    # 每次我们分别拿出两个列表中最小的数比较，把较小的放入result
    result = []
    while len(left)>0 and len(right)>0 :
        #为了保持稳定性，当遇到相等的时候优先把左侧的数放进结果列表，因为left本来也是大数列中比较靠左的
        if left[0] <= right[0]:
            result.append( left.pop(0) )
        else:
            result.append( right.pop(0) )
    #while循环出来之后 说明其中一个数组没有数据了，我们把另一个数组添加到结果数组后面
    result += left
    result += right
    return result

if __name__ == '__main__':
    li = [30,50,57,77,62,78,94,80,84]
    li2 = merge_sort(li)
    print(li2)

2. 不稳定的排序算法

不稳定的排序	时间复杂度	空间复杂度
选择排序(selection sort)	最差、平均都是O(n^2)	1
希尔排序(shell sort)	O(n log n)	1
堆排序(heapsort)	最差、平均、最好都是O(n log n)	1
快速排序(quicksort)	平均是O(n log n)，最差是O(n^2)	O(log n)

2.1 选择排序的实现

对于一个无序的序列我们可以通过n-1趟排序得到排序结果。我们定义一个无序序列list[R0…….RN] 1.初始状态：无序区为list 2.第一趟排序在无序区间内选择一个关键字作为暂时的最小值min，然后将min与无序区间内的数挨个作比较，遇到比min的值小的做交换然后继续比较，直到比较完全部的无序区间。将min与无序数列的第一个数交换（R0）。此时将无序区间缩小成list[R1….RN]. 3.第i趟比较在i之前的数已经比较完可以看做是有序序列区间，在i之后的数仍为无序区间待比较。此时重复2的步骤在list[Ri….Rn]中选取一个关键字作为暂时最小值然后进行比较。

def selection_sort(list):
    for i in range(0,len(list)):#第一趟循环排出有序数列
        min = i #设定暂时最小值为无序区间第一个元素
        for j in range(i+1,len(list)):#第二趟排序让min去和无序数列的数作比较找出真正最小值
            if list[min] > list[j]:
                min = j
        list[min],list[i] = list[i],list[min]
    return list

arr = [7, 4, 3, 67, 34, 1, 8]
selection_sort(arr)
print(arr)  # [1, 3, 4, 7, 8, 34, 67]

2.2 堆排序的实现

[https://www.cnblogs.com/chengxiao/p/6129630.html]

import random

def MAX_Heapify(heap,HeapSize,root):#在堆中做结构调整使得父节点的值大于子节点

    left = 2*root + 1
    right = left + 1
    larger = root
    if left < HeapSize and heap[larger] < heap[left]:
        larger = left
    if right < HeapSize and heap[larger] < heap[right]:
        larger = right
    if larger != root:#如果做了堆调整则larger的值等于左节点或者右节点的，这个时候做对调值操作
        heap[larger],heap[root] = heap[root],heap[larger]
        MAX_Heapify(heap, HeapSize, larger)

def Build_MAX_Heap(heap):#构造一个堆，将堆中所有数据重新排序
    HeapSize = len(heap)#将堆的长度当独拿出来方便
    for i in range((HeapSize -2)//2,-1,-1):#从后往前出数
        MAX_Heapify(heap,HeapSize,i)

def HeapSort(heap):#将根节点取出与最后一位做对调，对前面len-1个节点继续进行对调整过程。
    Build_MAX_Heap(heap)
    for i in range(len(heap)-1,-1,-1):
        heap[0],heap[i] = heap[i],heap[0]
        MAX_Heapify(heap, i, 0)
    return heap

if __name__ == '__main__':
    a = [30,50,57,77,62,78,94,80,84]
    print (a)
    HeapSort(a)
    print (a)
    b = [random.randint(1,1000) for i in range(1000)]
    print (b)
    HeapSort(b)
    print (b)

2.3 快速排序的实现

算法导论上的快速排序采用分治算法，步骤如下：
1.选取一个数字作为基准，可选取末位数字；

2.将数列第一位开始，依次与此数字比较，如果小于此数，将小数交换到左边，最后达到小于基准数的在左边，大于基准数的在右边，分为两个数组；

3.分别对两个数组重复上述步骤。

def QuickSort(arr,firstIndex,lastIndex):
    if firstIndex<lastIndex:
        divIndex=Partition(arr,firstIndex,lastIndex)
 
        QuickSort(arr,firstIndex,divIndex)       
        QuickSort(arr,divIndex+1,lastIndex)
    else:
        return
 
 
def Partition(arr,firstIndex,lastIndex):
    i=firstIndex-1
    for j in range(firstIndex,lastIndex):
        if arr[j]<=arr[lastIndex]:
            i=i+1
            arr[i],arr[j]=arr[j],arr[i]
    arr[i+1],arr[lastIndex]=arr[lastIndex],arr[i+1]
    return i
  
arr=[1,4,7,1,5,5,3,85,34,75,23,75,2,0]
 
print("initial array:\n",arr)
QuickSort(arr,0,len(arr)-1)
print("result array:\n",arr)