机试——排序算法总结

​ 机试中，排序算法是主要面临的一类算法，很久都没有接触机试的题了，解决的时候感觉有点思路不是很清楚了，因此写了这一片博客，来整理下常见的排序算法以及各种常见算法的效率稳定性等特点。

在机试中常用的排序算法主要包含下面几种：

​ 1.插入排序

​ 2.选择排序

​ 3.快速排序(最常用的排序)

​ 4.冒泡排序

​ 5.归并排序

​ 6.桶排序

下面我将具体介绍各种排序算法的一些特点：

排序算法	平均时间复杂度	最坏时间复杂度	空间复杂度	是否稳定
冒泡排序	O（n2）	O（n2）	O（1）	稳定
选择排序	O（n2）	O（n2）	O（1）	不稳定
直接插入排序	O（n2）	O（n2）	O（1）	稳定
希尔排序	O（n2）	O(O3/2)
归并排序	O(nlogn)	O(nlogn)	O（n）	稳定
快速排序	O(nlogn)	O(n2)	O（logn）	不稳定
堆排序	O(nlogn)	O(nlogn)	O(1)	不稳定

时间复杂度辅助记忆：

• 冒泡、选择、直接 排序需要两个for循环，每次只关注一个元素，平均时间复杂度为O（n2）（一遍找元素O(n)，一遍找位置O(n)）
• 快速、归并、希尔、堆基于二分思想，log以2为底，平均时间复杂度为O(nlogn)（一遍找元素O(n)，一遍找位置O(logn)）

1.插入排序

​ 每次从头到尾选择一个元素，并且将这个元素和整个数组中的所有已经排序的元素进行比较，然后插入到合适的位置。

​ 注意：插入排序的核心点就是两两比较时从后向前进行比较，如果比插入值大，那么将其向后移动，直到找到比插入值小的。

def insertion_sort(arr):
    length = len(arr)
    for i in range(1,length):     #从第一个元素开始依次进行排序
        tmp = arr[i]
        j = i
        while arr[j-1]>tmp and j>0:  #从当前元素从后向前向前开始遍历，寻找第一个比当前元素更小的元素
            arr[j] = arr[j-1]		#再找比当前小的元素位置的同时，只要扫描到的位置比当前元素大，那么将该元素后移一维
            j -= 1
        arr[j] = tmp
   return arr

稳定性：稳定

时间复杂度：O(n^2)

空间复杂度：O(1)

为什么插入排序是稳定的排序算法？

​ 当前从头到尾选择元素进行排序时，当选择到第i个元素时，前i-1个元素已经排好了续，取出第i个元素，从i-1开始向前开始比较，如果小于，则将该位置元素向后移动，继续先前的比较，如果不小于，那么将第i个元素放在当前比较的元素之后。

2.选择排序

​ 选择排序主要采用了从头到尾依次确定各个位置的方式来进行排序，首先遍历一次整个数组，如果遇到比第一个元素小的元素那么交换位置，一次遍历完成那么第一个位置就已经是整个数组中最小的元素了，经过n次遍历，确定全部位置的元素。

def selection_sort(arr):
    length = len(arr)
    for i in range(length):
        for j in range(i,length):
            if arr[i]>arr[j]:
                tmp = arr[i]
                arr[i] = arr[j]
                arr[j] = tmp
    return arr

稳定性：不稳定

时间复杂度：O(n^2)

空间复杂度：O(1)

3.冒泡排序

​ 冒泡排序额是实现是不停地进行两两比较，将较大的元素换到右侧，然后继续进行两两比较，直到比较完全全部元素，每进行完一轮两两比较，确定一个元素的位置。例如：第一轮两两比较确定最大的值，第二轮比较确定次大元素。

def bubble_sort(arr):
    length = len(arr)
    
    for i in range(0,length):
        for j in range(1,length-i):
            if arr[j]<arr[j-1]:
                tmp = arr[j]
                arr[j] = arr[j-1]
                arr[j-1] = tmp
    
    return arr

稳定性：稳定

时间复杂度：O(n^2)

空间复杂度：O(1)

冒泡排序在原始冒泡排序算法的基础上还能做哪些优化？

​ 1.设置是否已经排好序的flag。如果在某一轮的便利中没有出现任何的交换发生，这说明已经都排好序,那么直接将flag置True，每轮结束时检测flag，如果为True则直接返回

​ 2.某一轮的结束为止为j，但这一轮最后一次交换发生在lastSwap位置，那么说明lastSwap到j之间已经排好序，下次遍历的结束点就不需要再到j—而是直接到lastSwap即可。

4.希尔排序

​ 希尔排序是一种插入排序的改良算法，简单的插入排序不管元素怎么样，都从头到尾一步一步的进行元素比较，如果遇到逆序序列如：[5,4,3,2,1,0]数组末端的0要回到原始位置需要n-1次的比较和移动。而希尔排序使用跳跃式分组的策略，通过某个增量将数组元素划分为若干组，然后在各个组内进行插入排序，随后逐步缩小增量，继续按照组进行排序，直至增量为1。

​ 希尔排序通过这种策略使的整个数组在初始阶段宏观上基本有序，小的基本在前，大的基本在后，然后缩小增量相当于进行微调，不会过多的设计元素移动。

基本思想：把记录按照下标的一定增量进行分组，对每组使用直接插入排序算法进行排序；随着增量逐渐减少，魅族包含的元素个数越来越多，当增量减至1时，整个文件被分成一组，算法终止。

稳定性：不稳定

平均时间复杂度：O($n^2$)

最坏时间复杂度 : O($n^\frac{3}{2}$)

空间复杂度:O( $n^2$ )

5.快速排序

​ 快速排序的的主要思想是先找到一个任意一个元素作为基准元素pivot（一般都采用第一个元素作为基准），然后从右向左搜索，如果发现比pivot小，那么和pivot交换,然后从右向左进行搜索，如果发现比pviot大，那么进行交换，遍历一轮后pivot左边的元素都比它小，右边的元素都比他大，此时pivot的位置就是排好序后他也应该在的位置。然后继续用递归算法分别处理pivot左边的元素和右边的元素。

对于大的乱序数据快速排序被认为是最快速的排序方式

#方式一：递归
def quick_sort(arr,l,r):
    if(l<r):
        q = mpartition(arr,l,r)
        quick_sort(arr,l,q-1)    #前面经过一次mpartion后q位置已经排好序，因此递归时两部分跳过q位置
        quick_sort(arr,q+1,r)
    
    return arr
        

def mpartition(arr,l,r):
    """
    	递归子函数，povit放到指定位置
    	return l:最终标志元素被放置的位置，本轮确定了的元素位置
    """
    poviot = arr[l]
    
    while l<r:
        while l<r and arr[r]>=poviot:
            r -= 1
        if l<r:
            arr[l] = arr[r]
            l += 1
        
        while l<r and arr[l]<poviot:
            l += 1
        if l<r:
            arr[r] = arr[l]
            r -= 1

    arr[l]  = poviot
    
    return l

#方式二：非递归，利用栈

def partition(nums,low,high):
    #确定nums数组中指定部分low元素的位置，左边都比它小，右边都比他大
    
    pivot = nums[low]
    high_flag = True   #这里之所以设置这两个flag是为了确保交叉进行，否则可能会出现最大索引值处没有值或者最大索引值处一直付给各个low
    low_flag = False
    
    while low<high and low<len(nums) and high<len(nums):
        if high_flag:
            if nums[high]<pivot:
                nums[low]=nums[high]
                high_flag = False
                low_flag = True
            else:
                high -= 1
        if low_flag:
            if nums[low]>pivot:
                nums[high] = nums[low]
                low_flag = False
                high_flag = True
            else:
                low += 1
    nums[low] = pivot     
    
    return low
        
    

def quick_sort(nums):
    low = 0
    high = len(nums)-1
    stack = []    #存储每次遍历起始索引和结束索引
    
    if low<high:
        #先手动将找到第一个节点的最终位置，将原数组分为左右两个数组，分别左右索引入栈
        mid = partition(nums,low,high)
        if low<mid-1:
            stack.append(low)
            stack.append(mid-1)
        if high>mid+1:
            stack.append(mid+1)
            stack.append(high)
        
        #取出之前入栈的一个数组，来进行确定最终位置，分为左右两个子数组，分别左右索引入栈的操作，重复直到所有元素都已经排好序
        while stack:
            #这里写的是属于右半部都排好后左半部
            r = stack.pop()
            l = stack.pop()
            mid = partition(nums,l,r)
            if l<mid-1:
                stack.append(l)
                stack.append(mid-1)
            if r>mid+1:
                stack.append(mid+1)
                stack.append(r)
    
    return nums

稳定性：不稳定（排序过程中不停地交换元素位置造成了排序算法不稳定）

时间复杂度：

​ 平均时间O(nlogn)

​ 最坏情况：O(n^2)

空间复杂度：O(nlogn)

6.归并排序

​ 该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案”修补”在一起，即分而治之)。

​ 每次合并操作的平均时间复杂度为O(n)，而完全二叉树的深度为|log2n|。总的平均时间复杂度为O(nlogn)。而且，归并排序的最好，最坏，平均时间复杂度均为O(nlogn)。

def MergeSort(lists):
    if len(lists) <= 1:
        return lists
    num = int(len(lists) / 2)

    left = MergeSort(lists[:num])
    right = MergeSort(lists[num:])

    return Merge(left, right)

def Merge(left, right):
    r, l = 0, 0
    result = []
    while l < len(left) and r < len(right):
        if left[l] <= right[r]:
            result.append(left[l])
            l += 1
        else:
            result.append(right[r])
            r += 1
    result += list(left[l:])
    result += list(right[r:])
    return result

7.堆排序

​ 见堆排序

7.桶排序