Python排序算法

作者: lvyz0207 | 来源:发表于2019-12-10 09:56 被阅读0次

Python排序算法有哪几种？
排序算法详细代码实现
python 排序算法
排序算法最强总结及其代码实现（Python/Java）
第三章：高级排序算法
python实现计数排序(CountSort)
python实现选择排序(SelectionSort)
Python一行代码实现快速排序
数据结构与算法 - 排序与搜索
<算法入门>快速理解7种排序算法 | python3

# 冒泡排序
list1 = [13,34,3,23,24,6,76,44,58,90]    # 平均时间复杂度是 n**2
def maopao_sort(list1):
    for i in range(len(list1)):
        for j in range(len(list1)-1-i):
            if list1[j] > list1[j+1]: 
                list1[j],list1[j+1] = list1[j+1],list1[j]
    print(list1)
maopao_sort(list1)

[3, 6, 13, 23, 24, 34, 44, 58, 76, 90]

# 选择排序 枚举选出最小得数
list1 = [13,34,3,23,24,6,76,44,58,90]

def select_sort(nums):              # 平均时间复杂度是 n**2
    """选择排序"""
    for i in range(0, len(nums)-1):
        min_index = i     # 假设找到的最小元素下标为j
        for j in range(i + 1, len(nums)):    # 寻找最小元素的过程
            if nums[min_index] > nums[j]:    # 假设最小下标的值，大于循环中一个元素，那么就改变最小值的下标
                min_index = j
        if i != min_index:       # 为了容错处理，因为循环一开始就假设把最小值的下标j赋值给变量min_index
            nums[min_index], nums[i] = nums[i], nums[min_index]
    print(nums)

select_sort(list1)

[3, 6, 13, 23, 24, 34, 44, 58, 76, 90]

# 插入排序
def insert_sort(raw_list):          # 平均时间复杂度是 n**2
    length = len(raw_list)
    for i in range(1, length):
        temp = raw_list[i]
        #j从i-1 到 0倒序
        for j in range(i-1,-1,-1):
            if(raw_list[j]<=temp):
                break
            if(raw_list[j]>temp):
                raw_list[j],raw_list[j+1] = temp,raw_list[j]
    return raw_list
#测试
data_test = [10,23,1,53,654,54,546,31]
insert_sort(data_test)

[1, 10, 23, 31, 53, 54, 546, 654]

# 希尔排序
def shell_sort(list):      # 平均空间复杂度为 O(nlogn)
    length=len(list)
    dist=length//2
    while dist>0:
        for i in range(dist,length):
            temp=list[i]
            j=i
            while j>=dist and temp<list[j-dist]:
                list[j]=list[j-dist]
                j-=dist
            list[j]=temp
        dist//=2
    return list

#测试
list1=[10,23,1,53,654,54,16,546,31]
print(shell_sort(list1))

# 快速排序法
def quickSort(nums):  # 这种写法的平均空间复杂度为 O(nlogn)
    if len(nums) <= 1:
        return nums
    pivot = nums[0]  # 基准值
    left = [nums[i] for i in range(1, len(nums)) if nums[i] < pivot] 
    right = [nums[i] for i in range(1, len(nums)) if nums[i] >= pivot]
    return quickSort(left) + [pivot] + quickSort(right)

nums=[10,23,1,53,654,54,16,646,546,31]
print(quickSort(nums))

# 顺序查找
import random

data = [0]*5
for i in range(len(data)):
    val = random.randint(1,900)
    data[i] = val
print(data)
time2 = 0
val = int(input("请输入要查找的数字："))
for i in range(len(data)):
    time2 += 1
    if data[i] == val:
        print("找到啦....")
        print("顺序查找循环了：{}".format(time2))
        
# 二分查找  针对有序列表
data = sorted(data)
def binary_sort(data, value):
    time = 0
    low, high = 0, len(data)-1
    while low <= high:
        time += 1
        mid = (low + high)//2
        if value < data[mid]:
            high = mid - 1
        elif value > data[mid]:
            low = mid + 1
        else:
            print("终于找到了{}".format(str(data[mid])))
            print("time1:{}".format(time))
            return mid
    return -1

# 插值查找法
# 插值的核心就是使用公式：
# value = (key - list[low])/(list[high] - list[low])

data = sorted(data)
def binary_sort_2(data, key):
    time = 0
    low, high = 0, len(data)-1
    while low <= high:
        time += 1
        mid = low + int((high-low)*(key-data[low])/(data[high]-data[low]))
        if key < data[mid]:
            high = mid - 1
        elif key > data[mid]:
            low = mid + 1
        else:
            print("终于找到了{}".format(str(data[mid])))
            print("time2:{}".format(time))
            return mid
    return -1

binary_sort(data, val)
binary_sort_2(data, val)

[38, 700, 722, 37, 229]
请输入要查找的数字：37
找到啦....
顺序查找循环了：4
终于找到了37
time1:2
终于找到了37
time2:1





0

import time
print(time.strftime("%Y-%m-%d %H:%M:%S", time.localtime()))


import datetime  
now_time = datetime.datetime.now().strftime("%Y-%m-%d %H:%M:%S")
week = datetime.datetime.now().isoweekday()
print(now_time,week)

2019-12-09 20:10:52
2019-12-09 20:10:52 1

import os  
  
def dirlist(path, allfile):  
    filelist =  os.listdir(path)  
  
    for filename in filelist:  
        filepath = os.path.join(path, filename)  
        if os.path.isdir(filepath):  
            dirlist(filepath, allfile)  
        else:  
            allfile.append(filepath)  
    return allfile  
  
print dirlist("/home/yuan/testdir", [])   
from glob import glob
from os import path
def dirlist(parent, allfile):
    pattern = path.join(parent, '*', '*.wav')
    return glob(pattern)

from selenium.webdriver.common.action_chains import ActionChains

import random 

print(random.randint(1,1000))

from functools import reduce
num = sum(range(1,101))
print(num)

num1 = reduce(lambda a,b:a+b,range(1,101))
print(num, num1)

a = {1:'a',2:'b'}
b = {2:'c', 3:'c',4:'e'}
new_dict = {**a, **b}
print(new_dict)

5050
5050 5050
{1: 'a', 2: 'c', 3: 'c', 4: 'e'}

# list1 = [1,2,3,2,5,7,3,1]
# # list1 = list(set(list1))
# # list1
# list2.sort(key=list1.index)
# list2
def square(x): 
    return x**2
list1 = [1,2,3,4,5]  
list2 = list(map(square, list1))
list2

[1, 4, 9, 16, 25]

import random

print(random.randint(0,1000) + random.random())

645.9586767872188

a = 3
assert a < 4, "断言失败"

assert a > 4, "二次断言失败"

---------------------------------------------------------------------------

AssertionError                            Traceback (most recent call last)

<ipython-input-65-9c77d7531463> in <module>
      2 assert a < 4, "断言失败"
      3 
----> 4 assert a > 4, "二次断言失败"


AssertionError: 二次断言失败

s = "ajldjlajfdljfddd"
s = list(set(s))
s.sort(reverse=False)
res = " ".join(s)
res

'adfjl'

import re
a = "not 404 found 张三 99 深圳"
list1 = a.split(" ")
print(list1)
res = re.findall('\d+|[a-zA-Z]+', a)
print(res)
for i in res:
    if i in list1:
        list1.remove(i)
new_str = ' '.join(list1)
print(new_str)

a = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
def fun(a):
    return a%2 == 1
list1 = filter(fun, a)
list1 = [i for i in list1]
print(list1)

[i for i in a if i%2==1]

['not', '404', 'found', '张三', '99', '深圳']
['not', '404', 'found', '99']
张三 深圳
[1, 3, 5, 7, 9]





[1, 3, 5, 7, 9]

a = [1,5,7,9]
b = [2,2,6,8]
a.extend(b)
a.sort(reverse=True)
print(a)

[9, 8, 7, 6, 5, 2, 2, 1]

try:
    b = 0
    if b == 0:
        raise Exception("分子不能为0")
    a = 12/b
    print(a)
    
except Exception as e:
    print(e)

分子不能为0

a = [1,2]
b = [3,4,5]
dict1 = list(zip(a,b))
print(dict1)

[(1, 3), (2, 4)]

a="张明 98分"
res = re.sub("\d+", "100",a)
print(res)
# 两位小数
a="%.02f"%1.3335
b = round(float(a),2)
b

张明 100分





1.3335

a = tuple(zip(["a","b","c","d","e"],[1,2,3,4,5]))
list1.sort()
foo = [-5,8,0,4,9,-4,-20,-2,8,2,-4]
a = sorted(foo, key=lambda x:(x<0,abs(x)))
b = sorted(foo, reverse=True, key=lambda x:x)
print(a, b)

foo1 = [{"name":"zs","age":19},{"name":"ll","age":54},{"name":"wa","age":17},{"name":"df","age":23}]
c = sorted(foo1, key=lambda x:x["age"], reverse=True)
print(c)

foo2 = [("ab",120),("cd",34),("ef",56),("gh",78)]
d = sorted(foo2, key=lambda x:x[1])
print(d)

foo3 = [["ab",120],["cd",34],["ef",34],["gh",78]]
e = sorted(foo3, key= lambda x:(x[1],x[0]))
print(e)

# 对字典进行排序
dic = {"name":"amani","sex":"man", "city":"beijing"}
foo4 = list(zip(dic.keys(),dic.values()))    # 字典转化为嵌套元组，在变为列表
f = sorted(foo4, key=lambda x:x[0])    # 对列表进行排序
new_dic = {i[0]:i[1] for i in f}
print(new_dic, dic.items()) 

g = sorted(dic.items(),key=lambda x:x[0]) # 将列表嵌套的元组 进行倒序
new_dic1 = {i[0]:i[1] for i in g}    # 构造新的字典
print(new_dic1)

[0, 2, 4, 8, 8, 9, -2, -4, -4, -5, -20] [9, 8, 8, 4, 2, 0, -2, -4, -4, -5, -20]
[{'name': 'll', 'age': 54}, {'name': 'df', 'age': 23}, {'name': 'zs', 'age': 19}, {'name': 'wa', 'age': 17}]
[('cd', 34), ('ef', 56), ('gh', 78), ('ab', 120)]
[['cd', 34], ['ef', 34], ['gh', 78], ['ab', 120]]
{'city': 'beijing', 'name': 'amani', 'sex': 'man'} dict_items([('name', 'amani'), ('sex', 'man'), ('city', 'beijing')])
{'city': 'beijing', 'name': 'amani', 'sex': 'man'}

for i in range(2):
    print(random.randint(8,9), end='\t')
    
s = ['abc','a','wert','hello']
b = sorted(s, key=lambda x:len(x))
print(b)

email_list = ["wangxiao001@163.com","qwer@123.com","1231231@gmail.com"]
for email in email_list:
    ret = re.match("[\w]{4,20}@163.com", email)
    print(email)
    if ret:
        print(email)
    else:
        print(1234)

8   9   ['a', 'abc', 'wert', 'hello']
wangxiao001@163.com
wangxiao001@163.com
qwer@123.com
1234
1231231@gmail.com
1234

# 递归求和
def get_sum(num):
    if num > 0:
        res = num + get_sum(num-1)
    else:
        res = 0
    return res
print(get_sum(9))

s = "info:xiaoZhang 33 shandong"
res1 = re.split(r":| ", s)
print(res1)

s = "<img href='https://adfb....jpg' src='https://abcd.jpg'>"
res1 = re.findall(r"https://.*?\.jpg",s)[0]
res2 = re.search(r"https://.*?\.jpg", s)
print(res1,res2.group())

45
['info', 'xiaoZhang', '33', 'shandong']
https://adfb....jpg https://adfb....jpg

a = "abcd"
b = a 

del a
# id(a)
id(b)
del b
# id(a)
# id(b)

import pandas as pd
file = pd.read_excel("/Users/lvyz/Downloads/测试.xlsx")
print(file)

a = (9 + 4)//2
print(a)

import os

def get_fullfile_from_path(path, ext=None):
    allfiles = []
    needExtFilter = (ext != None)
    for root, dirs, files in os.walk(path):
        print(os.walk(path))
        for filespath in files:
            filepath = os.path.join(root, filespath)
            print("root:{}".format(root))
            extension = os.path.splitext(filepath)[1][1:]
            if needExtFilter and extension in ext:
                allfiles.append(filepath)
            elif not needExtFilter:
                allfiles.append(filepath)
    return allfiles

def get_file_name_from_path(path, ext=None):
    allfilenames = []
    needExtFilter = (ext != None)
    for root, dirs, files in os.walk(path):
        for filespath in files:
            filename, suffix = os.path.splitext(filespath)
            extension = os.path.splitext(filespath)[1][1:]
            if needExtFilter and extension in ext:
                allfilenames.append(filename)
            elif not needExtFilter:
                allfilenames.append(filename)
    print(allfilenames)
    return allfilenames
get_file_name_from_path("/Users/lvyz/Documents/study/100Days")

['Day11', 'Day01', 'Day15', '致橡树', 'Day19_协程', 'Day05', 'Day20', 'Day22-MySQL', 'Day04', 'Day18_diedaiqi', 'Day10', '装饰器', 'python_os', 'Day07', 'Day13', 'Day03', 'Day12', 'Day21-selenium', 'Day02', 'Day16', 'Day06', 'Day09', 'Day08', 'Day23_interview']





['Day11',
 'Day01',
 'Day15',
 '致橡树',
 'Day19_协程',
 'Day05',
 'Day20',
 'Day22-MySQL',
 'Day04',
 'Day18_diedaiqi',
 'Day10',
 '装饰器',
 'python_os',
 'Day07',
 'Day13',
 'Day03',
 'Day12',
 'Day21-selenium',
 'Day02',
 'Day16',
 'Day06',
 'Day09',
 'Day08',
 'Day23_interview']

import time
time.localtime()
time.localtime(time.time()) 
time.strftime("%Y-%m-%d-%X",time.localtime())

time.ctime(time.time())
time.asctime(time.localtime())
time.strptime('2011-05-05 16:37:06', '%Y-%m-%d %X')

time.struct_time(tm_year=2011, tm_mon=5, tm_mday=5, tm_hour=16, tm_min=37, tm_sec=6, tm_wday=3, tm_yday=125, tm_isdst=-1)

import datetime
now = datetime.datetime.now()
now
datetime.datetime.now().strftime("%Y-%m-%d %X")
datetime.datetime.now().date()
datetime.date.today() + datetime.timedelta(days=1)

datetime.datetime.combine(datetime.date.today(), datetime.time.min)
datetime.datetime.combine(datetime.date.today(), datetime.time.max)


(datetime.datetime(2019,12,16,12,0,0) - datetime.datetime.now()).total_seconds()

62025.299816

import re

s = "小明年龄18岁，工资1200元"
res = re.search("\d+",s).group()
print("seach 结果：{}".format(res))

res = re.findall('\d+',s)
print("findall结果{}".format(res))

res = re.match("\d+",s).group()
print("match 结果：{}".format(res))

seach 结果：18
findall结果['18', '1200']



---------------------------------------------------------------------------

AttributeError                            Traceback (most recent call last)

<ipython-input-16-267a93161ca0> in <module>
      8 print("findall结果{}".format(res))
      9 
---> 10 res = re.match("\d+",s).group()
     11 print("match 结果：{}".format(res))


AttributeError: 'NoneType' object has no attribute 'group'

Python排序算法有哪几种？
python排序算法有哪些？python中常见的排序算法有：插入排序、选择排序、冒泡排序、快速排序、归并排序、希尔...
排序算法详细代码实现
算法分类算法时间复杂度选择排序插入排序 C++实现 Python实现冒泡排序 Python实现归并排序 ...
python 排序算法
文章概述介绍各大常用经典的排序算法和效率，以及python实现常用算法（冒泡排序，选择排序，快速排序，插入排序）...
排序算法最强总结及其代码实现（Python/Java）
前言本文总结了常用的全部排序算法，内容包括：排序算法的定义和思路排序算法的代码实现：Python和Java，...
第三章：高级排序算法
归并排序算法（mergeSort）算法思想：Python使用函数实现：自底向上的归并排序算法算法思想：Pyt...
python实现计数排序(CountSort)
python实现【计数排序】(CountSort) 算法原理及介绍计数排序不是基于比较的排序算法，其核心在于将输...
python实现选择排序(SelectionSort)
python实现【选择排序】算法原理及介绍选择排序(Selection-sort)是一种简单直观的排序算法。它...
Python一行代码实现快速排序
上期文章排序算法——（2）Python实现十大常用排序算法为大家介绍了十大常用排序算法的前五种（冒泡、选择、插入、...
数据结构与算法 - 排序与搜索
文章来源：数据结构与算法（Python）排序与搜索排序算法（英语：Sorting algorithm）是一种能将...
<算法入门>快速理解7种排序算法 | python3
算法是程序的灵魂,而排序算法是算法的入门经典,作者在此用python亲自实现了7种主流的排序算法,并做简短的说明...