arr = [9,8,2,23,3]

# 冒泡排序 两两比较，互换位置

# 3 5 9 1 8

# A B C D E

# 3 5 9 1 8

# 3 5 9 1 8

# 3 5 1 9 8

# 3 5 1 8 9

# 第一轮比较将最大数排到最后，5个数总共需要4轮即1，2，3，4

# 比较是arr[j] > arr[j+1]，第一轮j取前4个数即range(4)即可，第二轮j取前3个数range(3)即可

# 5个数总共比较 4 3 2 1 = 10次

def bubble_sort(arr):

    print 'bubble_sort:',arr

    count = 0

    for i in range(1, len(arr)):

        for j in range(len(arr)-i):

            count += 1

            if arr[j] > arr[j+1]:

                arr[j], arr[j+1] = arr[j+1], arr[j]

    print 'bubble_sorted:', count, arr

bubble_sort([9,8,2,23,3])

# bubble_sort([int(i) for i in raw_input(':').split()])   

# 3 5 9 1 8

# A B C D E

def select_sort(arr):

    count = 0

    for i in range(len(arr)-1): #总共需要4次min or max

        arr_min = min(arr[i:])  #取出的数放在列首更容易处理

        arr.remove(arr_min)

        arr.insert(i, arr_min)  #注意插入位置更新

    print arr

# select_sort(arr[:])   

# 五个数字需要4轮

# 0位和1，2，3，4比较，小的马上换到0位

# 1位和2，3，4比较，小的马上换到1位

def select_sort1(arr):

    count = 0

    for i in range(len(arr)-1):

        for j in range(i+1, len(arr)):

            count += 1

            if arr[i] > arr[j]:  #注意arr[i]一直被更新

                arr[i], arr[j] = arr[j], arr[i]

    print count

    print arr

# select_sort1(arr[:])   

def select_sort2(arr):

    print 'select_sort2:',arr

    count = 0

    for i in range(len(arr)-1):

        min_index = i

        for j in range(i+1, len(arr)):

            count += 1

            if arr[min_index] > arr[j]:

                min_index = j

        arr[i], arr[min_index] = arr[min_index], arr[i]  #一轮之后再更新 arr[i]

    print 'select_sort2ed:', count, arr

select_sort2([9,8,2,23,3])  

# 3 5 9 1 8

# A B C D E

#A已排序，BCDE未排序

#AB已排序，CDE未排序

def insert_sort(arr):

    print 'insert_sort:',arr

    count = 0

    for i in range(1, len(arr)):  #操作数是B

        for j in range(0,i):  #操作数是A

            count += 1

            print 'B', arr[i], 'A', arr[j], arr

            if arr[i] < arr[j]:

                arr.insert(j, arr[i])

                arr.pop(i+1)  #先插入，导致原来要移除的位置推后1位

                print arr

                break

    print 'insert_sorted:', count, arr

insert_sort([9,8,2,23,3])