冒泡排序 选择排序 快速排序 归并排序

引言

写点基础的文章，这四个排序算法算是很基础了。

稳定与不稳定排序算法区别

稳定排序算法是指，如果碰到相同的值，两者不会互换位置。
不稳定排序算法是指，如果碰到相同的值，两者可能会互换位置。

冒泡排序

冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的稳定排序算法。

理解冒泡排序其实很简单，比如有个数组为m，长度为n。
首先我们需要确定的是，肯定需要从头到尾遍历一次，下标记作i，那么这个值就是m[i]，和这个值去比较的值，肯定是m[i] + 1，每次都是两两比较，如果只进行一次遍历，那么只能让相邻的两个值互换，因此我们需要嵌套遍历。
比如: 3 2 1

• 第一次遍历
• 3>2，两者互换变为2 3 1
• 下标前进1，此时比较的是3和1
• 3>1，两者互换
• 最后排序为 2 1 3。
• 此时最大的值3已经不用再排序了，需要再从下标0开始继续排序。

栗子：用python实现，因为脚本语言的好处就是可以返回多个值，并且也可以同时给多个值赋值，这样的代码让人看着更容易理解。

def bubble_sort(m):
	# 第一层遍历，一次遍历只能让一个值到指定的位置去
    arr_length = len(m)
    for i in range(arr_length - 1): 
        # 第二层遍历是为了让所有的值都经过一次比较
        # 但是之前比较过的不需要再比较了，所以这里可以-i
        for j in range(arr_length - i - 1):  
            if m[j] > m[j + 1]:
                # 两者互换位置
                m[j], m[j + 1] = m[j + 1], m[j]
    return m

从上面我们得知，因为2层遍历，这个算法的时间复杂度为O(n²)，n为数组长度。

选择排序

选择排序（Selection Sort）是不稳定的排序算法,这个算法我个人觉得是最好理解的一个了，每次遍历选择一个最小的值（reverse就选择最大的），和当前需要排序的首个下标值互换位置，和冒泡不同的是，它每次遍历之后前一个不需要再排序，而冒泡正好相反，并且它不是两两比较，这是它不稳定的原因。

def selection_sort(m):
	arr_length = len(m)
    for i in range(arr_length - 1):
        min_index = i # 用来记录最小值下标
        # 第二层循环正好和冒泡相反，发现了吗
        for j in range(i + 1, arr_length):
            if m[j] < m[min_index]:
                min_index = j
        # i 不是最小值下标时，将 i 和最小值互换
        if i != min_index:
            m[i], m[min_index] = m[min_index], m[i]
    return m

因为2层遍历，这个算法的时间复杂度为O(n²)，n为数组长度。

快速排序

快速排序（Quick Sort）是对冒泡排序的一种改进，是不稳定排序算法。
实际上我理解快排的时候我并没有觉得它和冒泡有什么相关的地方。

理解快排：
比如有个数组m为 5 8 1 3 6 9 4

• 我们将第一个值记录下来，base = 5(由于base值我们是取的第一个，所以开始的时候就得从后往前先开始。)
• 此时下标i=0，j=6(i为起始下标，j为结束下标)
• 我们从j下标开始(从后往前)找一个比base小的值(找到的是4)，并和它交换位置，此时数组变为4 8 1 3 6 9 5
• 此时i=0,j=6，没有变，因为从后往前第一个就找到了，m[j]还是那个base值5
• 我们从i下标开始(从前往后)找一个比base大的值(找到的是8)，并和它交换位置，此时数组变为4 5 1 3 6 9 8
• 此时i=1,j=6，m[i]还是那个base值5
• 再从后往前找，找一个比base小的值(找到的是3)，并和它交换位置，此时数组变为4 3 1 5 6 9 8
• 此时i=1,j=3，m[j]还是那个base值5
• 再从前往后找，找一个比base大的值，但此时如果找到的是6那么i就会大于j，如果i==j的时候就不需要排序了，更何况大于，此时就算第一遍排序完成，在5左边的都是比它小的，在5右边的都是比它大的，我们再用同样的方法对左右2边的进行排序即可。

下面python的例子没有使用循环，也就是没有使用 i,j 下标，因为python的列表操作十分简单，这里直接递归，需要注意的是这里虽然额外用了列表空间，但是并没有起到空间换时间的作用，只是为了让代码看着容易理解。(注意递归在列表足够大的情况下会造成栈溢出)。

def quick_sort(m):
    if len(m) >= 2:  # 如果数组长度>2才排序 递归也是通过这种方式退出的    
        base = m[0] 
        left, right = [], []  # 定义基准值左右两侧的列表        
        m.remove(base)  # 从原始数组中移除基准值        
        for num in m:            
            if num >= base:                
                right.append(num)            
            else:                
                left.append(num)        
        return quick_sort(left) + [base] + quick_sort(right)    
    else:        
        return m

归并排序

归并排序（Merge Sort）是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

理解归并排序：
就是将整个列表先分割成数个子列表，然后对这几个子列表进行排序，最后再进行归并操作。

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = int( len(arr) / 2 ) # 通过递归不停的分割子列表
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    
    # 分割后的子列表排序后归并并层层返回
    l, r = 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