杂记-排序顺便写python

# 生成随机整数列表
import random

def randomList(n):
    iList = []
    for i in range(n):
        iList.append(random.randrange(20))
    return iList

if __name__ == "__main__":
    iList = randomList(10)
    print(iList)

[7, 17, 19, 2, 8, 6, 11, 7, 4, 14]

# 冒泡排序
import timeit

iList = randomList(6)

def bubbleSort(iList):
    if (len(iList) <= 1):
        return iList
    for i in range(1, len(iList)):
        for j in range(0, len(iList) - 1):
            if (iList[j] >= iList[j+1]):
                iList[j], iList[j+1] = iList[j+1], iList[j]
        print (i, end= "")
        print(iList)
    return iList

if __name__ == "__main__":
    print (bubbleSort(iList))
    

1[11, 2, 0, 9, 12, 19]
2[2, 0, 9, 11, 12, 19]
3[0, 2, 9, 11, 12, 19]
4[0, 2, 9, 11, 12, 19]
5[0, 2, 9, 11, 12, 19]
[0, 2, 9, 11, 12, 19]

iList = randomList(6)

# 选择排序
def selectionSort(iList):
    for i in range(0, len(iList) - 1):
        #minIndex = i
        #for j in range(i+1, len(iList)):
         #   if iList[j] < iList[minIndex]:
          #      minIndex = j
        if iList[i] != min(iList[i:]):
            minIndex = iList.index(min(iList[i:]))
            iList[i], iList[minIndex] = iList[minIndex], iList[i]
        print (i, end="")
        print(iList)
    return iList

if __name__ == "__main__":
    selectionSort(iList)

0[2, 7, 16, 11, 8, 14]
1[2, 7, 16, 11, 8, 14]
2[2, 7, 8, 11, 16, 14]
3[2, 7, 8, 11, 16, 14]
4[2, 7, 8, 11, 14, 16]

iList = randomList(6)

# 插入排序
def insertionSort(iList):
    if len(iList)<=1:
        return iList
    for right in range(1, len(iList)):
        target = iList[right]
        for left in range(0, right):
            if target < iList[left]:
                iList[left+1:right+1] = iList[left:right]
                iList[left]=target
                break
        print (right, end="")
        print(iList)
        
    return iList

if __name__ == "__main__":
    insertionSort(iList)

1[1, 3, 4, 14, 17, 7]
2[1, 3, 4, 14, 17, 7]
3[1, 3, 4, 14, 17, 7]
4[1, 3, 4, 14, 17, 7]
5[1, 3, 4, 7, 14, 17]

iList = randomList(6)

# 归并排序
def mergeSort(iList):
    if len(iList)<=1:
        return iList
    
    middle = len(iList) // 2
    left, right = iList[0: middle], iList[middle:]
    #print (left)
    #print (right)
    return mergeList(mergeSort(left), mergeSort(right))

def mergeList(left, right):
    mList=[]
    while left and right:
        if (left[0] > right[0]):
            mList.append(right.pop(0))
        else:
            mList.append(left.pop(0))
    while left:
        mList.append(left.pop(0))
    while right:
        mList.append(right.pop(0))
    return mList

if __name__ == "__main__":
    print (iList)
    print (mergeSort(iList))
        
    

[10, 18, 0, 4, 16, 12]
[0, 4, 10, 12, 16, 18]

iList = randomList(6)

# 快速排序

def quickSort(iList):
    if len(iList) <= 1:
        return iList
    left = []
    right = []
    
    for i in iList[1:]:
        if (i < iList[0]):
            left.append(i)
        else:
            right.append(i)
            
    return quickSort(left) + [iList[0]] + quickSort(right)

if __name__ == "__main__":
    print (iList)
    print (quickSort(iList))

[11, 7, 7, 14, 4, 10]
[4, 7, 7, 10, 11, 14]

iList = randomList(6)

# 计数排序
def countingSort(iList):
    if len(iList) <= 1:
        return iList
    iLen = len(iList)
    rList = [None] * iLen
    for i in range(iLen):
        small = 0
        same = 0
        for j in range(iLen):
            if (iList[j] < iList[i]):
                small += 1
            elif  iList[j] == iList[i]:
                same +=1
        for k in range(small, small + same):
            rList[k] = iList[i]
    return rList

if __name__ == "__main__":
    print (iList)
    print (countingSort(iList))

[11, 10, 6, 5, 17, 0]
[0, 5, 6, 10, 11, 17]