L = [2,6,4,7,9,1,3,5,8]

# 1.插入排序

def insert_sort(List):

	n = len(List)

	for i in range(1,n):            # 得到索引

		j = i-1                     # 获取当前元素之前的索引

		temp = List[i]

		while j >= 0:               # 当索引大于等于时开始循环

			if temp < List[j]:      # 当List[i]元素小于之前的元素

				List[j+1] = List[j] # 交换两个元素的位置

				List[j] = temp

			j -= 1                  # 继续比较交换后的list[i]和再前一个元素的大小,继续循环

	return List

print(insert_sort(L))

#2.冒泡排序

def bubble_sort(List):

	n = len(List)

	for i in range(n):

		for j in range(i+1, n):

			if List[i] > List[j]:

				List[j], List[i] = List[i], List[j]

	return List

print(bubble_sort(L))

# 3.快速排序

def quick_sort(List,low,high):

    i=low

    j=high

    if i >= j:

        return List

    key=List[i]

    while i < j:

		# 当高位游标大于基准值时, 高位游标向左移动

        while i < j and List[j]>=key:

            j = j - 1

        List[i]=List[j]

		# 当低位游标指向的值,小于基准值时, 低位游标向右移动

        while i < j and List[i]<=key:

            i = i + 1

        List[j]=List[i]

    List[i]=key

    quick_sort(List,low,i-1) # 对基准值左边的未排序队列排序

    quick_sort(List,j+1,high)# 对基准值右边的未排序队列排序

    return List

print(quick_sort(L, 0, len(L)-1))

#4.选择排序

def select_sort(List):

    length = len(List)

    for i in range(length):   # 得出全部的索引

        min_index=i           # 假设最小的索引

        for j in range(i,length):      # 获取i之后的索引

            if List[j]<List[min_index]:# 比较i 之后的元素与最小元素的大小

                min_index=j            # 如果小于最小元素,那么久交换索引

        List[i],List[min_index]=List[min_index],List[i]  # 交换最小的索引指向的值

    return List

print(select_sort(L))

#5.归并排序

def merge_sort(list):

    if len(list)<=1:

        return list

    # 根据长度确定中间位置

    mid = int(len(list)/2)

    left=merge_sort(list[:mid])

    right=merge_sort(list[mid:])

    return merge(left,right)

def merge(list1,list2):

    list=[]

    i,j=0,0

    while i<len(list1) and j<len(list2):

        if list1[i]<list2[j]:

            list.append(list1[i])

            i=i+1

        elif list1[i]>=list2[j]:

            list.append(list2[j])

            j=j+1

    list.extend(list1[i:])

    list.extend(list2[j:])

    return list

print(merge_sort(L))

#6.希尔排序

def shell_sort(List):

    step = int(len(List)/2)

    while step > 0:

        for i in range(step, int(len(List))):

            while i >= step and List[i-step] > List[i]:

                List[i], List[i-step] = List[i-step], List[i]

                i -= step

        step = int(step/2)

    return List

print(shell_sort(L))

# 7.堆排序

def adjust_heap(List, i, size):

	lchild = 2 * i + 1

	rchild = 2 * i + 2

	m = i

	if i < int(size/2) and List[lchild] > List[m]:

		m = lchild

	if rchild < size and List[rchild] > List[m]:

		m = rchild

	if m != i:

		List[m], List[i] = List[i], List[m]

		adjust_heap(List, m, size)

def build_heap(List, size):

	for i in range(0, int(size/2))[::-1]:

		adjust_heap(List, i, size)

def heap_sort(List):

	size = len(List)

	build_heap(List, size)

	for i in range(0, size)[::-1]:

		List[0], List[i] = List[i], List[0]

		adjust_heap(List, 0, i)

	return List

print(heap_sort(L))

# 8.基数排序

import math

def radix_sort(List, radix=10):

	n = int(math.ceil(math.log(max(List), radix)))

	bucket = [[] for i in range(radix)]

	for i in range(1, n + 1):

		for j in List:

			bucket[int(j/(radix**(i-1))) % (radix**i)].append(j)

		del List[:]

		for x in bucket:

			List += x

			del x[:]

	return List

print(radix_sort(L))