排序算法：

一种能将一串数据依照特定顺序进行排列的一种算法

常见排序算法效率的比较

排序算法的实现

1. 冒泡排序

思想

1. 从索引为0的位置开始遍历，只比较相邻两个元素的大小，并且按照升序进行比较，这样遍历完成后，数组中的最大元素放在最后的位置。
2. 第二次的遍历范围是(0到n-2)， 因为n-1的位置已经被最大元素占据
3. 按照这个方法，每次遍历减少一个元素，两两比较升序排列，直到遍历到所以为1的位置终止
4. 最优时间复杂度：O(n) （表示遍历一次发现没有任何可以交换的元素，排序结束。）
   最坏时间复杂度：O(n2)
   稳定性：稳定

代码

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. 找出数组中最小元素，放在数组的起始位置。然后从剩下的数组中再找出最小的数组，依次放在上一次排序好元素之后，直到所有元素排序完毕
2. 最优时间复杂度：O(n2)
   最坏时间复杂度：O(n2)
   稳定性：不稳定（考虑升序每次选择最大的情况）

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. 通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
2. 最优时间复杂度：O(n) （升序排列，序列已经处于升序状态）
   最坏时间复杂度：O(n2)
   稳定性：稳定

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. 通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
2. 最优时间复杂度：O(nlogn)
   最坏时间复杂度：O(n2)
   稳定性：不稳定

代码

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. 归并排序是采用分治法的一个非常典型的应用。归并排序的思想就是先递归分解数组，再合并数组。
   将数组分解最小之后，然后合并两个有序数组，基本思路是比较两个数组的最前面的数，谁小就先取谁，取了后相应的指针就往后移一位。然后再比较，直至一个数组为空，最后把另一个数组的剩余部分复制过来即可。

代码

    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. 将数组列在一个表中并对列分别进行插入排序，重复这过程，不过每次用更长的列（步长更长了，列数更少了）来进行。最后整个表就只有一列了。将数组转换至表是为了更好地理解这算法，算法本身还是使用数组进行排序。
   3.最优时间复杂度：根据步长序列的不同而不同
   最坏时间复杂度：O(n2)
   稳定想：不稳定

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. 二分查找适用于有序数组
2. 可以类比查字典，先找出数组中的中间元素，与target比较，如果等于target, 即找到，返回True; 如果比target大，说明target在mid_element的左边，这时我们要更改查找范围，将其缩小为[0: mid-1]; 如果比target小，说明target在mid_element的右边，缩小查找范围为[mid+1：]，然后重复上述进行循环，直到first>last，退出循环，返回false
3. mid = first + (last - first) // 2是为了防止数值溢出
4. 优点是比较次数少，查找速度快，平均性能好；
5. 缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。
6. 时间复杂度：O(logn)
   空间复杂度：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)