当前位置:   article > 正文

2-基本算法-6种排序排序+二分法查找

冒泡排序 顺序排序 二分法排序

!!!认真学习,争取拿下Offer!!!

-------------------------------------进入学习模式---------------------------------------

常见的排序算法效率的比较:

排序方法

平均情况

最好

最坏

辅助空间

稳定性

冒泡

o(n^2)

o(n)

o(n^2)

o(1)

选择

o(n^2)

o(n^2)

o(n^2)

o(1)

×

插入

o(n^2)

o(n)

o(n^2)

o(1)

希尔

o(nlogn)- o(n^2)

o(n^1.3)

o(n^2)

o(1)

×

o(nlogn)

o(nlogn)

o(nlogn)

o(1)

×

归并

o(nlogn)

o(nlogn)

o(nlogn)

o(n)

快速【考的最多】

o(nlogn)

o(nlogn)

o(n^2)

o(logn)- o(n)

一、冒泡排序

1、基本思想:两个数比较大小,较大的数下沉,较小的数冒起来。

2、过程:

(1)比较相邻的两个数据,如果第二个数小,就交换位置。

(2)从后向前两两比较,一直到比较最前两个数据。最终最小数被交换到起始的位置,这样第一个最小数的位置就排好了。

(3)继续重复上述过程,依次将第2.3...n-1个最小数排好位置。

2c253f7d8305b69b96f38ef37c4127349da.jpg

3、平均时间复杂度:o(n^2)

4python代码:

"""冒泡排序:每个元素都比较一遍,进行冒泡比较【从小到大】
最优时间复杂度:o(n)    最坏时间复杂度:o(n^2)    稳定性:稳定"""
def bubble_sort(alist):
    n=len(alist)
    for j in range(n-1):
        for i in range(n-j-1):
            if alist[i]>alist[i+1]:
                alist[i],alist[i+1]=alist[i+1],alist[i]
    return alist
print(bubble_sort([5,2,8,7,1,3,4]))  #[1, 2, 3, 4, 5, 7, 8]

5、优化:

(1)针对问题:

数据的顺序排好之后,冒泡算法仍然会继续进行下一轮的比较,直到n-1次,后面的比较没有意义

(2)方案:

设置标志位flag,如果发生了交换flag设置为true;如果没有交换就设置为false。

这样当一轮比较结束后如果flag仍为false,即:这一轮没有发生交换,说明数据的顺序已经排好,没有必要继续进行下去。

def bubble_sort(alist):
    n=len(alist)
    for j in range(n-1):
        flag=False
        for i in range(n-j-1):
            if alist[i]>alist[i+1]:
                alist[i],alist[i+1]=alist[i+1],alist[i]
                flag=True
        if flag==False:
            break
    return alist
print(bubble_sort([5,2,8,7,1,3,4]))  #[1, 2, 3, 4, 5, 7, 8]

二、选择排序

1、基本思想:
(1)在长度为N的无序数组中,第一次遍历n-1个数,找到最小的数值与第一个元素交换;
(2)第二次遍历n-2个数,找到最小的数值与第二个元素交换;………………………………….
(3)第n-1次遍历,找到最小的数值与第n-1个元素交换,排序完成。

2、过程:

7e86a8d1583f3cd2482acd23c1477d3cab1.jpg

3、平均时间复杂度:o(n2)

4python代码

"""选择排序:始终从无序的列表中选择最小的往前面放【从小到大】
最优时间复杂度:o(n^2)    最坏时间复杂度:o(n^2)    稳定性:不稳定"""
def select_sort(alist):
    n=len(alist)
    for j in range(n-1):
        min_index=j
        for i in range(j+1,n):
            if alist[min_index]>alist[i]:
                min_index=i
        alist[j],alist[min_index]=alist[min_index],alist[j]
    return alist
print(select_sort([2,4,1,3,8,7,6]))  #[1, 2, 3, 4, 6, 7, 8]

三、插入排序

1、基本思想:
在要排序的一组数中,假定前n-1个数已经排好序,现在将第n个数插到前面的有序数列中,使得这n个数也是排好顺序的。如此反复循环,直到全部排好顺序。

2、过程:【有点像打牌

482fae832701d38ce8e24ae350463699461.jpg0d8dc09128012e4a00b21cdc1a072c218ae.jpg

3、平均时间复杂度:o(n2)

4python代码

"""插入排序:每次把最小的插入到第一个【从小到大】
最优时间复杂度:o(n)    最坏时间复杂度:o(n^2)    稳定性:稳定"""
def insert_sort(alist):
    n=len(alist)
    for j in range(1,n):
        i=j
        while i>0:
            if alist[i]<alist[i-1]:
                alist[i],alist[i-1]=alist[i-1],alist[i]
                i-=1
            else:
                break
    return alist
print(insert_sort([3,5,56,2,1,7,8]))  #[1, 2, 3, 5, 7, 8, 56]

四、希尔排序

1、前言:
数据序列1: 13-17-20-42-28 利用插入排序,13-17-20-28-42. Number of swap:1;
数据序列2: 13-17-20-42-14 利用插入排序,13-14-17-20-42. Number of swap:3;
如果数据序列基本有序,使用插入排序会更加高效。

2、基本思想:
在要排序的一组数中,根据某一增量分为若干子序列,并对子序列分别进行插入排序。
然后逐渐将增量减小,并重复上述过程。直至增量为1,此时数据序列基本有序,最后进行插入排序。

3、过程:

0318e0b55d027fab44ca0e2303b701da694.jpg

3、平均时间复杂度:o(n^1.3)    【其时间复杂度与选择的步长有关】

4python代码

"""希尔排序:插入排序的改进,增加一个gap(步长)【从小到大】
最优时间复杂度:根据gap的不同而不同    最坏时间复杂度:o(n^2)    稳定性:不稳定"""
def shell_sort(alist):
    n=len(alist)
    gap=n//2
    while gap>=1:
        for j in range(gap,n):
            i=j
            while i>0:
                if alist[i]<alist[i-1]:
                    alist[i],alist[i-1]=alist[i-1],alist[i]
                    i-=gap
                else:
                    break
        gap//=2
    return alist
print(shell_sort([3,5,56,2,1,7,8]))  #[1, 2, 3, 5, 7, 8, 56]

五、快速排序

1、基本思想:(分治)

(1)先从数列中取出一个数作为key值;

(2)将比这个数小的数全部放在它的左边,大于或等于它的数全部放在它的右边;

(3)对左右两个小数列重复第二步,直至各区间只有1个数。

2、辅助理解:挖坑填数

(1)初始时 i = 0; j = 9; key=72

由于已经将a[0]中的数保存到key中,可以理解成在数组a[0]上挖了个坑,可以将其它数据填充到这来。

从j开始向前找一个比key小的数。当j=8,符合条件,a[0] = a[8] ; i++ ; 将a[8]挖出再填到上一个坑a[0]中。

这样一个坑a[0]就被搞定了,但又形成了一个新坑a[8],这怎么办了?简单,再找数字来填a[8]这个坑。

这次从i开始向后找一个大于key的数,当i=3,符合条件,a[8] = a[3] ; j-- ; 将a[3]挖出再填到上一个坑中。

a659c350ca61fabf4020a0f48b4efce3ecf.jpg

(2)此时 i = 3; j = 7; key=72
再重复上面的步骤,先从后向前找,再从前向后找。

从j开始向前找,当j=5,符合条件,将a[5]挖出填到上一个坑中,a[3] = a[5]; i++;

从i开始向后找,当i=5时,由于i==j退出。
此时,i = j = 5,而a[5]刚好又是上次挖的坑,因此将key填入a[5]。

f40e3ac61935ae546d79353122b530440e3.jpg

(3)可以看出a[5]前面的数字都小于它,a[5]后面的数字都大于它。因此再对a[0…4]和a[6…9]这二个子区间重复上述步骤就可以了。

7c0d344ad9530affb166b72ca7aa9df9d23.jpg

3、平均时间复杂度:o(N*logN)

4、代码实现:

"""快速排序:【重点!!!常考!!!】
最优时间复杂度:o(nlogn)    最坏时间复杂度:o(n^2)    稳定性:不稳定"""
def quick_sort(alist,first,last):
    if first>=last:
        return ''
    else:
        mid_value=alist[first]
        low=first
        high=last
        while low<high:
            while low<high and alist[high]>=mid_value:
                high-=1
            alist[low]=alist[high]
            while low<high and alist[low]<mid_value:
                low+=1
            alist[high]=alist[low]
        alist[low]=mid_value  #退出循环时,low=high
        quick_sort(alist,first,high-1)  #对左侧的列表执行快速排序
        quick_sort(alist,low+1,last)  #对右侧的列表执行快速排序
        return alist
l=[54,26,93,17,77,31,44,55,20]
res=quick_sort(l,0,len(l)-1)  
print(res)  #[17, 20, 26, 31, 44, 54, 55, 77, 93]

六、归并排序

1、基本思想:

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。
首先考虑下如何将2个有序数列合并。这个非常简单,只要从比较2个数列的第一个数,谁小就先取谁,取了后就在对应数列中删除这个数。然后再进行比较,如果有数列为空,那直接将另一个数列的数据依次取出即可。

解决了上面的合并有序数列问题,再来看归并排序,其的基本思路就是将数组分成2组A,B,如果这2组组内的数据都是有序的,那么就可以很方便的将这2组数据进行排序。如何让这2组组内数据有序了?

可以将A,B组各自再分成2组。依次类推,当分出来的小组只有1个数据时,可以认为这个小组组内已经达到了有序,然后再合并相邻的2个小组就可以了。这样通过先递归的分解数列再合并数列就完成了归并排序。

2、过程:

c770ae31d901198e71426bbf2a8f08463b9.jpg

3、平均时间复杂度:o(NlogN)
归并排序的效率是比较高的,设数列长为N,将数列分开成小数列一共要logN步,每步都是一个合并有序数列的过程,时间复杂度可以记为O(N),故一共为O(N*logN)。

4、代码实现

"""归并排序:【重点!!!常考!!!】
最优时间复杂度:o(nlogn)    最坏时间复杂度:o(nlogn)    稳定性:稳定"""
def merge_sort(alist):
    n=len(alist)
    if n<=1:
        return alist
    mid=n//2
    left_li=merge_sort(alist[:mid])  #采用归并排序左侧的有序列表
    right_li=merge_sort(alist[mid:])  #采用归并排序右侧的有序列表

    left_pointer,right_pointer=0,0
    result=[]
    while left_pointer<len(left_li) and right_pointer<len(right_li):
        if left_li[left_pointer]<=right_li[right_pointer]:
            result.append(left_li[left_pointer])
            left_pointer+=1
        else:
            result.append(right_li[right_pointer])
            right_pointer+=1
    result+=left_li[left_pointer:]
    result+=right_li[right_pointer:]  #注:在Python中,若索引超出范围,就直接返回空列表[]
    return result

print(merge_sort([7,8,3,2,4,5,1,6]))  #[1, 2, 3, 4, 5, 6, 7, 8]

二分法查找:【重点!!!常考!!!】在一个有序的列表中查找

def binary_search(alist,item):
    n=len(alist)
    if n>0:
        mid=n//2
        if alist[mid]==item:
            return True
        elif item<alist[mid]:
            return binary_search(alist[:mid],item)
        else:
            return binary_search(alist[mid+1:],item)
    else:
        return False
l1=[17, 20, 26, 31, 44, 54, 55, 77]
print(binary_search(l1,30))  #False

转载于:https://my.oschina.net/pansy0425/blog/3038682

本文内容由网友自发贡献,转载请注明出处:https://www.wpsshop.cn/w/小舞很执着/article/detail/896695
推荐阅读
相关标签
  

闽ICP备14008679号