排序算法：

一種能將一串?dāng)?shù)據(jù)依照特定順序進(jìn)行排列的一種算法

常見排序算法效率的比較

排序算法的實(shí)現(xiàn)

1. 冒泡排序

思想

1. 從索引為0的位置開始遍歷，只比較相鄰兩個(gè)元素的大小，并且按照升序進(jìn)行比較，這樣遍歷完成后，數(shù)組中的最大元素放在最后的位置。
2. 第二次的遍歷范圍是(0到n-2)， 因?yàn)閚-1的位置已經(jīng)被最大元素占據(jù)
3. 按照這個(gè)方法，每次遍歷減少一個(gè)元素，兩兩比較升序排列，直到遍歷到所以為1的位置終止
4. 最優(yōu)時(shí)間復(fù)雜度：O(n) （表示遍歷一次發(fā)現(xiàn)沒有任何可以交換的元素，排序結(jié)束。）
   最壞時(shí)間復(fù)雜度：O(n2)
   穩(wěn)定性：穩(wěn)定

代碼

class Sorting(object):
    def bubble_sort(self, nums):
        n = len(nums)
        for j in range(n-1, 0, -1): # 確定遍歷的范圍
            for i in range(j): # 在特定的范圍的遍歷，比較元素大小
                if nums[i] > nums[i+1]:
                    nums[i], nums[i+1] = nums[i+1], nums[i]

        return nums

2. 選擇排序

思想

1. 找出數(shù)組中最小元素，放在數(shù)組的起始位置。然后從剩下的數(shù)組中再找出最小的數(shù)組，依次放在上一次排序好元素之后，直到所有元素排序完畢
2. 最優(yōu)時(shí)間復(fù)雜度：O(n2)
   最壞時(shí)間復(fù)雜度：O(n2)
   穩(wěn)定性：不穩(wěn)定（考慮升序每次選擇最大的情況）

class Sorting(object):
    def select_sort(self, nums):
        n = len(nums)
        for i in range(n-1):
            min_index = i
            for j in range(i+1, n):
                if nums[min_index]>nums[j]:
                    min_index = j
            if min_index != i:
                nums[min_index], nums[i] = nums[i], nums[min_index]

        return nums

3. 插入排序

思想

1. 通過構(gòu)建有序序列，對(duì)于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。插入排序在實(shí)現(xiàn)上，在從后向前掃描過程中，需要反復(fù)把已排序元素逐步向后挪位，為最新元素提供插入空間。
2. 最優(yōu)時(shí)間復(fù)雜度：O(n) （升序排列，序列已經(jīng)處于升序狀態(tài)）
   最壞時(shí)間復(fù)雜度：O(n2)
   穩(wěn)定性：穩(wěn)定

class Sorting(object):
    def insert_sort(self, nums):
        n = len(nums)
        for i in range(1, n):
            for j in range(i, 0, -1):
                if nums[j] < nums[j-1]:
                    nums[j], nums[j-1] = nums[j-1], nums[j]
                else:
                    break
        return nums

4. 快速排序

思想

1. 通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。
2. 最優(yōu)時(shí)間復(fù)雜度：O(nlogn)
   最壞時(shí)間復(fù)雜度：O(n2)
   穩(wěn)定性：不穩(wěn)定

代碼

class Sorting(object):
    def quick_sort(self, nums, first, last):
        if first >= last:
            return
        low = first
        high = last
        mid_value = nums[first]

        while low < high:
            while low < high and nums[high] >= mid_value:
                high -=1
            nums[high] = nums[low]

            while low < high and nums[low] < mid_value:
                low += 1
            nums[low] = nums[high]

        nums[low] = mid_value

        self.quick_sort(nums, first, (low-1))
        self.quick_sort(nums, (low+1), last)

        return nums

5. 歸并排序

思想

1. 歸并排序是采用分治法的一個(gè)非常典型的應(yīng)用。歸并排序的思想就是先遞歸分解數(shù)組，再合并數(shù)組。
   將數(shù)組分解最小之后，然后合并兩個(gè)有序數(shù)組，基本思路是比較兩個(gè)數(shù)組的最前面的數(shù)，誰小就先取誰，取了后相應(yīng)的指針就往后移一位。然后再比較，直至一個(gè)數(shù)組為空，最后把另一個(gè)數(shù)組的剩余部分復(fù)制過來即可。

代碼

    def merge_sort(self, nums):
        n = len(nums)
        if n <= 1:
            return nums
        mid = n // 2
        left_li = self.merge_sort(nums[:mid])
        right_li = self.merge_sort(nums[mid:])

        left_point, right_point = 0, 0
        result = []
        while left_point < len(left_li) and right_point < len(right_li):
            if left_li[left_point]<right_li[right_point]:
                result.append(left_li[left_point])
                left_point += 1
            else:
                result.append(right_li[right_point])
                right_point += 1

        result += left_li[left_point:]
        result += right_li[right_point:]

        return result

6.希爾排序

思想

1. 是插入排序的一種
2. 將數(shù)組列在一個(gè)表中并對(duì)列分別進(jìn)行插入排序，重復(fù)這過程，不過每次用更長(zhǎng)的列（步長(zhǎng)更長(zhǎng)了，列數(shù)更少了）來進(jìn)行。最后整個(gè)表就只有一列了。將數(shù)組轉(zhuǎn)換至表是為了更好地理解這算法，算法本身還是使用數(shù)組進(jìn)行排序。
   3.最優(yōu)時(shí)間復(fù)雜度：根據(jù)步長(zhǎng)序列的不同而不同
   最壞時(shí)間復(fù)雜度：O(n2)
   穩(wěn)定想：不穩(wěn)定

def shell_sort(nums):
    n = len(nums)
    gap= n // 2
    while gap > 0:
        for i in range(gap, n):
            for j in range(i, 0, -gap):
                if nums[j] < nums[j-1]:
                    nums[j], nums[j-1] = nums[j-1], nums[j]
                else:
                    break
        gap //= 2

搜索

二分查找

思想：

1. 二分查找適用于有序數(shù)組
2. 可以類比查字典，先找出數(shù)組中的中間元素，與target比較，如果等于target, 即找到，返回True; 如果比target大，說明target在mid_element的左邊，這時(shí)我們要更改查找范圍，將其縮小為[0: mid-1]; 如果比target小，說明target在mid_element的右邊，縮小查找范圍為[mid+1：]，然后重復(fù)上述進(jìn)行循環(huán)，直到first>last，退出循環(huán)，返回false
3. mid = first + (last - first) // 2是為了防止數(shù)值溢出
4. 優(yōu)點(diǎn)是比較次數(shù)少，查找速度快，平均性能好；
5. 缺點(diǎn)是要求待查表為有序表，且插入刪除困難。因此，折半查找方法適用于不經(jīng)常變動(dòng)而查找頻繁的有序列表。
6. 時(shí)間復(fù)雜度：O(logn)
   空間復(fù)雜度：O(1)

代碼

非遞歸法
def binary_search(nums, target):
    n = len(nums)
    first = 0
    last = n-1
    while first <= last:
        mid = first + (last - first) // 2
        if nums[mid] > target:
            last = mid-1
        elif nums[mid] < target:
            first = mid + 1
        else:
            return True
    return False

遞歸法
def binary_search2(nums, target):
    if len(nums) == 0:
        return False
    mid = len(nums) //2
    if nums[mid] == target:
        return True
    else:
        if target < nums[mid]:
            return binary_search(nums[:mid], target)
        else:
            return binary_search(nums[mid+1:],target)