常见排序算法心得-侏儒,快速,冒泡,选择

作者: RevinDuan | 来源:发表于2018-09-07 14:00 被阅读0次

几种算法实例

-- 记录了几种比较常用的算法,具体的也参考了很多文章,下面是我自己记录.侏儒 ,冒泡,选择,插入,快速排序,归并排序

首先我们介绍一个测试时间的利器,通常情况我们会使用time包来测试,但是只能测试总共的时间,而这个cProfile能测试具体步骤的时间,可以看得非常清楚瓶颈在哪里.

import cProfile   #测试间的利器

def add(a,b):
    return a+b

def for_func():
    result = 0
    for i in range(1000000):
        result += i 
    return result

def main(a,b):
    print 'this is the result for a + b'
    result = add(a,b)
    print result
    print 'test for function'
    print for_func()

cProfile.run('main(1,2)')

this is the result for a + b
3
test for function
499999500000
         115 function calls in 0.144 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.000    0.000 <ipython-input-56-3130e18dd725>:1(add)
        1    0.114    0.114    0.143    0.143 <ipython-input-57-827e3096c393>:1(for_func)
        1    0.000    0.000    0.144    0.144 <ipython-input-58-19c5a6c13393>:1(main)
        1    0.000    0.000    0.144    0.144 <string>:1(<module>)
        9    0.001    0.000    0.001    0.000 iostream.py:180(schedule)
        8    0.000    0.000    0.000    0.000 iostream.py:284(_is_master_process)
        8    0.000    0.000    0.000    0.000 iostream.py:297(_schedule_flush)
        8    0.000    0.000    0.001    0.000 iostream.py:342(write)
        9    0.000    0.000    0.000    0.000 iostream.py:87(_event_pipe)
        9    0.000    0.000    0.000    0.000 threading.py:570(isSet)
        9    0.000    0.000    0.000    0.000 threading.py:986(isAlive)
        8    0.000    0.000    0.000    0.000 utf_8.py:15(decode)
        8    0.000    0.000    0.000    0.000 {_codecs.utf_8_decode}
        8    0.000    0.000    0.000    0.000 {isinstance}
        8    0.000    0.000    0.000    0.000 {method 'decode' of 'str' objects}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
        8    0.000    0.000    0.000    0.000 {nt.getpid}
        9    0.000    0.000    0.000    0.000 {nt.urandom}
        1    0.029    0.029    0.029    0.029 {range}

# 这个表示正无穷,同理-inf表示负无穷,下面我们会用到
float('inf')

inf

侏儒排序法

从第一个数字开始和前面的进行比较,如果小于前面的数字就交换位置然后将指针减少1然后继续循环检测下一个. 最后的结果就是讲最小的移到第一位,然后从第一位在开始往后就像在纸上来回画直线一样每次将最小的数字放到最前面然后从最前面依次往后检测,知道在找到满足条件的再次将数字移到前面.

seq = [5,4,3,2,1]

def gnomesort(seq):
    i = 0 
    while i <len(seq):
        if i == 0 or seq[i-1] <= seq[i]:
            i += 1
        else:
            seq[i-1], seq[i] = seq[i], seq[i-1]
            i -= 1
    return seq

gnomesort(seq)

[1, 2, 3, 4, 5]

插入排序

从第一个开始,用这个数字和之前的每一个数字进行比较直到比他前一个数字小为止,那么这个数字的位置就可以确定了-放到他的前面.当然这个排序是从index = 0 开始的.

seq = [5,4,3,2,1]

# 递归版插入排序
def ins_sort_rec(seq,i):
    '''
    递归是从最低层开始排序的也就是从索引为0的地方开始排序的
    seq 是一个列表,i是列表的长度减1,也就是最后一个元素索引的位置.返回一个排序好的列表
    '''
    if i == 0:return seq
    ins_sort_rec(seq,i-1)   # 这个递归的使用可以理解为替换,将函数替换为这个函数的除去函数体的其他部分.
    j = i 
    while j > 0 and seq[j-1]> seq[j]:
        seq[j-1],seq[j] = seq[j],seq[j-1]
        j -= 1
    return seq

ins_sort_rec(seq,len(seq)-1)

[1, 2, 3, 4, 5]

# 插入排序 普通版
def ins_sort_nor(seq,i):
    '''seq 是一个列表,i是列表长度-1,这里用这个数字和他前一个数字进行比较如果小于就互换位置,互换后继续检查和前一个的大小比较,直到小于位置.
    '''
    for x in range(0,i):
        while x > 0 and seq[x-1] > seq[x]:
            seq[x-1],seq[x] = seq[x], seq[x-1]
            x -= 1
    return seq

ins_sort_nor(seq,len(seq)-1)

[1, 2, 3, 4, 5]

选择排序

选择排序:第一次将最大的放到最后,然后将剩下的所有中最大的放到最后,依次放到最后一个.

这个排序是从数列的最后一位开始的.

seq = [5,4,3,2,1]

# 递归版选择排序
def sel_sort_res(seq,i):
    if i == 0: return seq
    max_j = i 
    for x in range(i):
        if seq[x] > seq[max_j]:
            seq[x],seq[max_j] = seq[max_j],seq[x]
    return sel_sort_res(seq,i-1)

sel_sort_res(seq,len(seq)-1)

[1, 2, 3, 4, 5]

def sel_sort_nor(seq):
    for i in range(len(seq)-1,0,-1):
        max_j = i 
        for j in range(i):
            if seq[j] >seq[max_j]:max_j = j
        seq[i],seq[max_j] = seq[max_j],seq[i]
    return seq

sel_sort_nor([2,4,1])

[1, 2, 4]

快速排序

快速排序的逻辑是: 每次选中一个参考值,然后把大于参考值的放到右边小于参考值的放到左边,这样就可以确定参考值的位置,每次确定一个参考值的位置,循环往复就可以逐步确认每个数字的位置了

def QuickSort(myList,start,end):
    #判断low是否小于high,如果为false,直接返回
    if start < end:
        i,j = start,end
        #设置基准数
        base = myList[i]  

        while i < j:  
            #如果列表后边的数,比基准数大或相等,则前移一位直到有比基准数小的数出现
            while (i < j) and (myList[j] >= base):  
                j = j - 1  

            #如找到,则把第j个元素赋值给第个元素i,此时表中i,j个元素相等
            myList[i] = myList[j]

            #同样的方式比较前半区
            while (i < j) and (myList[i] <= base):
                i = i + 1
            myList[j] = myList[i]
        #做完第一轮比较之后,列表被分成了两个半区,并且i=j,需要将这个数设置回base
        myList[i] = base

        #递归前后半区
        QuickSort(myList, start, i - 1)
        QuickSort(myList, j + 1, end)
    return myList


myList = [49,38,65,97,76,13,27,49]
print("Quick Sort: ")
QuickSort(myList,0,len(myList)-1)
print(myList)

Quick Sort: 
[13, 27, 38, 49, 49, 65, 76, 97]

# 快速排序
def quick_sort(seq,start,end):
    if i < j: 
        i,j = start,end
        base = seq[i]
        while i <j:
            while i < j and seq[j] >= base:
                j -= 1
            seq[i] = seq[j]
            while i < j and seq[i] <= base:
                i += 1
            seq[j] = seq[i]
        seq[i] = base
    
    quick_sort(seq,start, i -1)
    quick_sort(seq,j+1,end)
    
    return seq

myList = [49,38,65,97,76,13,27,49]
print("Quick Sort: ")
quick_sort(myList,0,len(myList)-1)
print(myList)

Quick Sort: 
[13, 27, 38, 49, 49, 65, 76, 97]

冒泡排序

def bubble_sort(seq,order=1):
    end = len(seq)-1
    for x in range(end,0,-1):
        for y in range(x):
            if order == 1:
                if seq[y] > seq[y+1]:
                    seq[y],seq[y+1] = seq[y+1],seq[y]
            
    return seq

alist = [4,3,2,1,5,7,4,5,4,3,2,4,5,6,7,78,87,6,54,3,3]
bubble_sort(alist)

[1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 6, 6, 7, 7, 54, 78, 87]

这个算法中,最好的时间复杂度是 n, 最差的时间复杂度是n**2 所以是时间复杂度应该介于这两者之间

归并排序法

def mergesort(seq):
    mid = len(seq)//2
    lft, rgt = seq[:mid],seq[mid:]
    if len(lft) > 1 : lft = mergesort(lft)
    if len(rgt) > 1 : rgt = mergesort(rgt)
    res = []
    while lft and rgt:
        if lft[-1] >= rgt[-1]:
            res.append(lft.pop())
        else:
            res.append(rgt.pop())
    res.reverse()
    return (lft or rgt) + res

如何从某一个数字列表中找出彼此最接近但是不相等的两个数:

思路: 找出两个数字的绝对差最小,两次遍历整个列表,两个数的差值比较如果比上一个小那么就取用这个差值和这两个数字

alist = [1,2,5,3,5,3.122,12,23.43,79,4,8.1,8.12]

dd = float('inf')
for x in alist:
    for y in alist:
        if x == y : continue
        d = abs(x - y)
        if d < dd:
            xx, yy,dd = x, y,d

xx,yy  # 对于这个算法来说,时间复杂度是平方级的

(8.1, 8.12)

如果使用排序好的列表进行排序速度将会提高

newlist = sorted(alist)  # 如果使用list.sort() 方法那么原本的list的排序就会改变慎用

i = 0
dd = float('inf')
while i < len(newlist)-1:
    if newlist[i] == newlist[i+1]: 
        i +=1
    else:
        d = abs(newlist[i] - newlist[i+1])
        if d < dd:
            x,y,dd = newlist[i],newlist[i+1],d
        i += 1
x,y

(1, 2)

几种排序的思想以及方法

冒泡算法思想：

每次相邻元素进行比较，如果发现较小的元素在后面，就交换两个相邻的元素,每次循环都将最大是数据排列到结尾处.

选择排序算法思想：

在冒泡排序上做了优化，减少了交换次数，在首轮选择最大的数放在第一项，一轮之后第一项是有序的了，第二轮从第二项开始选择最大的数放在第二项，以此类推，直到整个数组完全有序

插入排序算法思想：

和前俩种排序不同，插入排序在排序过程中是局部有序，随着插入项的增多，有序部分的项的位置会发生改变，而冒泡排序和选择排序每轮确定的项数的位置是永远不变的。在首轮，选择第二项作为插入项，然后取出这一项放在一个变量中，和前一项比较而且小，则前一项后移到第二项的位置，然后第二项也就是插入项放在前一项的位置，第二轮选择第三项作为插入项然后取出和前一项也就是第二项比较如果小，第二项后移到插入项，然后插入相在和第一项比较如果小，则第一项后移到第二项，插入项放在第一项，以此类推。

总结：

冒泡算法，每次比较如果发现较大的元素在后面，就交换两个相邻的元素。而选择排序算法的改进在于：先并不急于调换位置，先从Aarray[0]开始逐个检查，看哪个数最大就记下该数所在的位置j，等一躺扫描完毕，再把Arraymax和A[0]对调，这时Array[0]到Array[6]中最大的数据就换到了最前面的位置。所以，选择排序每扫描一遍数组，只需要一次真正的交换，而冒泡可能需要很多次，比较的次数是一样的。插入排序算法比冒泡快一倍，比选择排序略快一点

seq = [7,5,3,56,7,8,3,12,2]

# 冒泡排序
def bubble_sort(seq):
    # 索引的位置
    i = len(seq)-1
    for x in range(i,0,-1):
        for y in range(x):
            if seq[y]<seq[y+1] :
                seq[y+1] , seq[y] = seq[y] ,seq[y+1]
    return seq

bubble_sort(seq)

[56, 12, 8, 7, 7, 5, 3, 3, 2]

seq

[7, 7, 7, 7, 7, 7, 7, 12, 12]

# 侏儒算法
def gon_sort(seq,end):
    i = 0
    while i < end:
        if  i == 0 or seq[i-1] <= seq[i]:
            i += 1
        else:
            seq[i-1],seq[i] = seq[i],seq[i-1]
            i -= 1
    return seq

seq = [7,5,3,56,7,8,3,12,2,5,3,21,6]
end = len(seq)
gon_sort(seq,end)

[2, 3, 3, 3, 5, 5, 6, 7, 7, 8, 12, 21, 56]

def quick_sort(seq,start,end):
    if start < end:
        i,j = start,end
        base = seq[i]
        while i < j:
            while i < j and seq[j] >= base:
                j -= 1
            seq[i] = seq[j]
            while i < j and seq[i] <= base:
                i += 1
            seq[j] = seq[i] 
        seq[i] = base
        
        quick_sort(seq,start,i-1)
        
        quick_sort(seq,j+1,end)
    return seq

seq = [7,5,3,56,7,8,3,12,2,5,3,21,6]
start = 0
end = len(seq)-1
quick_sort(seq,start,end)

[2, 3, 3, 3, 5, 5, 6, 7, 7, 8, 12, 21, 56]

def select_sort(seq,end):
    for x in range(end,0,-1):
        max_j = end 
        for y in range(x):
            if seq[y]>seq[max_j]: max_j = y