一、排序【這里介紹冒泡排序、選擇排序、快速排序和插入排序】

1. 冒泡排序

（1）原理

解釋：冒泡排序，分 多輪排序。

1）每一輪都是從上層的 第一個數開始與其下一個數進行對比 ， 如果大于下一個數就進行交換 ，下次對比就從上面第二個數【不管之前有無交換】再與其下一個數進行比較，依次比較到最后一個數。【如圖 i 的移動變化】

2） 第一輪比較【j=0】 。比較了最底下第二個數和最底下這個數后，即第一輪比較完。所以第一輪比較的次數為 n-1次 ，即從上面第一個數一直比較到底下第二個數。【其中序列有n個數】。此時一輪獲取序列的 最大值于最底下 。【如圖j=0時】

3） 第二輪【j=1】 的時候，從最上面第一個數開始與下一個數比較。一直到倒數第三個數和倒數第二個數比較完即結束一輪。【最底下的數已經再第一輪已經比較完了，無需再比較】，此時這輪比較的次數為為 n-2次 .此時 第二大值與底下往上第二個位置

4）之后依次類推。首先觀察，每次比較后，都得到一個當前比較序列的最大值依次放入底部排序而上。第一輪整體序列（n個）的最大值于最底部，第二輪除了最底部的那個數的序列（n-1）個數取的最大值與底部往上第二個位置。當獲取第n-1大的數與底部往上第n-1個位置時已經比較的輪數為n-1輪。圖中 j 即表示輪數的序號【但j從0開始? 所以輪序號從j=0到j=n-2?即 n-1輪】

5）而每一輪比較的次數，第一輪（j=0）比較n-1次【n個數】，第二輪（j=1）比較n-2次【n-1個數】，....，第n-1輪（j=n-2）比較1次【2個數】。所以比較次數 i 與 輪序 j 有關系。其中 i = n-1-j。

（2）代碼實現

            
              #!/usr/bin/env python3
# -*- coding: UTF-8 -*-

def bubble(alist):
    """1. 冒泡排序"""
    n = len(alist)
    for j in range(0,n-1):
        """比較輪數"""
        count = 0
        for i in range(0,n-1-j):
            """內層每次循環比較兩個元素的次數"""
            if alist[i] > alist[i+1]:
                alist[i],alist[i+1] = alist[i+1],alist[i]
                count+=1
        ### 如果原本有序
        if count == 0:
            return alist
    return alist

if __name__ == '__main__':
    alist = [34, 26, 12, 45, 78, 31]
    result = bubble(alist)
    print(result)


            
          

?

2. 選擇排序

（1）原理

1）第一次從列表中選出最小值，放在列表最左邊；

2）第二次再從后續的列表中選出最小值，放在列表左邊的第二個位置；

3）依次類推，直到后續列表全部結束，此時已經將列表全部元素從小到大排列好了；

（2）編程思維

1)? 每次選擇 要比較列表的 第一個元素 為最小值，循環該元素 后 的每一個元素，讓 后續元素依次與該元素比較 。

2）如果后續元素比這個元素小，則交換兩者的位置。循環完后續所有元素，即得到第一輪比較的最小值位于最左側第一個位置。

3）每次比較完，要比較列表就會比比上次要比較列表少一個數，這個數已經為上次比較列表的最小值放于左邊了。

4）所以外循環為從第一個位置比較到倒數第二個位置。即 j=0 到 j= n-2? 即 n-1 次，這個循環確定每次最終得到比較序列的最小值，內層循環比較的范圍則從外循環每次確定的最小值位置的下一位置一直比較到最后，即n-1。

（3）代碼實現

            
              #!/usr/bin/env python3
# -*- coding: UTF-8 -*-

def select_sort_a(alist):
    """2.選擇排序
    (1) 第一次循環所有數字，選出最小值放在最左邊，
    (2) 第二次循環所有(不包含第一個),選出最小值放在最左邊第二個位置
    依次類推"""
    n = len(alist)
    for j in range(0,n-1):
        """最外層循環次數"""
        # 默認第一個數為最小
        min_index = j
        for i in range(j+1,n):
            """循環最小值右邊的值與最小值進行對比"""
            if alist[i]
              
            
          

?

3. 快速排序

（1）原理

1） 每次選擇一個基準值，把列表分為大于基準值、基準值、小于基準值三部分

2）對小于基準值的列表再選出新的基準值，再進行同樣的切分。【大于基準值的列表也同樣處理】

3）依次類推，即每次切分出的列表再選基準值，再進行同樣的切分，直到切分的列表長度為1時結束。

（2）編程思維

1）因為每次都就進行相同的操作，這里可以使用遞歸的思想

2）每次切分成三部分，則這里分三部分。大于部分進行遞歸、小于部分進行遞歸、再和中間部分連接。即可得到最終排序列表。其中遞歸的條件是列表長度小于2。

（3）代碼實現

            
              #!/usr/bin/env python3
# -*- coding: UTF-8 -*-

import random

def quick_sort_s(alist):
    """3.快速排序
    (1).首先選出一個基準值，把列表分成大于、小于等于基準值三大塊
    (2). 再對小于、大于的小塊進行同樣的操作"""
    n = len(alist)

    # 基準返回條件：
    if n<2:
        return alist
    else:
        """隨機選擇列表中的一個序號為基準值索引"""
        jizhun_value_index = random.randint(0,n-1)
        less = [a for a in alist if a
              
                alist[jizhun_value_index]]

    result = quick_sort_s(less)+[alist[jizhun_value_index]]+quick_sort_s(more)
    return result

if __name__ == '__main__':
    alist1 = [34, 26, 12, 45, 78, 31]
    result = quick_sort_s(alist1)
    print(result)



              
            
          

4. 插入排序

（1）原理

1）相當于把列表分成兩部分（假想兩部分，實際只有一個部分），第一次選擇列表第一個元素放在最左邊這部分，其余元素放在右邊這部分。【此時左邊部分只有1個元素，右邊部分有n-1個元素】

2） 第一次 從右邊第一個元素【即整個列表的第二個元素】拿出放到左邊的這部分的第二個位置，再與左邊部分進行依次向前比較。第一次左邊只有一個元素，只需要比較1次。【比較完后，左邊2個元素、右邊n-2個元素】

3）后續依次類推，即從右邊依次取一個數拿到左邊的最后面依次與左邊元素進行比較。即插入到左邊的合適位置。

（2）編程思維

1)? 這里需要兩層循環，最外層循環控制依次從右邊部分取的數索引，這里應該從列表第二個元素開始取（j=1），一直取到最末尾（j=n）

2）內層控制從后面部分取出的數與前面部分依次比較的【取出的數應該放在左邊部分最尾部開始依次與前一個元素進行比較】。

3）最壞的情況是，這個取出的數一直向前比較，直到比較左邊部分最開始的元素，即i=0索引的元素。此時取出的數索引已經到了i=1的情況。所以最壞情況需要比較到取的數索引至少大于0的情況，即可停止比較。如果取的數依次比較時比要比較的數大，則無需再比較了，可以退出循環。即取的該數比較結束。因為比較數之前的數已經有序了，無需比較。

(3) 代碼實現

            
              #!/usr/bin/env python3
# -*- coding: UTF-8 -*-

def insert_sort_s(alist):
    """插入排序
    依次從第二個數開始取再依次與前面的數進行對比排序"""
    n = len(alist)
    for j in range(1,n):
        i = j
        while i>0:
            if alist[i]
              
            
          

二、棧與隊列

1.棧【stack】

(1) 定義

是一種容器，可存數據元素、訪問元素、刪除元素。其最大的特點就是只允需從容器的一端【稱為棧頂】輸入（push）、輸出元素（pop）元素；無位置概念，保證任何時候可訪問、可刪除的元素都是最上面的那個元素。

原理：后進先出【LIFO】

模型如下：

（2）代碼實現

            
              #!/usr/bin/env python3
# -*- coding: UTF-8 -*-

class stack_s(object):
    def __init__(self):
        """ 默認創建一個列表【使用私有變量】"""
        self.__list = []

    def push(self,item):
        """添加一個元素到列表
        【這里默認是選擇列表第一個元素為棧底，可自行定義】"""
        self.__list.append(item)

    def pop(self):
        """彈出一個元素【默認棧頂元素】與push相對"""
        self.__list.pop()

    def peek(self):
        """返回棧頂元素"""
        if self.__list:
            return self.__list[-1]
        else:
            return None
    def is_empty(self):
        """判斷是否為空"""
        return self.__list == []

    def size(self):
        return len(self.__list)

    def show_list(self):
        return self.__list

if __name__ == '__main__':
    stack = stack_s()
    print("剛創建好的棧元素個數: ",stack.size())
    print("剛創建好的棧是否為空: ",stack.is_empty())
    stack.push(1)
    stack.push(2)
    stack.push(3)
    print("push 1 2 3 元素后的列表: ",stack.show_list())
    print("彈出的棧頂元素是: ",stack.peek())
    stack.pop()
    print("先push 1 2 3 再彈出棧頂元素3后 棧元素個數: ",stack.size())
    print("先push 1 2 3 再彈出棧頂元素3后 棧是否為空: ",stack.is_empty())
            
          

2. 隊列 【 queue】

（1）定義

隊列是一種只允許從一端插入操作、另一端進行刪除操作的線性表。遵循先進先出（FIFO）準則。

（2）代碼實現

            
              #!/usr/bin/env python3
# -*- coding: UTF-8 -*-

class Queue(object):
    """ 隊列 """
    def __init__(self):
        """ 默認創建一個列表【使用私有變量】"""
        self.__list = []

    def in_queue(self,item):
        """添加一個元素到隊列
        【這里默認是選擇列表第一個元素為，可自行定義】"""
        self.__list.append(item)
        return self.__list

    def out_queue(self):
        """彈出第一個元素，與in相對"""
        return self.__list.pop(0)
        #return self.__list

    def is_empty(self):
        """判斷是否為空"""
        return self.__list == []

    def size(self):
        return len(self.__list)

if __name__ == '__main__':
    q = Queue()
    print("剛創建好的隊列元素個數: ",q.size())
    print("剛創建好的隊列是否為空: ",q.is_empty())
    print("進入第一個元素 3 后的對列",q.in_queue(3))
    print("進入第二個元素 2 后的對列",q.in_queue(2))
    print("進入第三個元素 1 后的對列",q.in_queue(1))

    print("in_queue 3 2 1 后 隊列元素個數: ",q.size())
    print("in_queue 3 2 1 后 隊列是否為空: ",q.is_empty())

    print("彈出的第一個元素是",q.out_queue())
    print("彈出的第二個元素是",q.out_queue())
    print("彈出的第三個元素是",q.out_queue())
            
          

三、二分查找

（1）定義

二分查找也稱折半查找（Binary Search），它是一種效率較高的查找方法。但是，折半查找要求線性表必須采用順序存儲結構，而且表中元素按關鍵字有序排列。

（2）代碼實現

            
              #!/usr/bin/env python3
# -*- coding: UTF-8 -*-

def binary_search(alist,item):
    """二分查找"""
    n = len(alist)
    low = 0
    high = n-1
    while low<=high:
        mid_index = (low+high)//2
        if alist[mid_index] == item:
            return "找到元素! 在原列表索引為{0}的位置".format(mid_index)

        elif alist[mid_index]
              
            
          

?