威尼斯人线上娱乐

排序算法之low,常用排序算法

19 4月 , 2019  

1、冒泡排序

python之算法LOB三人组,pythonlob三人组

1、冒泡排序

    a、冒泡排序—-优化

         
倘诺冒泡排序中进行一趟而尚未调换,则列表已经是不改变状态,能够一向结账法

import random
from timewrap import *

@cal_time
def bubble_sort(li):
    for i in range(len(li) - 1):
        # i 表示趟数
        # 第 i 趟时: 无序区:(0,len(li) - i)
        for j in range(0, len(li) - i - 1):
            if li[j] > li[j+1]:
                li[j], li[j+1] = li[j+1], li[j]

@cal_time
def bubble_sort_2(li):      #冒泡排序优化
    for i in range(len(li) - 1):
        # i 表示趟数
        # 第 i 趟时: 无序区:(0,len(li) - i)
        change = False
        for j in range(0, len(li) - i - 1):
            if li[j] > li[j+1]:
                li[j], li[j+1] = li[j+1], li[j]
                change = True
        if not change:
            return

li = list(range(10000))
# random.shuffle(li)
# print(li)
bubble_sort_2(li)
print(li)

二、接纳排序

    a、一趟遍历记录最小的数,放到第二个职位;

    b、在一趟遍历记录剩余列表中细小的数,继续放置

import random
from timewrap import *

@cal_time
def select_sort(li):
    for i in range(len(li) - 1):
        # i 表示趟数,也表示无序区开始的位置
        min_loc = i   # 最小数的位置
        for j in range(i + 1, len(li)):
            if li[j] < li[min_loc]:
                min_loc = j
        li[i], li[min_loc] = li[min_loc], li[i]


li = list(range(10000))
random.shuffle(li)
print(li)
select_sort(li)
print(li)

3、插入排序

    a、列表被分为有序区和无序区多个部分,最初有序区唯有三个因素

    b、每一趟从冬天区采用二个要素,插入到有序区的3个岗位,直到冬日区变空

import random
from timewrap import *

@cal_time
def insert_sort(li):
    for i in range(1, len(li)):
        # i 表示无序区第一个数
        tmp = li[i] # 摸到的牌
        j = i - 1 # j 指向有序区最后位置
        while li[j] > tmp and j >= 0:
            #循环终止条件: 1. li[j] <= tmp; 2. j == -1
            li[j+1] = li[j]
            j -= 1
        li[j+1] = tmp


li = list(range(10000))
random.shuffle(li)
print(li)
insert_sort(li)
print(li)

 

一、冒泡排序 a、冒泡排序—-优化
假若冒泡排序中实施壹趟而从不交流,则列表已经是上行下效状态,可…

排序low B三人组

列表排序:将冬季列表形成有充列表

选择场景:各样榜单,各样表格,给二分法排序使用,给别的算法使用

输入无序列表,输出有序列表(升序或降序)

排序low B三人组

 目录

    a、冒泡排序—-优化

壹. 冒泡排序

率先,列表每多个相邻的数做比较,假设日前的数比前边的数大,那么交换那多个数

def bubble_sort(l1):
    for i in range(len(l1)-1):
        for j in range(len(l1)-i-1):
            if l1[j] > l1[j+1]:
                l1[j],l1[j+1]=l1[j+1],l1[j]

    return l1

冒泡排序的优化

假诺冒泡排序中施行壹趟而从未交流,则列表已经是板上钉钉状态,能够间接停止排序

def bubble_sort_1(l1):
    for i in range(len(l1)-1):
        flag=False

        for j in range(len(l1)-i-1):
            if l1[j] > l1[j+1]:
                l1[j],l1[j+1]=l1[j+1],l1[j]
                flag=True

        if not flag:
            return l1

一、冒泡排序

         
假诺冒泡排序中推行壹趟而从不沟通,则列表已经是有序状态,能够直接买单法

排序算法之low,常用排序算法。二. 选项排序

一趟遍历记录中型小型小的的数,放到第二个职责
再一趟遍历记录剩余列表中细小的数,继续放置

    def select_sort(l1):
        for i in range(len(l1)-1):
            mid=i

            for j in range(i+1,len(l1)):
                if l1[j] <l1[mid]:
                    mid=j

            l1[mid],l1[i]=l1[i],l1[mid]

        return l1

二、选用排序

import random
from timewrap import *

@cal_time
def bubble_sort(li):
    for i in range(len(li) - 1):
        # i 表示趟数
        # 第 i 趟时: 无序区:(0,len(li) - i)
        for j in range(0, len(li) - i - 1):
            if li[j] > li[j+1]:
                li[j], li[j+1] = li[j+1], li[j]

@cal_time
def bubble_sort_2(li):      #冒泡排序优化
    for i in range(len(li) - 1):
        # i 表示趟数
        # 第 i 趟时: 无序区:(0,len(li) - i)
        change = False
        for j in range(0, len(li) - i - 1):
            if li[j] > li[j+1]:
                li[j], li[j+1] = li[j+1], li[j]
                change = True
        if not change:
            return

li = list(range(10000))
# random.shuffle(li)
# print(li)
bubble_sort_2(li)
print(li)

三. 插入排序

列表被分有有序区和冬天区多少个部分.最初有序区只有一个成分

历次从严节区摘取贰个成分,插入到有序区的岗位,直到冬天区变空

诸如,最初时有二个冬天列表l壹=[5,7,4,6,3,1,2,9,8]威尼斯人线上娱乐 ,,其使用插入排序时的步调为:

1.取无序列表l1中的第一个元素5,放入另一个有序列表tmp中
2.取无序列表l1中的第二个元素7,因为7比5大,把7放入有序列表tmp的第二个位置
3.取无序列表l1中的第三个元素4,因为4比5小,所以把4放入到有序列表tmp的元素5的左边中,此时有序列表tmp为[4,5,7]
4.取l1中第四个元素6,因为6比5大,又比7小,把6放入到元素5和7之间,此时tmp变成了[4,5,6,7]
...
每次从无序区中选择一个元素,插入到有序区的某个位置,直到无序区变空

def insert_sort(li):
    for i in range(1, len(li)):
        tmp = li[i]
        j = i - 1       #手里最后一张
        while j>=0 and li[j]>tmp:
            li[j+1]=li[j]
            j = j-1
        li[j+1] = tmp

    return li   

叁、插入排序

2、选取排序

肆、连忙排序

    a、壹趟遍历记录最小的数,放到第贰个职分;

五、堆排序

    b、在一趟遍历记录剩余列表中细小的数,继续放置

六、归并排序

import random
from timewrap import *

@cal_time
def select_sort(li):
    for i in range(len(li) - 1):
        # i 表示趟数,也表示无序区开始的位置
        min_loc = i   # 最小数的位置
        for j in range(i + 1, len(li)):
            if li[j] < li[min_loc]:
                min_loc = j
        li[i], li[min_loc] = li[min_loc], li[i]


li = list(range(10000))
random.shuffle(li)
print(li)
select_sort(li)
print(li)

七、基数排序

三、插入排序

八、希尔排序

    a、列表被分成有序区和冬日区三个部分,最初有序区唯有1个要素

九、桶排序

    b、每一趟从冬日区选用多个成分,插入到有序区的1个地点,直到严节区变空

十、总结

import random
from timewrap import *

@cal_time
def insert_sort(li):
    for i in range(1, len(li)):
        # i 表示无序区第一个数
        tmp = li[i] # 摸到的牌
        j = i - 1 # j 指向有序区最后位置
        while li[j] > tmp and j >= 0:
            #循环终止条件: 1. li[j] <= tmp; 2. j == -1
            li[j+1] = li[j]
            j -= 1
        li[j+1] = tmp


li = list(range(10000))
random.shuffle(li)
print(li)
insert_sort(li)
print(li)

 

一、冒泡排序

一、思路:首先,列表每五个相邻的数十分的大小,假诺前方的比前面包车型地铁大,那么那多个数就交流地点。就好像冒泡同样

二、代码关键点:

  • 趟数:n-1趟
  • 无序区

三、图示表明:依次类推就会拿到排序结果。冒泡排序的成效依然比异常低的

威尼斯人线上娱乐 1威尼斯人线上娱乐 2威尼斯人线上娱乐 3

4、代码示例

威尼斯人线上娱乐 4威尼斯人线上娱乐 5

 1 import random
 2 def bubble_sort(li):
 3     for i in range(1,len(li)-1):  #i表示趟数
 4         print('第%s趟'%i,)
 5         for j in range(len(li)-i-1):  #第i趟时,无序区为:(0,len(li)-i)
 6             if li[j] > li[j+1]:
 7                 li[j],li[j+1] = li[j+1],li[j]
 8 
 9 def bubble_sort2(li):
10     '''代码优化
11     如果冒泡排序中执行一趟而没有交换,
12     则列表已经是有序状态,
13     可以直接结束算法。
14 '''
15     for i in range(1,len(li)-1):  #i表示趟数
16         change = False
17         for j in range(len(li)-i-1):  #第i趟时,无序区为:(0,len(li)-i)
18             if li[j] > li[j+1]:
19                 li[j],li[j+1] = li[j+1],li[j]
20                 change = True
21         if not change:
22             return
23 
24 li = list(range(10))
25 random.shuffle(li)
26 print(li)
27 bubble_sort(li)
28 print(li)

冒泡排序

 

岁月复杂度:O(n二)

二、采用排序

一、思路:一趟遍历完笔录最小的数,放到第五个职位;在壹趟遍历记录剩余列表中的最小的数,继续放置

2、代码关键点:

  • 无序区
  • 小小的数的职分

三、难点:怎么选出最小的数?

威尼斯人线上娱乐 6威尼斯人线上娱乐 7

 1 import random
 2 def select_sort(li):
 3     for i in range(len(li)-1):
 4         #i 表示躺数,也表示无序区开始的位置
 5         min_loc = i  #最小数的位置
 6         for j in range(i+1,len(li)):  #i  ,i+1,就是后一个位置的范围
 7             # [9, 2, 1, 6, 5, 8, 3, 0, 7, 4]
 8             # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
 9             if li[j] <li[min_loc]:  #两个位置进行比较,如果后面的一个比最小的那个位置还小,说明就找到最小的了
10                 min_loc = j   #找到最小的位置
11         li[i],li[min_loc] = li[min_loc],li[i]  #吧找到的两个值进行互换位置
12 li = list(range(10))
13 random.shuffle(li)
14 print(li)
15 select_sort(li)
16 print(li)

挑选排序

 四、时间复杂度:O(n2)

3、插入排序

一、思路:成分被分成有序区和冬天区两片段。最初有序区唯有叁个因素。每一回从冬日区中精选一个要素,插入到有序区的岗位,直到冬辰区变空。

二、代码关键点:

  • 摸到的牌
  • 手里的牌

3、图示表明

威尼斯人线上娱乐 8

威尼斯人线上娱乐 9

插入后:

威尼斯人线上娱乐 10

威尼斯人线上娱乐 11

威尼斯人线上娱乐 12

四、代码示例

威尼斯人线上娱乐 13威尼斯人线上娱乐 14

 1 import random
 2 def insert_sort(li):
 3     for i in range(1,len(li)):
 4         #i 表示无序区的第一个数
 5         tmp = li[i]  #摸到的牌
 6         j = i-1 #指向有序区最后一个位置
 7         while li[j] >tmp and j>=0:
 8             #循环终止条件 li[j]<=tmp  and j==-1
 9             li[j+1] = li[j]  #向后移动
10             j-=1
11         li[j+1] = tmp
12         
13 li = list(range(10))
14 random.shuffle(li)
15 print(li)
16 insert_sort(li)
17 print(li)

插入排序

肆、飞快排序

一、思路:①、取五个成分p(第三个要素),是成分p归位(去它该去的地方);

     2、列表被p分成两有个别,左侧的都比p小,左侧的都比p大;

     三、递归完毕排序

贰、算法关键点

  • 归位
  • 递归

3、图示表明

威尼斯人线上娱乐 15

威尼斯人线上娱乐 16

威尼斯人线上娱乐 17

肆、怎么归并呢?先把5收取来,这时候就会有一个空位,从左边找比第五小学的数填充过来,以后左边有三个空位了,从左边找比5大的放到右侧的空位上。依次类推,

只要left和right碰在一齐,那样就找打五的岗位了

如图示:

图一威尼斯人线上娱乐 18图二威尼斯人线上娱乐 19

 图三威尼斯人线上娱乐 20图四威尼斯人线上娱乐 21

 那样在把找到的5的地方放进去去ok了

威尼斯人线上娱乐 22

伍、代码示例

威尼斯人线上娱乐 23威尼斯人线上娱乐 24

 1 import time
 2 def wrapper(func):
 3     def inner(*args,**kwargs):
 4         start = time.time()
 5         ret = func(*args,**kwargs)
 6         end = time.time()
 7         print('%s running time :%s'%(func.__name__,start-end))
 8         return ret
 9     return inner
10 
11 
12 def partition(li,left,right):
13     '''归位函数'''
14     tmp = li[left]  #先把5取出来
15     while left < right:
16         while left < right and li[right] >= tmp:  #如果降序排列修改li[right] <= tmp
17                 right -= 1 #从右边找比5小的数,填充到5的位置
18         li[left] = li[right]
19         while left < right and li[left] <= tmp:  #如果降序排列修改li[right] >= tmp
20                 left += 1# 从左边找比5大的数字放在右边的空位
21         li[right] = li[left]
22     li[left] = tmp  #当跳出循环条件的时候说明找到了,并且把拿出来的5在放进去
23     return left
24 
25 
26 def _quick_sort(li,left,right):
27     '''快速排序的两个关键点:归位,递归'''
28     if left < right:  #至少有两个元素,才能进行递归
29         mid = partition(li,left,right)  #找到归位的位置
30         _quick_sort(li,left,mid-1)  #递归,右边的-1
31         _quick_sort(li,mid+1,right) #递归,左边的+1
32 
33 @wrapper
34 def quick_sort(li):
35     return _quick_sort(li, 0, len(li)-1)
36 
37 @wrapper
38 def sys_sort(li):
39     '''系统排序'''
40     li.sort()
41 
42 import random
43 li = list(range(100000))
44 random.shuffle(li)
45 # print(li)
46 quick_sort(li)
47 # print(li)
48 
49 sys_sort(li)  
50 
51 #结论:系统的排序要比快排的时间快的多
52 # quick_sort running time :-0.6240355968475342
53 # sys_sort running time :-0.002000093460083008

急速排序算法

陆、迅速排序的时日复杂度O(nlogn)

五、堆排序

有关对的询问:

壹、堆排序进程:

  • 1、建立堆
  • 2、获得堆顶成分,为最大因素
  • 3、去掉堆顶,将堆最后二个要素放在堆顶,此时可通过一遍调控重新使堆有序
  • 4、堆顶成分为第2大成分
  • 5、重复步骤三,直到堆变空

代码示例

威尼斯人线上娱乐 25威尼斯人线上娱乐 26

 1 import random
 2 
 3 def _sift(li, low, high):
 4     """
 5     :param li:
 6     :param low: 堆根节点的位置
 7     :param high: 堆最有一个节点的位置
 8     :return:
 9     """
10     i = low  # 父亲的位置
11     j = 2 * i + 1  # 孩子的位置
12     tmp = li[low]  # 原省长
13     while j <= high:
14         if j + 1 <= high and li[j + 1] > li[j]:  # 如果右孩子存在并且右孩子更大
15             j += 1
16         if tmp < li[j]:  # 如果原省长比孩子小
17             li[i] = li[j]  # 把孩子向上移动一层
18             i = j
19             j = 2 * i + 1
20         else:
21             li[i] = tmp  # 省长放到对应的位置上(干部)
22             break
23     else:
24         li[i] = tmp  # 省长放到对应的位置上(村民/叶子节点)
25 
26 
27 def sift(li, low, high):
28     """
29     :param li:
30     :param low: 堆根节点的位置
31     :param high: 堆最有一个节点的位置
32     :return:
33     """
34     i = low         # 父亲的位置
35     j = 2 * i + 1   # 孩子的位置
36     tmp = li[low]   # 原省长
37     while j <= high:
38         if j + 1 <= high and li[j+1] > li[j]: # 如果右孩子存在并且右孩子更大
39             j += 1
40         if tmp < li[j]: # 如果原省长比孩子小
41             li[i] = li[j]  # 把孩子向上移动一层
42             i = j
43             j = 2 * i + 1
44         else:
45             break
46     li[i] = tmp
47 
48 
49 
50 def heap_sort(li):
51     n = len(li)
52     # 1. 建堆
53     for i in range(n//2-1, -1, -1):
54         sift(li, i, n-1)
55     # 2. 挨个出数
56     for j in range(n-1, -1, -1):    # j表示堆最后一个元素的位置
57         li[0], li[j] = li[j], li[0]
58         # 堆的大小少了一个元素 (j-1)
59         sift(li, 0, j-1)
60 
61 
62 li = list(range(10))
63 random.shuffle(li)
64 print(li)
65 heap_sort(li)
66 print(li)
67 
68 # li=[2,9,7,8,5,0,1,6,4,3]
69 # sift(li, 0, len(li)-1)
70 # print(li)

堆排序

陆、归并排序

①旦以后的列表分两段有序,如何将其合成为一个静止列表。那种操作称为二次归并

威尼斯人线上娱乐 27

1、思路:

二、归并关键字

威尼斯人线上娱乐 28

  • 解说:将列表越分越小,直至分成三个因素
  • 甘休条件:2个因素是一成不改变的
  • 合并:将七个有体系表归并,列表更大

叁、图实示例:

4、代码示例:

威尼斯人线上娱乐 29威尼斯人线上娱乐 30

 1 import random
 2 def merge(li, low, mid, high):
 3     # 一次归并
 4     '''
 5     :param li: 列表
 6     :param low: 起始位置
 7     :param mid: 按照那个位置分
 8     :param high: 最后位置
 9     :return:
10     '''
11     i = low
12     j = mid + 1
13     ltmp = []
14     while i <= mid and j <= high:
15         if li[i] < li[j]:
16             ltmp.append(li[i])
17             i += 1
18         else:
19             ltmp.append(li[j])
20             j += 1
21     while i <= mid:
22         ltmp.append(li[i])
23         i += 1
24     while j <= high:
25         ltmp.append(li[j])
26         j += 1
27     li[low:high+1] = ltmp
28 
29 
30 def _merge_sort(li, low, high):
31     if low < high:  # 至少两个元素
32         mid = (low + high) // 2
33         _merge_sort(li, low, mid)
34         _merge_sort(li, mid+1, high)
35         merge(li, low, mid, high)
36         print(li[low:high+1])
37 
38 
39 def merge_sort(li):
40     return _merge_sort(li, 0, len(li)-1)
41 
42 
43 li = list(range(16))
44 random.shuffle(li)
45 print(li)
46 merge_sort(li)
47 
48 print(li)

归并排序

5、归并排序的岁月复杂度:O(nlogn),空间复杂度是:O(n)

总结:

LOw B 三人组

  • 冒泡排序,选拔排序,直接插入排序他们的日子复杂度都是O(n^二),空间复杂度是O(一)

NB 三人组

  • 火速排序,归并排序,堆排序他们的年月复杂度都以O(nlogn)
  • 三种排序算法的短处
    • 高效排序:极端情状下排序作用低
    • 归并排序:必要相当的内部存款和储蓄器开支
    • 堆排序:在快的排序算法中相对非常慢

威尼斯人线上娱乐 31

挨着换的喜逐颜开,不挨着换的不安宁

 


相关文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图