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

1. 冒泡排序

（1）原理

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

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

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

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

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

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

（2）代碼實(shí)現(xiàn)

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

def bubble(alist):
    """1. 冒泡排序"""
    n = len(alist)
    for j in range(0,n-1):
        """比較輪數(shù)"""
        count = 0
        for i in range(0,n-1-j):
            """內(nèi)層每次循環(huán)比較兩個(gè)元素的次數(shù)"""
            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）第二次再?gòu)暮罄m(xù)的列表中選出最小值，放在列表左邊的第二個(gè)位置；

3）依次類推，直到后續(xù)列表全部結(jié)束，此時(shí)已經(jīng)將列表全部元素從小到大排列好了；

（2）編程思維

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

2）如果后續(xù)元素比這個(gè)元素小，則交換兩者的位置。循環(huán)完后續(xù)所有元素，即得到第一輪比較的最小值位于最左側(cè)第一個(gè)位置。

3）每次比較完，要比較列表就會(huì)比比上次要比較列表少一個(gè)數(shù)，這個(gè)數(shù)已經(jīng)為上次比較列表的最小值放于左邊了。

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

（3）代碼實(shí)現(xiàn)

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

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

?

3. 快速排序

（1）原理

1） 每次選擇一個(gè)基準(zhǔn)值，把列表分為大于基準(zhǔn)值、基準(zhǔn)值、小于基準(zhǔn)值三部分

2）對(duì)小于基準(zhǔn)值的列表再選出新的基準(zhǔn)值，再進(jìn)行同樣的切分。【大于基準(zhǔn)值的列表也同樣處理】

3）依次類推，即每次切分出的列表再選基準(zhǔn)值，再進(jìn)行同樣的切分，直到切分的列表長(zhǎng)度為1時(shí)結(jié)束。

（2）編程思維

1）因?yàn)槊看味季瓦M(jìn)行相同的操作，這里可以使用遞歸的思想

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

（3）代碼實(shí)現(xiàn)

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

import random

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

    # 基準(zhǔn)返回條件：
    if n<2:
        return alist
    else:
        """隨機(jī)選擇列表中的一個(gè)序號(hào)為基準(zhǔn)值索引"""
        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）相當(dāng)于把列表分成兩部分（假想兩部分，實(shí)際只有一個(gè)部分），第一次選擇列表第一個(gè)元素放在最左邊這部分，其余元素放在右邊這部分。【此時(shí)左邊部分只有1個(gè)元素，右邊部分有n-1個(gè)元素】

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

3）后續(xù)依次類推，即從右邊依次取一個(gè)數(shù)拿到左邊的最后面依次與左邊元素進(jìn)行比較。即插入到左邊的合適位置。

（2）編程思維

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

2）內(nèi)層控制從后面部分取出的數(shù)與前面部分依次比較的【取出的數(shù)應(yīng)該放在左邊部分最尾部開始依次與前一個(gè)元素進(jìn)行比較】。

3）最壞的情況是，這個(gè)取出的數(shù)一直向前比較，直到比較左邊部分最開始的元素，即i=0索引的元素。此時(shí)取出的數(shù)索引已經(jīng)到了i=1的情況。所以最壞情況需要比較到取的數(shù)索引至少大于0的情況，即可停止比較。如果取的數(shù)依次比較時(shí)比要比較的數(shù)大，則無需再比較了，可以退出循環(huán)。即取的該數(shù)比較結(jié)束。因?yàn)楸容^數(shù)之前的數(shù)已經(jīng)有序了，無需比較。

(3) 代碼實(shí)現(xiàn)

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

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

二、棧與隊(duì)列

1.棧【stack】

(1) 定義

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

原理：后進(jìn)先出【LIFO】

模型如下：

（2）代碼實(shí)現(xiàn)

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

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

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

    def pop(self):
        """彈出一個(gè)元素【默認(rèn)棧頂元素】與push相對(duì)"""
        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("剛創(chuàng)建好的棧元素個(gè)數(shù): ",stack.size())
    print("剛創(chuàng)建好的棧是否為空: ",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 再?gòu)棾鰲ｍ斣?后 棧元素個(gè)數(shù): ",stack.size())
    print("先push 1 2 3 再?gòu)棾鰲ｍ斣?后 棧是否為空: ",stack.is_empty())
            
          

2. 隊(duì)列 【 queue】

（1）定義

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

（2）代碼實(shí)現(xiàn)

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

class Queue(object):
    """ 隊(duì)列 """
    def __init__(self):
        """ 默認(rèn)創(chuàng)建一個(gè)列表【使用私有變量】"""
        self.__list = []

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

    def out_queue(self):
        """彈出第一個(gè)元素，與in相對(duì)"""
        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("剛創(chuàng)建好的隊(duì)列元素個(gè)數(shù): ",q.size())
    print("剛創(chuàng)建好的隊(duì)列是否為空: ",q.is_empty())
    print("進(jìn)入第一個(gè)元素 3 后的對(duì)列",q.in_queue(3))
    print("進(jìn)入第二個(gè)元素 2 后的對(duì)列",q.in_queue(2))
    print("進(jìn)入第三個(gè)元素 1 后的對(duì)列",q.in_queue(1))

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

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

三、二分查找

（1）定義

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

（2）代碼實(shí)現(xiàn)

            
              #!/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]
              
            
          

?