07-排序

当我们取出来自数据库的数据后，可能需要对数据进行相应的排序，方便后期的数据处理。

1. 什么是排序

按照既定的规则对数据的索引进行排列，使得数据按照我们的要求进行展示。

2. 数据的分类

• 2.1 冒泡排序

  • 冒泡排序通过将所有的数据中最大（最小的值）选出来放在最前面（最后面），再通过循环，从而实现了排序

    
    冒泡排序过程图

• 2.2 选择排序

  • 选择排序通过将数据分为两部分，一部分是已排序（最开始为第一个或者最后一个），剩余的部分是未排序部分。在未排序部分中，选择最小或者最大的数和已排序部分再进行排序。

    
    选择排序过程图

• 2.3 插入排序

  • 插入排序的过程是直接按照索引进行数据选取，再将已经选取的数据进行一次排序

    
    插入排序过程图

• 2.4 归并排序

  • 先将数据拆分为一个一个的元素，再在合并元素的过程中排序

    
    归并排序过程

• 2.5 快速排序

  • 将数据分为三部分，中间部分（索引的中间）为一个确定的值，左边部分都比中间小（大），右边部分都比中间大（小），循环直到都拆分为一个一个的单元格，最后归并起来。

    
    快速排序过程图

• 2.6 总结

  • 以上排序方法，主要是针对数据的拆分和排列部分分成了以上5种方法。因此，理解以上5中排序算法时，可以根据拆分方式和排列方式进行分类理解。

3. 代码

3.1 冒泡排序

def bubble_sort(array):
    count = len(array)-1
    for i in range(count):
        temp_c = True
        for j in range(count-i):
            if num[j] > num[j+1]:
                num[j],num[j+1] = num[j+1],num[j]
                temp_c =False

3.2 选择排序

def selector_sort(array):
    for j in range(len(array)-1): 
        min_index = j
        for i in range(min_index+1,len(array)):
            if array[i] < array[min_index]:
                min_index = i
        array[j],array[min_index] = array[min_index],array[j]

3.3 插入排序

def insert_sort(array):
    for i in range(1,len(array)):
        for j in range(i,0,-1):
            if array[j] < array[j-1]:
                array[j],array[j-1] =array[j-1],array[j]

3.4 归并排序

def merge_sort(list_data):
    if len(list_data) <= 1:
        return list_data
    count = int (len(list_data)/2)
    # 递归直到拆分为一个一个的单元格
    left  = merge_sort(list_data[:count])
    right = merge_sort(list_data[count:])
    return merge(left,right)

def merge(left,right):
    l,r = 0,0
    result=[]
    # 递归函数会一直往上传递直到合并完毕 
    while l < len(left) and r<len(right):
        if left[l] < right[r]:
            result.append(left[l])
            l = l+1 
        else:
            result.append(right[r])
            r += 1
    result += list(left[l:])
    result += list(right[r:])
    return result

3.5 快速排序

def quick_sort(array):
    if len(array) >=2:
        mid = array[len(array)//2]
        left ,right =[],[]
        array.remove(mid)
        for data in array:
            if data < mid:
                left.append(data)
            else:
                right.append(data)
        return quick_sort(left) + [mid] + quick_sort(right)
    else:
        return array