数据结构-排序

内排序

插入排序

在已排序的表中插入数据，可在插入数据时确定位置。

冒泡排序

对长度为 n 的表进行 n 趟冒泡。

选择排序

对长度为 n 的表进行 n 趟排序，每趟找出最小值。

希尔排序

设置增量$d_i$,执行$d_i$趟排序，每趟$d_i$<上一趟的$d_i$，找出下标是$d_i$整数被的元素，分为$d_i$组，进行组内插入排序。

d = 3；
arr= 1 5 4 10 24 7 6 12 3；
1t  [1     10      6]       ->[1  6 10] |
      [5      24      12]   ->[5 12 24] |
        [4       7       3] ->[3  4  7] v
                              [1 5 3 6 12 4 10 24 7]
d = 2;
arr= 1 5 3 6 12 4 10 24 7;
2t  [1   3   12   10    7] ->[1 3 7 10 12]|
      [5   6    4    24]   ->[4 5 6 24]   v
                             [1 4 3 5 7 6 10 24 12]
d = 1;
arr= 1 4 3 5 7 6 10 24 12;
3t  [1 3 4 5 6 7 10 12 24]

堆排序

${K_i \in S} K_i \ge k_{2i+m} K_i \le k_{2i+m} m \in {0,1}$

1. 建立初始大/小根堆
2. 拆大/小根
3. 调整新堆

归并排序

[1,3,5,7,9];
[10,8,6,4,2];
[1,10|3,8|5,6|4,7|2,9];
[1,3,8,10|4,5,6,7|2,9];
[1,3,4,5,6,7,8,10|2,9];
[1,2,3,4,5,6,7,8,9,10];

基数排序

1 5 4 10 24 7 6 12 3->[01,05,04,10,24,07,06,12,03];
1turn:
0:[01,05,04,07,06,03];
1:[10,12];
2:[24];
2turn:
0:{1:02,3:03,4:04,5:05,6:06,7:07};
1:{0:10,2:12}
2:{4:24}
done;

外排序

对于大文件，不能全部读取到内存中，就需要使用外排序，一般使用归并排序算法。