10种排序算法

排序low B三人组

1、冒泡排序：

思路：遍历列表列表中的元素，如果当前元素比后面相邻的元素大，那么就交换，最大的数也就‘浮’在最后。
代码：

# -*- coding:utf-8 -*-
# @File    : bubble_sort.py
# @Author  : Clint
import random

def bubble_sort(data_list):     # 冒泡排序  O(n^2)
    for i in range(len(data_list)-1):
        for j in range(len(data_list)-i-1):
            if data_list[j] < data_list[j+1]:
                data_list[j], data_list[j+1] = data_list[j+1], data_list[j]

data = list(range(100))
random.shuffle(data)     # 洗牌函数，将有序的列表打乱
bubble_sort(data)
print(data)

优化后的冒泡排序

# -*- coding:utf-8 -*-
# @Author  : Clint

def bubble_sort(data_list):     # 优化后的冒泡排序 最好情况下的时间复杂时间是O(n)
    for i in range(len(data_list)-1):
        exchange = False
        for j in range(len(data_list)-i-1):
            if data_list[j] < data_list[j+1]:
                data_list[j], data_list[j+1] = data_list[j+1], data_list[j]
                exchange = True
        if not exchange:
            break

2、选择排序：

思路：一趟遍历最小的数，放到第一个位置；再一趟遍历剩余列表中最小的数，继续放置已排序元素后面；... 排序完成。
问题：怎么选出最小的数？
代码：

# -*- coding:utf-8 -*-
# @Author  : Clint
# @File    : select_sort.py

def select_sort(data_list):     # 选择排序  O(n^2)
    for i in range(len(data_list)-1):
        min_loc = i
        for j in range(i+1, len(data_list)):
            if data_list[j] < data_list[min_loc]:
                min_loc = j
        data_list[i], data_list[min_loc] = data_list[min_loc], data_list[i]

data = [3, 5, 7, 4, 2, 6, 33, 0, 54]
select_sort(data)
print(data)

3、插入排序：

思路：列表被分为有序区和无序区两个部分，最初有序区只有一个元素（第一次元素）；从无序区遍历一个元素，在有序区从后往前扫描，找到相应位置并插入，直到无序区变空
代码：

# -*- coding:utf-8 -*-
# @Author  : Clint

def insert_sort(data_list):　　　　# 插入排序　O(n^2)
    for i in range(1, len(data_list)):
        temp = data_list[i]
        j = i-1
        while j >= 0 and data_list[j] > temp:
            data_list[j+1],data_list[j] = data_list[j], temp 　　　　　　　
            j -= 1 
data = [7,5,8,6,3,1,2,9,0] 
insert_sort(data) 
print(data)

# PS： 插入排序有个优化空间：应用二分查找来寻找插入点

排序NB二人组

4、堆排序：

前置知识点：
树：

1.树是一种数据库结构，如：目录结构
2.树是一种可以递归定义的数据结构
3.树是由n个节点组成的集合：
如果n=0，那这是一颗空树；
如果n>0，那存在1个节点作为树的根节点，其他节点可以分为m个集合，每个集合本身又是一棵树。
相关概念：根节点、叶子节点；树的深度(高度)；树的度；孩子节点、父节点；子树等等；

二叉树：
二叉树的储存方式：链式储存、顺序存储(列表)

堆：
大根堆：一颗完全二叉树，满足任一节点都比其孩子节点大
小根堆：一颗完全二叉树，满足任一节点都比其孩子节点小

思路：

1.建立堆（sift）；
2.得到堆顶，为最大元素
3.去掉堆顶，将堆最后一个元素放到堆顶，此时可通过一次调整重新使堆有序；
4.堆顶元素为第二大元素；
5.重复步骤3，直到堆变空；

代码：

# -*- coding:utf-8 -*-
# @Author  : Clint

# 升序 建大根堆
def sift(data_list, low, high):
    i = low         # 最开始的父节点
    j = 2*i+1       # 最开始的左子节点
    tmp = data_list[i]
    while j <= high:    # 如果子节点没到子树的最后，那么继续
        if data_list[j] < data_list[j+1] and j+1 <= high:
            j += 1
        if tmp < data_list[j]:   # 如果父节点比子节点小
            data_list[i] = data_list[j]   # 那么父子节点互换
            i = j                # 字节点成为父节点
            j = 2*i+1            # 新子节点
        else:
            break
    data_list[i] = tmp

def heap_sort(data_list):
    n = len(data_list)
    for i in range(n//2 - 1, -1, -1):
        sift(data_list, i, n-1)
    # 堆建好了
    for i in range(n-1, -1, -1):    # i指向堆的最后
        data_list[0], data_list[i] = data_list[i], data_list[0]     # 父节点出局，堆的最后叶子节点上位
        sift(data_list, 0, i-1)     # 调整出新的父节点

data = [7, 5, 8, 6, 3, 1, 2, 9, 0]
heap_sort(data)
print(data)　　# 升序排列，若要降序排列，则建小根堆即

5、归并排序

思路：
1.将列表越分越小，直至分成一个元素；
2.把一个元素理解成是是有序的；
3.合并：将两个有序列表归并，列表越来越大；

代码：

# -*- coding:utf-8 -*-
# @Author  : Clint
import sys
import random
sys.setrecursionlimit(10000)  # python最大递归数为999

def one_merge(data_list, low, mid, high):       # 一次归并
    i = low
    j = mid + 1
    lda = []
    while i <= mid and j <= high:
        if data_list[i] < data_list[j]:
            lda.append(data_list[i])
            i += 1
        else:
            lda.append(data_list[j])
            j += 1
    while i <= mid:
        lda.append(data_list[i])
        i += 1
    while j <= high:
        lda.append(data_list[j])
        j += 1
    data_list[low:high+1] = lda

def merge_sort(data_list, low, high):       # 合并排序 O(nlogn)
    if low < high:
        mid = (low + high)//2
        merge_sort(data_list, low, mid)         # 递归实现
        merge_sort(data_list, mid+1, high)
        one_merge(data_list, low, mid, high)

data = list(range(100))
random.shuffle(data)     # 洗牌函数，将有序的列表打乱
print(data)
merge_sort(data, 0, len(data)-1)
print(data)

其他更优方案

6、快速排序：

思路：取一个元素p（第一个元素），使元素p归位；列表被p分成两部分，左边都比p小，右边都比p大；递归完成排序
算法关键点：1.整理；2.递归
代码：

# -*- coding:utf-8 -*-
# @Author  : Clint

def quick_sort(data_list, left, right):         # 快速排序 O(nlogn)
    if left < right:
        mid = partition(data_list, left, right)
        quick_sort(data_list, left, mid-1)
        quick_sort(data_list, mid+1, right)

def partition(data_list, left, right):
    temp = data_list[left]
    while left < right:
        while left < right and data_list[right] >= temp:
            right -= 1
        data_list[left] = data_list[right]
        while left < right and data_list[left] <= temp:
            left += 1
        data_list[right] = data_list[left]
    data_list[left] = temp
    return left

data = [7, 5, 8, 6, 3, 1, 2, 9, 0]
quick_sort(data, 0, len(data)-1)
print(data)

7、希尔排序

实质上是一种分组的插入排序；

思路：
1.首先取一个整数d1 = n / 2，将元素分为d1个组，每组相邻的元素之间距离为d1，在各组内进行直接插入排序；
2.取第二个整数d2 = d1 / 2 ，重复上述分组排序过程，直到 di = 1，既所有元素在同一组内进行直接插入排序；
PS：希尔排序每趟并不使某些元素有序，而是使整体数据越来越接近有序；最后一趟排序使得所有数据有序。

代码：

# -*- coding:utf-8 -*-
# @Author  : Clint

def shell_sort(data_list):          # 希尔排序 O（n(1+T)）
    gap = len(data_list) // 2
    while gap > 0:
        for i in range(gap, len(data_list)):
            temp = data_list[i]
            j = i-gap
            while j >= 0 and temp < data_list[j]:
                data_list[j+gap] = data_list[j]
                j -= gap
            data_list[j+gap] =temp
        gap /= 2