Leaky Cauldron
0%

排序算法汇总

Posted on Edited on

参考资料: https://www.cnblogs.com/onepixel/p/7674659.html

比较排序

00. 冒泡排序

算法描述

  1. 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
  2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
  3. 针对所有的元素重复以上的步骤，除了最后一个；
  4. 重复步骤1~3，直到排序完成。

时间复杂度计算

算法实现

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


input_arr = [9, 10, 2, 44, 33, 5, 6, 0, 11]
bubble_sort(input_arr)
1
[0, 2, 5, 6, 9, 10, 11, 33, 44]

01. 插入排序

算法描述

插入排序都采用in-place在数组上实现。具体算法描述如下：

  1. 从第一个元素开始，该元素可以认为已经被排序；
  2. 取出下一个元素，在已经排序的元素序列中从后向前扫描；
  3. 如果该元素（已排序）大于新元素，将该元素移到下一位置；
  4. 重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置；
  5. 将新元素插入到该位置后；
  6. 重复步骤 2~5。

算法实现

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

    return arr


input_arr = [9, 10, 2, 44, 33, 5, 6, 0, 11]
insertion_sort(input_arr)
1
[0, 2, 5, 6, 9, 10, 11, 33, 44]

02. 希尔排序

算法描述

希尔排序也是一种插入排序, 它是简单插入排序经过改进之后的一个更高效的版本, 也称为缩小增量排序

简单插入排序很循规蹈矩, 不管数组分布是怎么样的, 依然一步一步的对元素进行比较, 移动, 插入, 如 [5,4,3,2,1,0] 这种倒序序列, 数组末端的 0 要回到首位置很是费劲, 比较和移动元素均需 n-1 次. 而希尔排序在数组中采用跳跃式分组的策略, 通过某个增量将数组元素划分为若干组, 然后分组进行插入排序, 随后逐步缩小增量, 继续按组进行插入排序操作, 直至增量为1. 希尔排序通过这种策略使得整个数组在初始阶段达到从宏观上看基本有序, 小的基本在前, 大的基本在后, 微调即可.

参考: https://www.cnblogs.com/chengxiao/p/6104371.html

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def shell_sort(arr):
    length = len(arr)
    gap = int(length / 2)

    while gap > 0:
        for i in range(gap, length):
            for j in range(i, -1, -gap):  # 相当于将插入排序的遍历的间隔由 1 改为 -gap, 即完成了分组
                if arr[j] < arr[j - gap] and j - gap >= 0:
                    arr[j], arr[j - gap] = arr[j - gap], arr[j]
        gap = int(gap / 2)


input_arr = [9, 10, 2, 44, 33, 5, 6, 0, 11]
shell_sort(input_arr)
print(input_arr)
1
[0, 2, 5, 6, 9, 10, 11, 33, 44]

03. 选择排序

算法描述

n 个记录的直接选择排序可经过 n-1 趟直接选择排序得到有序结果。具体算法描述如下：

  1. 初始状态: 无序区为 R[1..n]，有序区为空

  2. 第 i 趟排序 (i=1,2,3…n-1) 开始时, 当前有序区和无序区分别为 R[1..i-1] 和 R(i..n). 该趟排序从当前无序区中-选出关键字最小的记录 R[k], 将它与无序区的第 1 个记录 R 交换, 使 R[1..i] 和R[i+1..n] 分别变为记录个数增加 1 个的新有序区和记录个数减少 1 个的新无序区

  3. n-1 趟结束，数组有序化了。

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
def selection_sort(arr):
    length = len(arr)
    for i in range(length):
        min_index = i
        for j in range(i, length):
            min_index = j if arr[j] < arr[min_index] else min_index
        arr[i], arr[min_index] = arr[min_index], arr[i]
    return arr


input_arr = [9, 10, 2, 44, 33, 5, 6, 0, 11]
selection_sort(input_arr)
1
[0, 2, 5, 6, 9, 10, 11, 33, 44]

04. 堆排序

堆

堆需满足:

  1. 堆中某个节点的值总是不大于或不小于其父节点的值
  2. 堆总是一棵完全二叉树

将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

算法描述

  1. 将初始待排序关键字序列 (R1,R2…Rn) 构建成大顶堆，此堆为初始的无序区

  2. 将堆顶元素 R[1] 与最后一个元素 R[n] 交换, 此时得到新的无序区 (R1,R2,…Rn-1) 和新的有序区 (Rn), 且满足 R[1,2…n-1] <= R[n]

  3. 由于交换后新的堆顶 R[1] 可能违反堆的性质, 因此需要对当前无序区 (R1,R2,…Rn-1) 调整为新堆, 然后再次将 R[1] 与无序区最后一个元素交换, 得到新的无序区 (R1,R2…Rn-2) 和新的有序区 (Rn-1,Rn). 不断重复此过程直到有序区的元素个数为 n-1，则整个排序过程完成。

算法实现

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
30
31
32
33
34
35
36
37
38
39
40
41
def heap_sort(arr):
    heap_size = len(arr)
    for i in range(heap_size):
        heapify(arr, i)

    while heap_size > 0:
        heap_size -= 1
        arr[0], arr[heap_size] = arr[heap_size], arr[0]
        heap_adjust(arr, 0, heap_size)


# 将数组转化为堆, 若 index 处的节点大于父节点则交换, 循环直至满足堆条件
def heapify(arr, index):
    while arr[index] > arr[int((index - 1) / 2)]:
        arr[index], arr[int((index - 1) / 2)] = arr[int((index - 1) / 2)], arr[index]
        index = int((index - 1) / 2)


# 数组调整为最大堆
def heap_adjust(arr, index, heap_size):

    left = 2 * index + 1  # 当前节点的左孩子

    # 由堆的根节点开始向下调整，与其大孩子交换，逐层向下，使重新成堆
    while left < heap_size:
        # 求出左右子中较大的一个
        largest = left + 1 if left + 1 < heap_size and arr[left + 1] > arr[left] else left
        # 求孩子与父节点中较大的一个
        largest = largest if arr[largest] > arr[index] else index

        if largest == index:
            break

        arr[index], arr[largest] = arr[largest], arr[index]
        index = largest
        left = 2 * index + 1


input_arr = [9, 10, 2, 44, 33, 5, 6, 0, 11]
heap_sort(input_arr)
print(input_arr)
1
[0, 2, 5, 6, 9, 10, 11, 33, 44]

05. 归并排序

算法描述

  1. 把长度为n的输入序列分成两个长度为 n/2 的子序列；
  2. 对这两个子序列分别采用归并排序；
  3. 将两个排序好的子序列合并成一个最终的排序序列。

递归示例

1
2
3
4
5
6
7
8
9
10
11
12
# 递归查找最大值
def get_max(arr, L, R):  # L 和 R 为索引
    if (L == R):  # base case 问题划分到 base case 时停止划分
        return arr[L]
    mid = int((L + R) / 2)  # 写成 L + int((R - L) / 2) 可以防止溢出
    max_left = get_max(arr, L, mid)
    max_right = get_max(arr, mid + 1, R)
    return max(max_left, max_right)


input_arr = [9, 10, 2, 44, 33, 5, 6, 0, 11]
get_max(input_arr, 0, len(input_arr) - 1)
1
44

算法实现

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
30
31
32
33
34
35
36
37
38
39
# 递归过程
def sort_process(arr, L, R):
    if (L == R):
        return
    mid = L + int((R - L) / 2)
    sort_process(arr, L, mid)
    sort_process(arr, mid + 1, R)
    merge(arr, L, mid, R)


# 合并过程, 非递归
def merge(arr, L, mid, R):
    tmp = []
    p1 = L
    p2 = mid + 1

    while p1 <= mid and p2 <= R:  # p1 p2 均不越界时
        if arr[p1] < arr[p2]:
            tmp.append(arr[p1])
            p1 += 1
        else:
            tmp.append(arr[p2])
            p2 += 1

    while (p1 <= mid):
        tmp.append(arr[p1])
        p1 += 1

    while (p2 <= R):
        tmp.append(arr[p2])
        p2 += 1

    for i in range(len(tmp)):
        arr[L + i] = tmp[i]


input_arr = [9, 10, 2, 44, 33, 5, 6, 0, 11]
sort_process(input_arr, 0, len(input_arr) - 1)
print(input_arr)
1
[0, 2, 5, 6, 9, 10, 11, 33, 44]

小和问题

描述

在一个数组中, 每一个数左边比当前数小的数累加起来, 叫做这个数组的小和. 求数组 [1, 3, 4, 2, 5] 的小和.

  • 1左边比1小的数，没有
  • 3左边比3小的数, 1
  • 4左边比4小的数, 1, 3
  • 2左边比2小的数, 1
  • 5左边比5小的数, 1, 3, 4, 2

所以小和为 1+1+3+1+1+3+4+2=16

基于归并排序的实现
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
def sort_process(arr, L, R):
    if (arr[L] == arr[R]):
        return 0
    mid = L + int((R - L) / 2)
    return sort_process(arr, L, mid) +\
            sort_process(arr, mid + 1, R) + \
            merge(arr, L, mid, R)


def merge(arr, L, mid, R):
    tmp = []
    p1 = L
    p2 = mid + 1
    result = 0

    while p1 <= mid and p2 <= R:
        if arr[p1] < arr[p2]:
            result += (R - p2 + 1) * arr[p1] if arr[p1] < arr[p2] else 0
            tmp.append(arr[p1])

            p1 += 1
        else:
            tmp.append(arr[p2])
            p2 += 1

    while p1 <= mid:
        tmp.append(arr[p1])
        p1 += 1

    while p2 <= R:
        tmp.append(arr[p2])
        p2 += 1

    for i in range(len(tmp)):
        arr[L + i] = tmp[i]

    return result


def cal_small_sum(arr):
    if arr is None or len(arr) < 2:
        return 0
    print('小和为: %d' % sort_process(arr, 0, len(arr) - 1))


input_arr = [1, 3, 4, 2, 5]
cal_small_sum(input_arr)
1
小和为: 16

06. 快速排序

算法描述

快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：

  1. 从数列中挑出一个元素，称为 “基准”（pivot）
  2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作
  3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

参考

算法实现

原始实现

单侧扫描, 将小于 p 的数字放到 p 的左边, 大于 p 的不动

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def partition(arr: list, l: int, r: int):
    lp = l # 记录左指针位置, 每当有满足条件的值时就与 lp 交换位置, 并自增

    for i in range(l, r + 1):
        if arr[i] <= arr[r]:
            arr[lp], arr[i] = arr[i], arr[lp]
            lp += 1


def quick_sort(arr: list, l: int, r: int):
    for i in range(r, l - 1, -1):
        partition(arr, l, i)


input_arr = [9, 8, 7, 4, 8, 3, 5, 2, 4, 1]
quick_sort(input_arr, 0, len(input_arr) - 1)
print(input_arr)
1
[1, 2, 3, 4, 4, 5, 7, 8, 8, 9]
递归实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def partition(arr: list, l: int, r: int):
    lp = l # 记录左指针位置, 每当有满足条件的值时就与 lp 交换位置, 并自增

    for i in range(l, r + 1):
        if arr[i] <= arr[r]:
            arr[lp], arr[i] = arr[i], arr[lp]
            lp += 1


def quick_sort(arr: list, l: int, r: int):
    if l < r:
        partition(arr, l, r)
        quick_sort(arr, l, r - 1)


input_arr = [9, 8, 7, 4, 8, 3, 5, 2, 4, 1]
quick_sort(input_arr, 0, len(input_arr) - 1)
print(input_arr)
1
[1, 2, 3, 4, 4, 5, 7, 8, 8, 9]
改进实现

两端扫描

  1. 使用两个变量 less 和 more, less 指向首元素的元素下一个元素(最左边的首元素为中轴元素), more 指向最后一个元素
  2. 从前往后找, 找到一个比中轴元素大的, 然后从后往前找, 找到一个比中轴元素小的, 然后交换这两个元素, 直到这两个变量交错 ( less > more ) (注意不是相遇 less == more，因为相遇的元素还未和中轴元素比较)
  3. 对左半数组和右半数组重复上述操作.
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
30
31
32
33
34
35
# 改进实现, 双侧移动, 取最左侧为中轴元素
def partition(arr: list, l: int, r: int) -> int:
    """
    r(在右侧找到比中轴小的元素) => l(中轴)
    l(在左侧找到比中轴大的元素) => r(在右侧找到比中轴小的元素)
                      中轴值 => l/r(此时 l == r, 即 l 和 r 均指向左右部分的交界)
    """
    p = arr[l]
    while l != r:
        while l < r and arr[r] >= p:
            r -= 1
        arr[l] = arr[r]  # 在右侧找到比中轴小的元素

        while l < r and arr[l] <= p:
            l += 1
        arr[r] = arr[l]  # 在左侧找到比中轴大的元素

    arr[l] = p  # 此时 L = R, 即把中轴值赋给左右部分的交界位置
    return l  # 返回中轴索引


def quick_sort(arr: list, l: int, r: int) -> list:
    if l < r:
        p_index = partition(arr, l, r)

        # 中轴已经排好, 递归时可去除中轴
        quick_sort(arr, l, p_index - 1)
        quick_sort(arr, p_index + 1, r)

    return arr


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

随机快速排序

以上为经典快速排序, 在中轴值两侧数分布不均匀时, 时间复杂度很高, 所以一般使用随机快速排序

随机快速排序算法实现
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
30
31
32
33
34
35
36
import random


def partition(arr: list, l: int, r: int):
    # 随机选取一个数与中轴值上的数交换
    rand_index = random.randint(l, r)
    arr[rand_index], arr[l] = arr[l], arr[rand_index]

    p = arr[l]
    while l != r:
        while l < r and arr[r] >= p:
            r -= 1
        arr[l] = arr[r]  # 在右侧找到比中轴小的元素

        while l < r and arr[l] <= p:
            l += 1
        arr[r] = arr[l]  # 在左侧找到比中轴大的元素

    arr[l] = p  # 此时 L = R, 即把中轴值赋给左右部分的交界位置
    return l  # 返回中轴索引


def quick_sort(arr: list, l: int, r: int):
    if l < r:
        p_index = partition(arr, l, r)

        # 中轴已经排好, 递归时可去除中轴
        quick_sort(arr, l, p_index - 1)
        quick_sort(arr, p_index + 1, r)

    return arr


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

衍生问题

荷兰国旗问题

现有红白蓝三种不同颜色的小球，乱序排列在一起，请重新排列这些小球，使得红白蓝三色的同颜色的球在一起。这个问题之所以叫荷兰国旗问题，是因为我们可以将红白蓝三色小球想象成条状物，有序排列后正好组成荷兰国旗。

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 partition(arr, L, R):
    p = arr[L]
    while L != R:
        while L < R and arr[R] >= p:
            R -= 1
        arr[L] = arr[R]

        while L < R and arr[L] <= p:
            L += 1
        arr[R] = arr[L]

    arr[L] = p
    return L


def netherland_flag(arr, L, R):
    if L < R:
        p = partition(arr, L, R)

        netherland_flag(arr, L, p - 1)
        netherland_flag(arr, p + 1, R)


input_arr = [0, 2, 1, 0, 2, 1, 2, 2, 1, 0]
netherland_flag(input_arr, 0, len(input_arr) - 1)
print(input_arr)
1
[0, 0, 0, 1, 1, 1, 2, 2, 2, 2]
奇偶划分

给出一列数, 按奇偶划分, 左侧为奇数, 右侧为偶数, 要求不额外创建数组, 划分后奇数与奇数, 偶数与偶数之间顺序与划分前相同.

采用快排类似的算法, 需保证 partition 部分为稳定排序, 难以实现

非比较排序

01. 计数排序

算法描述

  1. 找出待排序的数组中最大和最小的元素
  2. 统计数组中每个值为 i 的元素出现的次数, 存入数组 C 的第 i 项
  3. 对所有的计数累加(从 C 中的第一个元素开始, 每一项和前一项相加)
  4. 反向填充目标数组: 将每个元素i放在新数组的第 C(i) 项, 每放一个元素就将 C(i) 减去 1

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def counting_sort(arr):
    """
    原算法使用数组保存数据, 因使用下标所以有序
    本实现使用字典, 保存时无序, 输出时按序取出, 可减小一定的空间复杂度
    """
    bucket = dict()
    max_value = max(arr)
    min_value = min(arr)

    for i in arr:
        bucket[i] = bucket.get(i, 0) + 1

    index = 0

    for i in range(min_value, max_value + 1):
        if bucket.get(i) is not None:
            for j in range(bucket[i]):
                arr[index] = i  # 放回原数组, 减小空间复杂度
                index += 1


input_arr = [5, 3, 8, 5, 6, 7, 4, 9, 2]
counting_sort(input_arr)
print(input_arr)
1
[2, 3, 4, 5, 5, 6, 7, 8, 9]

02. 桶排序

算法描述

  1. 设置一个定量的数组当作空桶
  2. 遍历输入数据，并且把数据一个一个放到对应的桶里去
  3. 对每个不是空的桶进行排序
  4. 从不是空的桶里把排好序的数据拼接起来

算法实现

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
30
31
def bucket_sort(arr, bucket_size):
    max_value = max(arr)
    min_value = min(arr)

    # 桶的初始化
    buckets = []
    bucket_num = int((max_value - min_value) / bucket_size) + 1
    for i in range(bucket_num + 1):
        buckets.append([])

    for ele in arr:
        buckets[int((ele - min_value) / bucket_size)].append(ele)

    # 对桶内元素进行插入排序
    for bucket in buckets:
        for i in range(len(bucket)):
            for j in range(i - 1, -1, -1):
                if bucket[j] > bucket[j + 1]:
                    bucket[j], bucket[j + 1] = bucket[j + 1], bucket[j]

    index = 0
    # 将结果填回原数组
    for bucket in buckets:
        for i in bucket:
            arr[index] = i
            index += 1


input_arr = [5, 3, 8, 5, 6, 7, 4, 9, 2]
bucket_sort(input_arr, 5)
print(input_arr)
1
[2, 3, 4, 5, 5, 6, 7, 8, 9]

衍生问题

最大间隔问题 (leetcode 164)

给定 n 个实数 x1, x2, ..., xn, 求这 n 个实数在实轴上相邻两个数之间的最大差值, 要求设计线性的时间算法

时间线性, 故不能采用排序算法, 可采用抽屉原理, 即为桶排序, 在输入过程中找出数据的最大值 max_ 与最小值 min_, 在 (min_, max_) 区间内, 将最大值与最小值之间进行均分成 n-1 份, 每个区间的大小为 len = (max_ - min_)/(n-1) 即此时为 n-1 个桶, 将最大值最小值人为放置于第一个桶和最后一个桶中, 分别代表了各自桶的上限和下限. 根据这个判断剩余的 n-2 个元素放置的桶的位置, 因为有 n-1 个桶需要放置 n-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
30
31
32
33
34
35
def max_gap(arr):
    if len(arr) <= 1:
        return 0
    max_value = max(arr)
    min_value = min(arr)

    if max_value == min_value:
        return 0

    length = len(arr)

    # 创建 N + 1 个桶
    maxs = [0] * (length + 1)
    mins = [0] * (length + 1)
    has_num = [False] * (length + 1)

    for ele in arr:
        index = int((ele - min_value) * length / (max_value - min_value))
        mins[index] = ele if not has_num[index] else min(ele, mins[index])
        maxs[index] = ele if not has_num[index] else max(ele, maxs[index])
        has_num[index] = True

    max_gap = 0

    tmp_max = maxs[0]
    for i in range(1, length + 1):
        if has_num[i]:
            max_gap = max(mins[i] - tmp_max, max_gap)
            tmp_max = maxs[i]

    return max_gap


input_arr = [3, 1, 12, 111, 123, 44, 54, 66]
max_gap(input_arr)
1
45

03. 基数排序

算法描述

  1. 取得数组中的最大数，并取得位数
  2. arr 为原始数组, 从最低位开始取每个位组成 radix 数组
  3. 对 radix 进行计数排序(利用计数排序适用于小范围数的特点)

算法实现

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
30
31
32
33
34
35
36
37
38
39
40
# 获取指定位上的数字, 索引从 0 开始
def get_digit(x, digit):
    return x // 10 ** digit % 10


# 获取最大数的位数
def max_digit_length(arr):
    max_value = max(arr)
    length = 0

    while max_value != 0:
        length += 1
        max_value //= 10

    return length


def radix_sort(arr):
    max_length = max_digit_length(arr)

    for i in range(max_length):
        bucket_dict = dict()
        for ele in arr:
            digit = get_digit(ele, i)
            if bucket_dict.get(digit):
                bucket_dict[digit].append(ele)
            else:
                bucket_dict[digit] = [ele]

        index = 0
        for j in range(10):
            if bucket_dict.get(j):
                for ele in bucket_dict[j]:
                    arr[index] = ele
                    index += 1


input_arr = [999, 101, 22, 32, 45, 5, 14, 90, 1, 1, 2, 3, 44]
radix_sort(input_arr)
print(input_arr)
1
[1, 1, 2, 3, 5, 14, 22, 32, 44, 45, 90, 101, 999]

后记

在 Java, C++ 中使用的综合排序, 当输入数组的长度小于某值时采用的是插入排序, 当大于某长度时采用的是归并排序或快速排序.

当数组中要排序的元素是自定义类型时, 通常采用归并排序; 当元素为基本类型(如 int, double, char 等)时, 采用的是快速排序. 差别在于排序算法的稳定性, 归并排序可保证排序后的数组保留部分原有数组的顺序, 对基本类型来说相等元素的顺序并不重要, 但对自定义类型来说可能有一定的意义.