排序算法

数据结构

冒泡排序

两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。

def bubblesort(list):
    for iter_num in range(len(list)-1,0,-1):
        for idx in range(iter_num):
            if list[idx]>list[idx+1]:
                temp = list[idx]
                list[idx] = list[idx+1]
                list[idx+1] = temp
list = [19,2,31,45,6,11,121,27]
bubblesort(list)

简单选择排序

每次从待排序数据元素中选出最小/最大存放在序列的起始位置，知道全部待排序的数据元素排完。

def selectorder(unsortedlist):
    for idx in rang(len(unsortedlist)):
        min_idx = idx
        for j in range(idx+1,len(unsortedlist)):
            if unsortedlist[min_idx] > unsortedlist[j]:
                min_idx = j
        unsortedlist[idx],unsortedlist[min_idx] = unsortedlist[min_idx],unsortedlist[idx]
    return unsortedlist

直接插入排序

将一个数据直接插入到已经排好序的序列中。

def insertsort(unsortedlist):
    for i in range(1,len(unsortedlist)):
        j = i-1
        next_element = unsortedlist[i]
        while (unsortedlist[j] > nxt_element) and (j >= 0):
            unsortedlist[j+1] = unsortedlist[j]
            j -= 1
        unsortedlist[j+1] = next_element
    return unsortedlist

希尔排序

按一定下标的增量分组（每隔一定间隔选取一个数），对每组使用直接插入排序算法排序，随着增量逐渐减少每组包含的关键词越来越少，当增量减到1的时候，算法终止。然后再进行微调即可获得排序序列。
常见增量序列（非最优）：{n/2,(n/2)/2...1} n=len(list)

def shellsort(unsortedlist):
    gap = len(unsortedlist) //2
    while gap >= 1:
        for i in range(gap, len(unsortedlist)):
            temp = unsortedlist[i]
            j = i
            while j >= gap and unsortedlist[j-gap] > temp:
                unsortedlist[j] = unsortedlist[j-gap]
                j = j - gap
            unsortedlist[j] = temp
        gap = gap // 2
    return unsortedlist

堆排序

归并排序

将两个已经排序的序列合并成一个序列。

#import sys
#sys.setrecursionlimit(1000000)
def mergesort(unsortedlist):
    if len(unsortedlist) <= 1:
        return unsortedlist
    middle = len(unsortedlist) // 2
    list_left = unsortedlist[:middle]
    list_right = unsortedlist[middle:]
    list_left = mergesort(list_left)
    list_right = mergesort(list_right)
    return list(merge(list_left,list_right))
def merge(list_left,list_right):
    result = []
    while len(list_left) != 0 and len(list_right) !=0:
        if list_left[0] < list_right[0]:
            result.append(list_left[0])
            list_left.remove(list_left[0])
        else:
            result.append(list_right[0])
            list_right.remove(list_right[0])
    if len(list_left) == 0:
        result += list_right
    else:
        result += list_left
    return result
unsortedlst = [64, 34, 25, 12, 22, 11, 90]
print(mergesort(unsortedlst))

快速排序