排序算法and二分查找-python3

一、简单排序

https://www.cnblogs.com/siyz/p/7231569.html

1、插入排序

https://blog.csdn.net/su_bao/article/details/81003803
https://www.cnblogs.com/AlwinXu/p/5444799.html
1.1、插入排序原理

• 百度上的话，学术性太强，不容易看懂，我用自己的话复述一下插入排序原理。
• 插入排序的核心在于，它把一个无序数列看成两个数列，假如第一个元素构成了第一个数列，那么余下的元素构成了第二个数列，很显然，第一个数列是有序的（因为只有一个元素嘛，肯定有序哦），那么我们把第二个数列的第一个元素拿出来插入到第一个数列，使它依然构成一个有序数列，直到第二个数列中的所有元素全部插入到第一个数列，这时候就排好序了。
• 插入排序的复杂度是$O(n^2)$O(n2)，在数据量较小时效率较高

1.2、一图以明之

1.3、Python代码

def InsertSort(myList):
    #获取列表长度
    length = len(myList)
    for i in range(1,length):
        #设置当前值前一个元素的标识
        j = i - 1
        #如果当前值小于前一个元素,则将当前值作为一个临时变量存储,将前一个元素后移一位
        if(myList[i] < myList[j]):
            temp = myList[i]
            myList[i] = myList[j]
            #继续往前寻找,如果有比临时变量大的数字,则后移一位,直到找到比临时变量小的元素或者达到列表第一个元素
            j = j-1
            while j>=0 and myList[j] > temp:
                myList[j+1] = myList[j]
                j = j-1
            #将临时变量赋值给合适位置
            myList[j+1] = temp

myList = [49,38,65,97,76,13,27,49]
InsertSort(myList)
print(myList)

2、选择排序

https://www.cnblogs.com/AlwinXu/p/5424510.html

选择排序比较好理解，好像是在一堆大小不一的球中进行选择（以从小到大，先选最小球为例）：

1. 选择一个基准球
2. 将基准球和余下的球进行一一比较，如果比基准球小，则进行交换
3. 第一轮过后获得最小的球
4. 在挑一个基准球，执行相同的动作得到次小的球
5. 继续执行4，直到排序好
   时间复杂度：O(n^2). 需要进行的比较次数为第一轮 n-1，n-2…1, 总的比较次数为 n*(n-1)/2。

从所有序列中先找到最小的，然后放到第一个位置。之后再看剩余元素中最小的，放到第二个位置……以此类推，就可以完成整个的排序工作。

def selectedSort(myList):
    #获取list的长度
    length = len(myList)
    #一共进行多少轮比较
    for i in range(0,length-1):
        #默认设置最小值得index为当前值
        smallest = i
        #用当先最小index的值分别与后面的值进行比较,以便获取最小index
        for j in range(i+1,length):
            #如果找到比当前值小的index,则进行两值交换
            if myList[j]<myList[smallest]:
                #tmp = myList[j]
                myList[j], myList[smallest]= myList[smallest],myList[j]
                #myList[smallest]=tmp
        #打印每一轮比较好的列表
        print("Round ",i,": ",myList)


myList = [1,4,5,0,6]
print("Selected Sort: ")
selectedSort(myList)

3、冒泡排序

它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。
走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端。
复杂度是$O(n^2)$O(n2)

data_set = [12,45,2,48,66,2,1,56,36,90,5,10,503]

for i in range(len(data_set)):   ##控制相邻比较的轮数 
    for j in range(len(data_set)-i-1):  #控制每轮相邻比较的次数
        #如果前面的元素的值大于后面一个元素 互换值
        if data_set[j]>data_set[j+1]:
            data_set[j], data_set[j+1]=data_set[j+1], data_set[j]
print(data_set)

---

二、快速排序

快速排序（quickSort）

1、取一个参考值放到列表中间，初次排序后，让左侧的值都比他小，右侧的值，都比他大。
2、分别对左侧和右侧的部分递归第1步的操作。

利用了 分而治之 的思想。

其中一次排序步骤如下：

快速排序漫画图解：

https://blog.csdn.net/hrn1216/article/details/51526362

---

实现思路：
https://www.cnblogs.com/kunpengv5/p/7833361.html

• 两个指针left，right分别指向列表的第一个元素和最后一个元素，然后取一个参考值，默认为第一个列表的第一个元素list[0]，称为K；
• 然后left指向的值先和参考值K进行比较，若list[left]小于或等于K值，left就一直向右移动，left+1，直到移动到大于K值的地方，停住；
• right指向的值和参考值K进行比较，若list[right]大于K值，right就一直向左移动，right-1，直到移动到小于K值的地方，停住；
• 此时，left和right若还没有相遇，即left还小于right，则二者指向的值互换；
• 若已经相遇则说明，第一次排序已经完成，将list[right]与list[0]的值进行互换，进行之后的递归。

#快排的主函数，传入参数为一个列表，左右两端的下标
def QuickSort(list,low,high):
    if high > low:
        #传入参数，通过Partitions函数，获取k下标值
        k = Partitions(list,low,high)
        #递归排序列表k下标左侧的列表
        QuickSort(list,low,k-1)
        # 递归排序列表k下标右侧的列表
        QuickSort(list,k+1,high)

def Partitions(list,low,high):
    left = low
    right = high
    #将最左侧的值赋值给参考值k
    k = list[low]
    #当left下标，小于right下标的情况下，此时判断二者移动是否相交，若未相交，则一直循环
    while left < right :
        #当left对应的值小于k参考值，就一直向右移动
        while list[left] <= k:
            left += 1
        # 当right对应的值大于k参考值，就一直向左移动
        while list[right] > k:
            right = right - 1
        #若移动完，二者仍未相遇则交换下标对应的值
        if left < right:
            list[left],list[right] = list[right],list[left]
    #若移动完，已经相遇，则交换right对应的值和参考值
    list[low] = list[right]
    list[right] = k
    #返回k值
    return right

list_demo = [6,1,2,7,9,3,4,5,10,8]
print(list_demo)
QuickSort(list_demo,0,9)
print(list_demo)

时间复杂度：O(nlgn)
另一个人思路：

# https://www.cnblogs.com/AlwinXu/p/5424905.html

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)

---

三、二分查找

1、递归解决二分查找

def binary_chop(alist, data):
    """
    递归解决二分查找
    """

    # 二分查找只针对排好序的数组
    n = len(alist)
    # 如果查找到最后都没有匹配的，返回false
    if n < 1:
        return False
    mid = n // 2
    if alist[mid] > data:
        return binary_chop(alist[0:mid], data)
    elif alist[mid] < data:
        return binary_chop(alist[mid+1:], data)
    else:
        return True

if __name__ == '__main__':
    lis = [5, 14, 2,4, 12, 23]
    lis.sort()
    # 如果查找的数存在，输出它排序后的下标
    if (binary_chop(lis, 23)):
        print(lis.index(23))
    else:
        print("no data")

2、非递归解决二分查找

def binary_chop(alist, data):
    """
    非递归解决二分查找
    """
    n = len(alist)
    first = 0
    last = n - 1
    while first <= last:
        mid = (last + first) // 2
        # 如果中间的数alist[mid] 比要查找的数data大，则从first~mid-1的列表中继续查找
        if alist[mid] > data:
            last = mid - 1
        # 如果中间的数alist[mid] 比要查找的数data小，则从mid+1到last的列表中继续查找
        elif alist[mid] < data:
            first = mid + 1
        else:
            return True
    return False

if __name__ == '__main__':
    lis = [5, 14, 2,4, 12, 23]
    lis.sort()
    # 如果查找的数存在，输出它排序后的下标
    if (binary_chop(lis, 23)):
        print(lis.index(23))
    else:
        print("no data")

---

另一个大神写的八大排序算法