一、非线性时间比较类排序

• 交换排序
  1. 冒泡排序
  2. 快速排序
• 插入排序
  3. 简单插入排序
  4. 希尔排序
• 选择排序
  5. 简单选择排序
  6. 堆排序
• 归并排序
  7. 二路归并排序
  8. 多路归并排序

二、线性时间非比较类排序

9. 基数排序
10. 捅排序
11. 计数排序

各算法实现

import time

01 冒泡排序实现

冒泡排序思想:使用双重for循环，内层变量为i， 外层为j，在内层循环中不断的比较相邻的两个值（i, i+1）的大小，
如果i+1的值大于i的值，交换两者位置，每循环一次找到一个最大值放大最后，每循环一次，外层的j增加1，等到j等于n-1的时候，结束循环
代码实现：

def maoPao(nums):
    for i in range(len(nums)-1):
        print(i)
        for j in range(len(nums)-i-1):
            #print(j+1)
            if nums[j] > nums[j+1]:
                nums[j],nums[j+1] = nums[j+1],nums[j]
            print(nums)
    return nums
nums = [35,12,99,22,45]
start = time.clock()
maoPao(nums)
end = time.clock()
#print(end-start)
print(maoPao(nums))

02选择排序

选择排序思想:先取出第一个元素,依次和后面的元素进行比较,符合if条件,进行交换,先找到最小的下标代码实现：

numszl02 = [9,3,5,2,7,4]
def quickSort(nums):
    for i in range(0,len(nums)-1):
        index = i
        print("index的值为:",index)
        for j in range(i+1,len(nums)):
            print(j)
            if nums[index] > nums[j]:
                index = j
        nums[i],nums[index] = nums[index],nums[i]
        print(nums);
    return nums
quickSort(numszl02)
print(quickSort(nums))

03 直接插入排序

直接插入排序思想:直接排序是一组数据a[0…n]，从i（初始i =1）个开始
假设a[0…i-1]都是有序的，
a[i]是要插入的数据，遍历a[0…i-1]，如果a[0…i-1]中有比a[i]还要大，
那么将此数据向后移一位，直到遇到没有比a[i]大的数a[s]或到头为止，
最后将a[i]放到最后那个a[s]之后即可代码实现：

numzl = [2,1,5,7,3]
def insertSort(nums):
    for i in range(1,len(nums)):
        temp = nums[i]
        j = i
        print("外层循环中j的值为",j)
        while j>0 and nums[j-1]>temp:
        # if j>0 and nums[j-1]>temp:
            print("执行了while几次,内层循环j的值",j)
            nums[j] = nums[j-1]
            print(nums)
            j = j-1
        nums[j] = temp
    return nums
print(insertSort(numzl))

_未完待续