Python3 示例

1. 数字求和

 num1 = input('输入第一个数字：')
 num2 = input('输入第二个数字:')
 sum = float(num1) + float(num2)
 print ('数字{0} 加 数字{1} 的和为{2}'.format(num1,num2,sum))

2. 平方根

import cmath
num = input('输入一个数字:')
if num > 0:
    num_sqrt = num ** 0.5
else:
    num_sqrt = cmath.sqrt(num)

print ('数字{0}的平方根为{1}'.format(num,num_sqrt))

3. 二次方程

'''
二次方程式 ax**2 + bx + c = 0
a、b、c 用户提供，为实数，a ≠ 0

'''

import cmath

a = float(input('输入 a :'))
b = float(input('输入 b :'))
c = float(input('输入 c :'))

d = (b ** 2) - (4*a*c)

sol1 = (-b-cmath.sqrt(d))/(2*a)
sol2 = (-b+cmath.sqrt(d))/(2*a)
print('结果为 {0} 和 {1}'.format(sol1,sol2))

4. 三角形面积

a = input('输入三角形第一边长:')
b = input('输入三角形第二边长:')
c = input('输入三角形第三边长:')

# 计算半周长
s = (a + b + c)/2
t = s*(s-a)*(s-b)*(s-c)
if t > 0:
    area = t ** 0.5
    print('三角形面积为 %0.2f' %area)
else:
    print ('{0} {1} {2} 无法形成三角形'.format(a, b, c))

5. 圆的面积

def findArea(r):
    PI = 3.142
    return PI * (r**2)
print ('半径为{0}的圆的面积为 {1}'.format(5,findArea(5)))

6. 随机数

'''

random.randint(a,b)
函数返回数字 N ，N 为 a 到 b 之间的数字（a <= N <= b），包含 a 和 b。
'''

import random
print(random.randint(0,9))

7. 交换变量

x = input('输入x值')
y = input('输入y值')
tenp = x
x = y
y = tenp
print ('x {0} y {1}'.format(x, y))

8. if 语句

num = input('输入一个数字:')
if num >=0 :
   if num == 0:
       print ('0')
   else:
       print ('正数')
else:
    print ('负数')

9. 判断字符串是否为数字

'''
python2 可能不准确
'''

def is_number(s):
    try:
        float(s)
        return True
    except ValueError:
        pass

    try:
        import unicodedata
        for i in s:
            unicodedata.numeric(i)
        return True
    except (TypeError, ValueError):
        pass

    return False

# 测试字符串和数字
print(is_number('foo'))   # False
print(is_number('1'))     # True
print(is_number('1.3'))   # True
print(is_number('-1.37')) # True
print(is_number('1e3'))   # True

# 测试 Unicode
# 阿拉伯语 5
print(is_number('٥'))  # True
# 泰语 2
print(is_number('๒'))  # True
# 中文数字
print(is_number('四')) # True
# 版权号
print(is_number('©'))  # False

10. 判断奇偶数

num = int(input('输入一个数字:'))
if (num % 2) == 0:
    print ('{0} 是偶数'.format(num))
else:
    print ('{0} 是奇数'.format(num))

11. 判断闰年

num = input('输入年份:')

if (num % 4) == 0:
    if (num % 100) == 0:
        if (num % 400) == 0:
            print ('闰年')
        else:
            print ('不是闰年')

    else:
        print ('闰年')

else:
    print ('不是闰年')

12. 获取最大值函数

print (max(1, 2))
print (max('a', 'b'))
print (max([1, 2]))
print (max((1, 2)))

13. 质数判断

def is_prime(n):
    if n > 1:
        for i in range(2, n):
            if (n % i) == 0:
                print ('非质数')
                break
        else:
            print ('质数')


    else:
        print ('非质数')

print (is_prime(13))

14.输出指定范围内的素数

lower = int(input("输入区间最小值: "))
upper = int(input("输入区间最大值: "))

for num in range(lower,upper+1):
    if num > 1 :
        for i in range(2, num):
            if (num % i) == 0:
                break
        else:
            print (num)

15. 阶乘

while True:
    try:
        num = int(input('输入一个数字：'))
        break
    except (TypeError, ValueError, NameError):
        pass

factorial = 1
if (num > 0):
    for i in range(1, num+1):
        factorial *= i
    else:
        print ('{0}的阶乘 为 {1}'.format(num, factorial))

elif (num == 0):
    print ('{0}的阶乘 为 {1}'.format(num, factorial))

else:
    print ('{0} 负数无阶乘')

16. 九九乘法表

'''
通过指定end参数的值，可以取消在末尾输出回车符，实现不换行
'''
for i in range(1, 10):
    for j in range(1, i+1):
        print ('{0} x {1} = {2} \t'.format(j, i, j*i), end = " ")

17. 斐波那契数

a = 0
b = 1
count = 0

num = int(input('你需要几项斐波那契数:'))
if num <= 0:
    print ('请输入一个正数')
elif num == 1:
    print (a)
else:
    print (a)
    print (b)

    while count < num-2:
        nth = a + b
        a = b
        b = nth
        count +=1
        print (nth)


def fibo(n):
    if n <= 1:
        return n
    else:
        return fibo(n-1) + fibo(n-2)

nterms = int(input("您要输出几项? "))

if nterms <= 0:
    print ('请输入正数')
else:
    print ('斐波那契数列:')
    for i in range(nterms):
        print (fibo(i))

18. 阿姆斯特朗 数

'''
如果一个n位正整数等于其各位数字的n次方之和,则称该数为阿姆斯特朗数。 
例如1^3 + 5^3 + 3^3 = 153。
1000以内的阿姆斯特朗数： 1, 2, 3, 4, 5, 6, 7, 8, 9, 153, 370, 371, 407

'''

num = int(input('输入一个数字:'))
n = len(str(num))
s = 0

temp = num
while temp > 0:
    digt = temp % 10
    s += digt ** n
    temp = temp // 10

if s == num :
    print ('是 阿姆斯特朗 数')
else:
    print ('不是 阿姆斯特朗 数')


lower = int(input("最小值: "))
upper = int(input("最大值: "))


for i in range(lower, upper+1):
    s = 0
    n = len(str(i))
    temp = i
    while temp>0 :
        digt = temp % 10
        s += digt ** n
        temp = temp/10
    if s == i:
        print (i)

19. 进制转换

num = int(input('输入一个数字:'))

print ('十进制 ：{}'.format(num))
print ('二进制 : {}'.format(bin(num)))
print ('八进制 : {}'.format(oct(num)))
print ('十六进制 : {}'.format(hex(num)))

20. ASCII码 与字符互相转换

c = input("请输入一个字符: ")
a = int(input("请输入一个ASCII码: "))

print( c + " 的ASCII 码为", ord(c))
print( a + " 对应的字符为", chr(a))

21. 最大公约数

num1 = int(input('输入一个数字:'))
num2 = int(input('输入第二个数字:'))

if num1 > num2:
    samller = num2
else:
    samller = num1

for i in range(1, samller+1):
    if (num1 % i) ==0 and (num2 % i) ==0:
        hrf = i

print (hrf)

22. 最小公倍数

num1 = int(input('输入第一个数字:'))
num2 = int(input('输入第二个数字:'))

if num1 > num2:
    greater = num1
else:
    greater = num2

while(True):
    if (greater % num1) == 0 and (greater % num2) == 0:
        lcm = greater
        break
    greater += 1
print (lcm)

23. 日历

import calendar

yy = int(input('输入年份:'))
mm = int(input('输入月份:'))

if (mm > 12 or mm <0 or yy <0):
    print ('输入有误')
else:
    print (calendar.month(yy, mm))

24.字符串 判断

str1 = "runoob.com"
print(str1.isalnum()) # 判断所有字符都是数字或者字母
print(str1.isalpha()) # 判断所有字符都是字母
print(str1.isdigit()) # 判断所有字符都是数字
print(str1.islower()) # 判断所有字符都是小写
print(str1.isupper()) # 判断所有字符都是大写
print(str1.istitle()) # 判断所有单词都是首字母大写，像标题
print(str1.isspace()) # 判断所有字符都是空白字符、\t、\n、\r


str2 = "runoob"
print(str2.isalnum())
print(str2.isalpha())
print(str2.isdigit())
print(str2.islower())
print(str2.isupper())
print(str2.istitle())
print(str2.isspace())

25. 字符串 大小写转换

str = "www.runoob.com"
print(str.upper())          # 把所有字符中的小写字母转换成大写字母
print(str.lower())          # 把所有字符中的大写字母转换成小写字母
print(str.capitalize())     # 把第一个字母转化为大写字母，其余小写
print(str.title())          # 把每个单词的第一个字母转化为大写，其余小写

26. 计算每个月天数

'''
输出的是一个元组，第一个元素是所查月份的第一天对应的是星期几（0-6），第二个元素是这个月的天数。
以上实例输出的意思为 2019 年 11 月份的第一天是星期五，该月总共有 30 天
'''
import calendar
monthRange = calendar.monthrange(2019, 11)
print (monthRange)

27. 获取昨天日期

import datetime
def getTesterday():
    today = datetime.date.today()
    oneday = datetime.timedelta(days=1)
    yesterday = today-oneday
    return yesterday
print (getTesterday())

28. 约瑟夫生者死者小游戏

'''
30 个人在一条船上，超载，需要 15 人下船。

于是人们排成一队，排队的位置即为他们的编号。

报数，从 1 开始，数到 9 的人下船。

如此循环，直到船上仅剩 15 人为止，问都有哪些编号的人下船了呢？

'''

people = {}

for x in range(1, 31):
    people[x] = 1

check = 0
i = 1
j = 0

while i <= 31:
    if i == 31:
        i = 1
    elif j == 15:
        break
    else:
        if people[i] == 0:
            i += 1
            continue
        else:
            check += 1
            if check == 9:
                people[i] = 0
                check = 0
                j += 1
                print('{0} 号下船'.format(i))
            else:
                i += 1
                continue

29. 计算 n个自然数的立方和

def sumofserises(n):
    sum1 = 0
    for i in range(1, n+1):
        sum1 += i**3
    return sum1

n = 5
print(sumofserises(n))

30. 计算数组元素的和

def sumofarr(arr):
    return sum(arr)
arr = [12, 15, 10, 20]
print(sumofarr(arr))

31. 数组翻转指定个数的元素

'''
定义一个整型数组，并将指定个数的元素翻转到数组的尾部。

例如：(ar[], d, n) 将长度为 n 的 数组 arr 的前面 d 个元素翻转到数组尾部

'''

def leftRotate(arr, d, n):
    for i in range(d):
        leftRotatebyOne(arr, n)
def leftRotatebyOne(arr, n):
    temp = arr[0]
    for i in range(n-1):
        arr[i] = arr[i+1]
    arr[n-1] = temp
arr = [1, 2, 3, 4, 5, 6, 7]
leftRotate(arr, 2, 7)
print(arr)





def leftRotate2(arr, d, n):
    temp1 = arr[:d]
    arr[:d] = []
    arr.extend(temp1)

arr2 = [1, 2, 3, 4, 5, 6, 7]
leftRotate2(arr2, 2, 7)
print(arr2)


def reversal(lst,n):
    for x in range(n):
        lst.append(arr.pop(0))
    return lst

32. 将列表中的首尾两个元素对调

def swapList(newList):
    size = len(newList)

    temp = newList[0]
    newList[0] = newList[size - 1]
    newList[size - 1] = temp

    return newList


newList = [1, 2, 3]

print(swapList(newList))


def swapList2(newList):
    newList[0], newList[-1] = newList[-1], newList[0]

    return newList


newList2 = [1, 2, 3]
print(swapList2(newList2))


def swapList3(list):
    get = list[-1], list[0]

    list[0], list[-1] = get

    return list


newList3 = [1, 2, 3]
print(swapList3(newList3))

33. 将列表中的指定位置的两个元素对调

def swapPos(list, pos1, pos2):
    list[pos1], list[pos2] = list[pos2], list[pos1]
    return list
list = [12, 25, 39, 45]
pos1, pos2 = 1, 3
print(swapPos(list, pos1-1, pos2-1))


def swapPos(list, pos1, pos2):
    first_ele = list.pop(pos1)
    second_ele = list.pop(pos2-1)

    list.insert(pos1, second_ele)
    list.insert(pos2, first_ele)

    return list


List = [23, 65, 19, 90]
pos1, pos2 = 1, 3

print(swapPos(List, pos1 - 1, pos2 - 1))


def swapPositions(list, pos1, pos2):
    get = list[pos1], list[pos2]

    list[pos2], list[pos1] = get

    return list


List = [23, 65, 19, 90]

pos1, pos2 = 1, 3
print(swapPositions(List, pos1 - 1, pos2 - 1))

34. 翻转列表

'''
翻转前 : list = [10, 11, 12, 13, 14, 15]
翻转后 : [15, 14, 13, 12, 11, 10]
'''

def Reverse(lst):
    return [ele for ele in reversed(lst)]
lst = [10, 11, 12, 13, 14, 15]
print (Reverse(lst))


def Reverse(lst):
    lst.reverse()
    return lst
lst = [10, 11, 12, 13, 14, 15]
print (Reverse(lst))


def Reverse(lst):
    new_list = lst[::-1]
    return new_list
lst = [10, 11, 12, 13, 14, 15]
print (Reverse(lst))

35. 判断元素是否在列表中存在

test_list = [1, 6, 3, 5, 3, 4]

for i in test_list:
    if (i == 4):
        print ("存在")



if (4 in test_list):
    print ("存在")


test_list_set = [1, 6, 3, 5, 3, 4]
test_list_set = set(test_list_set)
if 4 in test_list_set:
    print ("存在")

from bisect import bisect_left
test_list_bisect = [1, 6, 3, 5, 3, 4]
test_list_bisect.sort()
if bisect_left(test_list_bisect, 4):
    print ("存在")

36. 清空列表

RUNOOB = [6, 0, 4, 1]
RUNOOB.clear()
print(RUNOOB)

RUNOOB = [6, 0, 4, 1]
RUNOOB[:] = []
print(RUNOOB)

RUNOOB = [6, 0, 4, 1]
del RUNOOB[:]
print(RUNOOB)

37. 复制列表

def clone_runoob(li1):
    li_copy = li1[:]
    return li_copy

li1 = [4, 8, 2, 10, 15, 18]
li2 = clone_runoob(li1)
print (li2)


def clone_runoob(li1):
    li_copy = []
    li_copy.extend(li1)
    return li_copy
li1 = [4, 8, 2, 10, 15, 18]
li2 = clone_runoob(li1)
print (li2)


def clone_runoob(li1):
    li_copy = list(li1)
    return li_copy
li1 = [4, 8, 2, 10, 15, 18]
li2 = clone_runoob(li1)
print (li2)

38. 计算元素在列表中出现的次数

def countX(lst,x):
    count = 0
    for i in lst:
        if i == x:
            count += 1

    return count

lst = [8, 6, 8, 10, 8, 20, 10, 8, 8]
print (countX(lst, 8))


def countX(lst, x):
    return lst.count(x)
lst = [8, 6, 8, 10, 8, 20, 10, 8, 8]
print (countX(lst, 8))

39. 计算列表元素和

def sumoffarr(lst):
    total = 0
    for i in lst:
        total += i
    return total

lst = [11, 5, 17, 18, 23]
print (sumoffarr(lst))


def sumoffarr(lst):
    total = 0
    ele = 0
    while ele<len(lst):
        total += lst[ele]
        ele += 1
    return total

lst = [11, 5, 17, 18, 23]
print (sumoffarr(lst))


def sumOfList(list, size):
   if (size == 0):
     return 0
   else:
     return list[size - 1] + sumOfList(list, size - 1)

lst = [11, 5, 17, 18, 23]
print (sumoffarr(lst))

40. 计算列表元素积

def mulofflst(lst):
    mul = 1
    for i in lst:
        mul *= i
    return mul
list1 = [2, 2, 3]
print (mulofflst(list1))

41. 查找列表中最小值

def minofflst(lst):
    return min(lst)

list1 = [10, 20, 4, 45, 99]
print (minofflst(list1))


def minofflst(lst):
    lst2 = sorted(lst)
    return lst2[0]

list1 = [10, 20, 4, 45, 99]
print (minofflst(list1))

42. 查找列表中 最大元素

def maxofflst(lst):
    return max(lst)

list1 = [10, 20, 4, 45, 99]
print (maxofflst(list1))


def maxofflst(lst):
    lst1 = sorted(lst)
    return lst1[-1]

list1 = [10, 20, 4, 45, 99]
print (maxofflst(list1))

43. 移除字符串中指定位置的元素

def removestr(str, i):
    str2 = str[:i] + str[i+1:]
    return str2

test_str = "Runoob"
print (removestr(test_str, 2))

def removestr(str1, i):
    lst = list(str1)
    lst.pop(i)
    str2 = ''.join(lst)
    return str2
test_str = "Runoob"
print (removestr(test_str, 2))

44. 判断字符串中是否存在子字符串

def checkStr(orgStr, searchStr):
    if (orgStr.find(searchStr)==-1):
        print('不存在')
    else:
        print('存在')

str1 = 'runoob.com'
str2 = 'com'
checkStr(str1, str2)

45. 计算字符串的长度

def lenofstr(str):
    return len(str)

str = 'runoob'
print(lenofstr(str))


def lenofstr(str):
    count = 0
    while str[count:]:
        count += 1
    return count

str = 'runoob'
print(lenofstr(str))

46. 使用正则表达式提取字符串中的URL

import re
def find(string):
    url = re.findall('https?://(?:[-\w.]|(?:%[\da-fA-F]{2}))+', string)
    return url

string = 'Runoob 的网页地址为：https://www.runoob.com，Google 的网页地址为：https://www.google.com'
print(find(string))

47. 将字符串作为可执行代码

def exec_code():
    LOC = """
def factorial(num):
    fact=1
    for i in range(1,num+1):
        fact = fact*i
    return fact
print(factorial(5))
    """
    exec (LOC)

exec_code()

48. 字符串翻转

def reversed(str):
    return str[::-1]

str='Runoob'
print(reversed(str))


def reversed2(str1):
    return ''.join(reversed(str))

str='Runoob'
print(reversed2(str))

49. 对字符串切片及翻转

'''
给定一个字符串，从头部或尾部截取指定数量的字符串，然后将其翻转拼接
'''

def rotate(str, d):
    lfirst = str[:d]
    lsecond = str[d:]
    rfirst = str[0 : len(str)-d]
    rsecond = str[len(str)-d : ]
    print(lsecond+lfirst)
    print(rsecond+rfirst)

str = 'Runoob'
d = 2
rotate(str, d)

50. 按键或值对字典排序

def dictionairy():
    # 声明字典
    key_value = {}

    # 初始化
    key_value[2] = 56
    key_value[1] = 2
    key_value[5] = 12
    key_value[4] = 24
    key_value[6] = 18
    key_value[3] = 323

    print("按键(key)排序:")

    # sorted(key_value) 返回一个迭代器
    # 字典按键排序
    for i in sorted(key_value):
        print((i, key_value[i]), end=" ")
    print('\n')

dictionairy()


def dictionairy():
    # 声明字典
    key_value = {}

    # 初始化
    key_value[2] = 56
    key_value[1] = 2
    key_value[5] = 12
    key_value[4] = 24
    key_value[6] = 18
    key_value[3] = 323

    print("按值(value)排序:")
    print(sorted(key_value.items(), key=lambda kv: kv[1]))
    print('\n')

dictionairy()

lis = [{"name": "Taobao", "age": 100},
       {"name": "Runoob", "age": 7},
       {"name": "Google", "age": 100},
       {"name": "Wiki", "age": 200}]

# 通过 age 升序排序
print("列表通过 age 升序排序: ")
print(sorted(lis, key=lambda i: i['age']))

print("\r")

# 先按 age 排序，再按 name 排序
print("列表通过 age 和 name 排序: ")
print(sorted(lis, key=lambda i: (i['age'], i['name'])))

print("\r")

# 按 age 降序排序
print("列表通过 age 降序排序: ")
print(sorted(lis, key=lambda i: i['age'], reverse=True))

51. 计算字典值的和

def sumofdict(dic):
    sum = 0
    for i in dic:
        sum += dic[i]
    return sum

dict = {'a': 100, 'b':200, 'c':300}
print(sumofdict(dict))


def sumofdict(dic):
    sum = 0
    for item in dic.items():
        sum += item[1]
    return sum


dict = {'a': 100, 'b':200, 'c':300}
print(sumofdict(dict))

52. 移除字典中键值对

test_dict = {"Runoob" : 1, "Google" : 2, "Taobao" : 3, "Zhihu" : 4}

del test_dict['Zhihu']
# 移除没有的 key 会报错
#del test_dict['Baidu']


test_dict.pop('Taobao')
# 使用 pop() 移除没有的 key 不会发生异常，我们可以自定义提示信息
print(test_dict.pop("baidu", '没有该键'))
print(test_dict)

test_dict = {"Runoob" : 1, "Google" : 2, "Taobao" : 3, "Zhihu" : 4}
new_dict = {key:val for key, val in test_dict.items() if key != 'Zhihu'}
print(new_dict)

53. 合并字典

# 使用 update() 方法，第二个参数合并第一个参数
def merge(dict1, dict2):
    dict2.update(dict1)
    return dict2

dict1 = {'a': 10, 'b': 8}
dict2 = {'d': 6, 'c': 4}
print(merge(dict1, dict2))

# 使用 **，函数将参数以字典的形式导入
def merge(dict1, dict2):
    res = {**dict1, **dict2}
    return res

dict1 = {'a': 10, 'b': 8}
dict2 = {'d': 6, 'c': 4}
print(merge(dict1, dict2))

54. 将字符串的时间转成时间戳

import time
a1 = '2019-11-22 14:21:56'
timearray = time.strptime(a1, '%Y-%m-%d %H:%M:%S')
timestamp = int(time.mktime(timearray))
print(timestamp)

55. 获取几天前的时间

import time
import datetime

# 先获得时间数组格式的日期
threedayago = (datetime.datetime.now() - datetime.timedelta(days=3))
# 转换为时间戳
timesp = int(time.mktime(threedayago.timetuple()))
# 转换为其他字符串格式
otherStyleTime = threedayago.strftime("%Y-%m-%d %H:%M:%S")
print(otherStyleTime)


import time
import datetime

# 给定时间戳
timeStamp = 1557502800
dateArray = datetime.datetime.utcfromtimestamp(timeStamp)
threeDayAgo = dateArray - datetime.timedelta(days=3)
print(threeDayAgo)

56. 将时间戳转换指定格式的时间

import time
now = int(time.time())
timearray = time.localtime(now)
otherstyletime = time.strftime('%Y-%m-%d %H:%M:%S', timearray)
print(otherstyletime)


import datetime
now = datetime.datetime.now()
otherstyletime = now.strftime('%Y:%m:d %H:%M:%S')
print(otherstyletime)



import time
timesp = 1557502800
timearray = time.localtime(timesp)
otherstyletime = time.strftime('%Y-%m-%d %H:%M:%S',timearray)
print(otherstyletime)


import datetime
timesp = 1557502800
datearray = datetime.datetime.utcfromtimestamp(timesp)
otherstyletime = datearray.strftime('%Y:%m:%d %H:%M:%S')
print(otherstyletime)

57. 二分法查找

'''
二分搜索是一种在有序数组中查找某一特定元素的搜索算法。
搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；
如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。
如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半
'''


def binarySearch(arr, l, r, x):
    if r >= 1:
        mid = int((l + r) / 2)

        if (arr[mid] == x):
            return mid
        elif (arr[mid] > x):
            return binarySearch(arr, l, mid-1, x)
        else:
            return binarySearch(arr, mid+1, r, x)
    else:
        return -1


arr = [1, 2, 3, 4, 5, 100, 200, 300]
x = 100
print(binarySearch(arr, 0, len(arr)-1, x))

58. 线性查找

'''
线性查找指按一定的顺序检查数组中每一个元素，直到找到所要寻找的特定值为止
'''

def search(arr, n, x):
    for i in range(0, n):
        if (arr[i] == x):
            return i
    return -1

arr = [ 'A', 'B', 'C', 'D', 'E' ];
print(search(arr, len(arr), 'D'))

59. 插入排序

'''
插入排序（英语：Insertion Sort）是一种简单直观的排序算法。
它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入
'''

def insertionSort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i-1

        while j>=0 and key < arr[j]:
            arr[j+1] = arr[j]
            j -= 1
        arr[j+1] = key

arr = [12, 11, 13, 5, 6]
insertionSort(arr)
print(arr)

60. 快速排序

'''

快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为较小和较大的2个子序列，然后递归地排序两个子序列。

步骤为：

挑选基准值：从数列中挑出一个元素，称为"基准"（pivot）;
分割：重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（与基准值相等的数可以到任何一边）。
在这个分割结束之后，对基准值的排序就已经完成;
递归排序子序列：递归地将小于基准值元素的子序列和大于基准值元素的子序列排序。
递归到最底部的判断条件是数列的大小是零或一，此时该数列显然已经有序。

选取基准值有数种具体方法，此选取方法对排序的时间性能有决定性影响

'''


def partition(arr,low,high):
    i = low
    pivot = arr[high]
    for j in range(low, high):
        if arr[j] <= pivot:
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
    arr[i], arr[high] = arr[high], arr[i]

    return i

def quicksort(arr, low, high):
    if low < high:
        pi = partition(arr, low, high)

        quicksort(arr, low, pi-1)
        quicksort(arr, pi+1,high)

arr = [11,15,12,13,5,8,6]
quicksort(arr,0,len(arr)-1)
print(arr)


def quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr)//2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quicksort(left)+ middle + quicksort(right)
arr = [11,8,9,7,6,10,14,15,14]
print(quicksort(arr))

61. 选择排序

'''
选择排序（Selection sort）是一种简单直观的排序算法。
它的工作原理如下。
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，
然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
以此类推，直到所有元素均排序完毕


'''

def choosesort(arr):
    for i in range(len(arr)):
        min_idx = i
        for j in range(i+1, len(arr)):
            if arr[min_idx] > arr[j]:
                min_idx = j

        arr[i], arr[min_idx] = arr[min_idx], arr[i]


arr = [11, 5, 15, 12, 14, 13, 8, 5, 10]
choosesort(arr)
print(arr)

# 数据有重复时会有问题 不推荐
def choosesort2(arr):
    counter = 0
    array = []
    for x in arr:
        counter += 1
        for y in arr[counter:]:
            if x > y:
                x = y
            arr.remove(x)
            arr.insert(counter - 1, x)
        array.append(x)

arr = [11,15, 12, 14, 13, 8, 5, 10]

choosesort2(arr)
print(arr)

62. 冒泡排序

def bubblesort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]

arr = [52,18,56,77,15,122]
bubblesort(arr)
print(arr)

63. 归并排序

'''

归并排序（英语：Merge sort，或mergesort），是创建在归并操作上的一种有效的排序算法。
该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

分治法:

分割：递归地把当前序列平均分割成两半。
集成：在保持元素顺序的同时将上一步得到的子序列集成到一起（归并）

'''


def merge_sort(li):
    # 不断递归调用自己一直到拆分成成单个元素的时候就返回这个元素，不再拆分了
    if len(li) == 1:
        return li

    # 取拆分的中间位置
    mid = len(li) // 2

    # 拆分过后左右两侧子串
    left = li[:mid]
    right = li[mid:]

    # 对拆分过后的左右再拆分 一直到只有一个元素为止
    # 最后一次递归时候ll和lr都会接到一个元素的列表
    # 最后一次递归之前的ll和rl会接收到排好序的子序列
    ll = merge_sort(left)
    rl = merge_sort(right)

    # 我们对返回的两个拆分结果进行排序后合并再返回正确顺序的子列表
    # 这里我们调用拎一个函数帮助我们按顺序合并ll和lr
    return merge(ll, rl)

#这里接收两个列表
def merge( left , right ):
    # 从两个有顺序的列表里边依次取数据比较后放入result
    # 每次我们分别拿出两个列表中最小的数比较，把较小的放入result
    result = []
    while len(left)>0 and len(right)>0 :
        #为了保持稳定性，当遇到相等的时候优先把左侧的数放进结果列表，因为left本来也是大数列中比较靠左的
        if left[0] <= right[0]:
            result.append( left.pop(0) )
        else:
            result.append( right.pop(0) )
    #while循环出来之后 说明其中一个数组没有数据了，我们把另一个数组添加到结果数组后面
    result += left
    result += right
    return result


li = [4,3,2,1]
li2 = merge_sort(li)
print(li2)


def merge(arr, l, m, r):
    n1 = m - l + 1
    n2 = r - m

    # 创建临时数组
    L = [0] * (n1)
    R = [0] * (n2)

    # 拷贝数据到临时数组 arrays L[] 和 R[]
    for i in range(0, n1):
        L[i] = arr[l + i]

    for j in range(0, n2):
        R[j] = arr[m + 1 + j]

        # 归并临时数组到 arr[l..r]
    i = 0  # 初始化第一个子数组的索引
    j = 0  # 初始化第二个子数组的索引
    k = l  # 初始归并子数组的索引

    while i < n1 and j < n2:
        if L[i] <= R[j]:
            arr[k] = L[i]
            i += 1
        else:
            arr[k] = R[j]
            j += 1
        k += 1

    # 拷贝 L[] 的保留元素
    while i < n1:
        arr[k] = L[i]
        i += 1
        k += 1

    # 拷贝 R[] 的保留元素
    while j < n2:
        arr[k] = R[j]
        j += 1
        k += 1


def mergeSort(arr, l, r):
    if l < r:
        m = int((l + (r - 1)) / 2)

        mergeSort(arr, l, m)
        mergeSort(arr, m + 1, r)
        merge(arr, l, m, r)

arr = [12, 11, 13, 5, 6, 7]
mergeSort(arr, 0, len(arr)-1)
print (arr)

64. 堆排序

'''
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。
堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：
即子结点的键值或索引总是小于（或者大于）它的父节点。
堆排序可以说是一种利用堆的概念来排序的选择排序
'''

def heapify(arr, n, i):
    largest = i # 父节点
    l = 2 * i + 1  # left = 2*i + 1 左节点
    r = 2 * i + 2  # right = 2*i + 2 右节点

    if l < n and arr[i] < arr[l]:  # 存在左节点 且 左节点大于父节点
        largest = l

    if r < n and arr[largest] < arr[r]:  # 存在右节点 且 右节点大于最大节点
        largest = r

    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]  # 交换

        heapify(arr, n, largest)


def heapSort(arr):
    n = len(arr)

    # Build a maxheap 最大堆
    for i in range(n, -1, -1):
        heapify(arr, n, i)
    print (arr)

    # 一个个交换元素
    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]  # 交换
        heapify(arr, i, 0)


arr = [12, 11, 13, 15, 6, 7]
heapSort(arr)
print (arr)

65. 计数排序

'''
计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。
作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数

桶排序

'''

def countSort(arr):
    output = [0 for i in range(256)]

    count = [0 for i in range(256)]

    ans = ["" for _ in arr]

    for i in arr:
        count[ord(i)] += 1

    for i in range(256):
        count[i] += count[i - 1]

    for i in range(len(arr)):
        output[count[ord(arr[i])] - 1] = arr[i]
        count[ord(arr[i])] -= 1

    for i in range(len(arr)):
        ans[i] = output[i]
    return ans


arr = "wwwrunoobcom"
ans = countSort(arr)
print ("字符数组排序 %s" % ("".join(ans)))

66. 希尔排序

'''

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。
但希尔排序是非稳定排序算法。
希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，
待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序

'''

def shellSort(arr):
    n = len(arr)
    gap = int(n / 2)

    while gap > 0:

        for i in range(gap, n):

            temp = arr[i]
            j = i
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = temp
        gap = int(gap / 2)


arr = [12, 34, 54, 2, 3]
shellSort(arr)
print (arr)

67. 拓扑排序

'''

对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，
是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，
则u在线性序列中出现在v之前。
通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。
简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。
在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，
称为该图的一个拓扑排序（英语：Topological sorting）：

每个顶点出现且只出现一次；
若A在序列中排在B的前面，则在图中不存在从B到A的路径

'''

from collections import defaultdict


class Graph:
    def __init__(self, vertices):
        self.graph = defaultdict(list)
        self.V = vertices

    def addEdge(self, u, v):
        self.graph[u].append(v)

    def topologicalSortUtil(self, v, visited, stack):

        visited[v] = True

        for i in self.graph[v]:
            if visited[i] == False:
                self.topologicalSortUtil(i, visited, stack)

        stack.insert(0, v)

    def topologicalSort(self):
        visited = [False] * self.V
        stack = []

        for i in range(self.V):
            if visited[i] == False:
                self.topologicalSortUtil(i, visited, stack)

        print (stack)


g = Graph(6)
g.addEdge(5, 2);
g.addEdge(5, 0);
g.addEdge(4, 0);
g.addEdge(4, 1);
g.addEdge(2, 3);
g.addEdge(3, 1);

print ("拓扑排序结果：")
g.topologicalSort()