问题描述

对N个整数（数据由键盘输入）进行升序排列

问题分析

利用数组进行存储，利用两个相邻元素间进行比较交换的过程将一个无序表变成有序表。

假设数组元素的个数为n， 最糟的情况下需要比较的次数为（(n-1)+(n-2)+…+2+1）=n(n-1)/2

算法设计

Code

# !/user/bin/python3
# -*- coding: utf-8 -*-
# @author: HHVic
# @desc: 冒泡排序

import time

# add timer to calculate the performance
# Basic performance
###############################################################

start = time.time()

def bubbleSort(a):
    #首先获取列表的总长度
    n=len(a)
    #进行n-1次比较，控制比较的轮数
    i=1
    while i<=n-1:
        #控制每轮比较的次数
        j=0
        while j<n-i:
            if a[j]>a[j+1]:
                t=a[j]
                a[j]=a[j+1]
                a[j+1]=t
            j+=1
        i+=1
    #打印每轮交换后的列表
    for a1 in a:
        print(a1,end=' ')

if __name__=='__main__':
    print('请为列表元素赋初值，列表末尾不能有空格：')
    x=input()
    a=x.split(' ') #空格方式分割每个元素
    for i in range(0,len(a)):
        a[i]=int(a[i])
    print('你输入的列表元素为：\n',a)
    print('经过交换后的数组元素为：')
    bubbleSort(a)
    print('\n')



end = time.time()
print("The Basic Runtime is {0}".format((end-start)))

结果

请为列表元素赋初值，列表末尾不能有空格：
4 5 2 7 3 8 2 1 5
你输入的列表元素为：
 [4, 5, 2, 7, 3, 8, 2, 1, 5]
经过交换后的数组元素为：
1 2 2 3 4 5 5 7 8 

The Basic Runtime is 18.147606134414673