概述

内部排序：待排序记录存放在计算机内存中进行的排序过程。

外部排序：待排序记录的数量很大，以致于内存不能一次容纳全部记录，所以在排序过程中需要对外存进行访问的排序过程。

排序

算法实现

直接插入排序

1.核心思想
直接插入排序（Insert Sort）是插入排序的一种，从第二个元素开始遍历，每次取出一个元素开始遍历，跟左边那个元素进行比较：比左边大则不动；比左边小，就和左边替换，继续向左遍历，直到找到该插入的位置。

2.代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
def directSort(arr):
    if len(arr) <= 1:
        return arr
    for i in range(1,len(arr)):
        while i > 0 and arr[i] < arr[i-1]:
            arr[i],arr[i-1] = arr[i-1],arr[i]
            i = i - 1
    return arr
    
arr = [64, 34, 25, 12, 22, 11, 90]

b = directSort(arr)
print(b)

3.性能
稳定排序
时间复杂度：O（n2）
空间复杂度：O（1）

冒泡排序

1.核心思想
冒泡排序（Bubble Sort）也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端。
2.代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def bubbleSort(arr):
    n = len(arr)
    # 遍历所有数组元素
    for i in range(n):

        # Last i elements are already in place
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

arr = [64, 34, 25, 12, 22, 11, 90]

b = bubbleSort(arr)
print(b)

3.性能
稳定排序
时间复杂度：O（n2）
空间复杂度：O（1）

基数排序

1.核心思想
基数排序(Radix Sort)是一种非比较型整数排序算法，是桶排序的扩展。算法实现步骤：

  1. 取得数组中的最大数，并取得位数；
  2. 对数位较短的数前面补零；
  3. 分配，先从个位开始，根据位值(0-9)分别放到0~9号桶中;
  4. 收集，再将放置在0~9号桶中的数据按顺序放到数组中;
  5. 重复3~4过程，直到最高位，即可完成排序。

2.代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
def radix_sort(arr):
    n = len(str(max(arr)))  # 记录最大值的位数
    for k in range(n):  # n轮排序
        # 每一轮生成10个列表
        bucket_list = [[] for i in range(10)]  # 因为每一位数字都是0~9，故建立10个桶
        for i in arr:
            bucket_list[i//(10**k) % 10].append(i)  # 按第k位放入到桶中
        arr = [j for i in bucket_list for j in i]  # 按当前桶的顺序重排列表
    return arr

arr = [64, 34, 25, 12, 22, 11, 90]
b = radix_sort(arr)
print(b)

3.性能
稳定排序
时间复杂度：O（d（n+r））
空间复杂度：O（r）

归并排序

1.核心思想
归并排序是典型的分治法应用。先递归分解数组，再合并数组。
原理：将数组分解最小之后，然后合并两个有序数组，基本思想是比较两个数组最前面的数，取小值，然后将相应指针后移一位。然后再比较，直到一个数组为空，最后把另一个数组的剩余部分复制过来即可。

2.代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    # 二分分解
    num = len(arr) // 2
    left = merge_sort(arr[:num])
    right = merge_sort(arr[num:])
    # 合并
    return merge(left, right)

def merge(left, right):
    '''合并操作，将两个有序数组left[]和right[]合并成一个大的有序数组'''
    # 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 += 1
        else:
            result.append(right[r])
            r += 1
    result += left[l:]
    result += right[r:]
    return result

arr = [64, 34, 25, 12, 22, 11, 90]
b = merge_sort(arr)
print(b)

3.性能
稳定排序
时间复杂度：O（nlogn）
空间复杂度：O（n）

希尔排序

1.核心思想
希尔排序（shell_Sort），也称递减增量排序算法，是插入排序的一种更高效的改进版本。基本思想：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。
希尔排序
2.代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def shellSort(arr):
    n = len(arr)
    gap = int(n / 2)

    while gap > 0:

        for i in range(gap, n):

            temp = arr[i]
            j = i
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = temp
        gap = int(gap / 2)
    return arr

arr = [64, 34, 25, 12, 22, 11, 90]

b = shellSort(arr)
print(b)

3.性能
不稳定排序
时间复杂度：O（n1.3）
空间复杂度：O（1）

快速排序

1.核心思想
快速排序(quick sort)采用了分治的策略。基本思想：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行。

  1. 优先设置两个变量i和j,设置元素位置i=0,j=len(array)-1;
  2. 选取第一个元素作为基准值，即：base = array[i];
  3. j向左开始移动，每次移动一个元素，即j-=1，直到该元素小于基准值时停下，此时将该值赋值给array[i]，即：array[i] = array[j];
  4. i向右开始移动，每次移动一个元素，即i+=1，直到该元素大于基准值时停下，此时将该值赋值给array[j]，即：array[j] = array[i];
  5. 重复执行3/4两个步骤，直到i=j时停下，此时即找到了基准值的位置，即：array[i] = base，目前也就完成了一次排序；
  6. 通过第一轮排序后得出前后两个半区，则继续递归执行前后两半区实现最终排序。

2.代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def QuickSort(arr, start, end):

    if start < end:  # 判断start是否小于end,如果为false,直接返回
        i, j = start, end
        base = arr[i]  # 设置基准数

        while i < j:
            while (i < j) and (arr[j] >= base):  # 如果列表后边的数比基准数大或相等,则前移一位直到有比基准数小的数
                j = j - 1
            arr[i] = arr[j]  # 如找到,则把第j个元素赋值给第i个元素

            while (i < j) and (arr[i] <= base):  # 同样的方式比较前半区
                i = i + 1
            arr[j] = arr[i]

        arr[i] = base  # 做完第一轮比较之后,列表被分成了两个半区,并且i=j，此时找到基准值

        # 递归前后半区
        # print(base, myList)
        QuickSort(arr, start, i - 1)
        QuickSort(arr, j + 1, end)
    return arr

arr = [64, 34, 25, 12, 22, 11, 90]
print("arr:",QuickSort(arr, 0, len(arr) - 1))

3.性能
不稳定排序
时间复杂度：O（nlogn）
空间复杂度：O（nlogn）

简单选择排序

1.核心思想
简单选择排序（simpleselect_Sort）：从无序数列中选取最小的元素和无序数列中的第一个元素交换，每轮都可以确定最小元素的位置。

2.代码实现

1
2
3
4
5
6
7
8
9
10
11
def simselect_Sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(i+1, n):
            if arr[j] < arr[i]:
                arr[j], arr[i] = arr[i], arr[j]
    return arr

arr = [64, 34, 25, 12, 22, 11, 90]
b = simselect_Sort(arr)
print(b)

3.性能
不稳定排序
时间复杂度：O（n2）
空间复杂度：O（1）

堆排序

1.核心思想

  1. 堆分为大根(顶)堆与小根(顶)堆，升序排序采用大根堆，降序排序采用小根堆。
  2. 堆是完全二叉树，利用层序遍历(遍历方式还有前中后)映射到数组后，假设树或子树的根节点为arr[root],则其对应的子节点分别为arr[root2+1],arr[root2+2]。
  3. 对于堆排序，基本思想是，将一个无序序列调整为一个大根堆，就可以找出这个序列的最大值，然后将这个最大值交换到序列的最后一个，这样有序序列元素就增加一个，无序序列元素就减少一个。对新的无序序列重复如上的操作，最终实现堆排序。即分为两块：1.大根堆的构建。2.首尾元素互换，序列长度减去1再构建大根堆。排序的过程就是每次待排序的序列长度减去1再执行这两步。

2.代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def big_endian(arr, start, end):  # 调整三个节点（root，lchild，rchild）为大根堆
    root = start
    while True:
        child = root * 2 + 1  # lchild
        if child > end:
            break
        if child + 1 <= end and arr[child] < arr[child + 1]:  # 找到左右孩子较大的孩子节点下标
            child += 1
        if arr[root] < arr[child]:  # 调整为大根堆
            arr[root], arr[child] = arr[child], arr[root]
            # root = child
        else:
            break

def heap_sort(arr):  # 堆排序
    first = len(arr) // 2 - 1
    for start in range(first, -1, -1):  # 初始化为大根堆
        big_endian(arr, start, len(arr) - 1)
    for end in range(len(arr) - 1, 0, -1):
        arr[0], arr[end] = arr[end], arr[0]  # 交换堆顶和堆末尾元素
        big_endian(arr, 0, end - 1)  # 然后把剩下堆元素调整为大根堆
    return arr

arr = [64, 34, 25, 12, 22, 11, 90]
b = heap_sort(arr)
print(b)

3.性能
不稳定排序
时间复杂度：O（nlogn）
空间复杂度：O（1）

排序算法复杂度总结

排序总结