排序

假设\(K_i=K_j (1 \leq i \leq n,1 \leq j \leq n,i \neq j)\),且在排序前的序列中\(R_i\)领先于\(R_j\)(即i<j)。若在排序后的序列中\(R_i\)仍领先于\(R_j\),则称所用的排序方法是稳定的;反之,若可能使排序后的序列中Rj领先于Ri,则称所用的排序方法是不稳定的

1
2
3
4
5
6
7
8
9
10
11
#define MAXSIZE 20
typedef int KeyType
typedef struct {} InfoType
typedef struct {
KeyType key; // 关键字项
InfoType otherinfo; // 其他数据项
}RedType;
typedef struct {
RedType r[MAXSIZE+1]; // r[0]闲置或用做哨兵单元
int length; // 顺序表长度
}SqList; // 顺序表类型

插入排序

每一趟将一个待排序的记录,按其关键字的大小插入到已经排好序的一组记录的适当位置上,直到所有待排序记录全部插入为止

直接插入排序

将一条记录插入到已排好序的有序表中,从而得到一个新的、记录数量增1的有序表

  • 时间复杂度: \(O(n^2)\)
  • 空间复杂度: \(O(1)\)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void InsertSort(SqList *L)
{
for (int i = 2; i <= L.length; i++)
{
if (L.r[i].key < L.r[i-1].key)
{
L.r[0] = L.r[i]; // 将待插入的记录暂存到监视哨中
L.r[i] = L.r[i-1]; // r[i-1]后移
// 从后向前寻找插入位置
for (int j = i - 2; L.r[0].key < L.r[j].key; j++)
{
L.r[j+1] = L.r[j]; // 记录逐个后移,直到找到插入位置
}
L.r[j+1] = L.r[0]; // 将r[0]即r[i],插入到正确位置
}
}
}

折半插入排序

  • 时间复杂度: \(O(n^2)\)
  • 空间复杂度: \(O(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
void BInsertSort(SqList *L)
{
for (int i=2;i<=L.length;i++)
{
L.r[0] = L.r[i];
int low=1; high=i-1;
// 折半查找
while (low <= high)
{
int m = (low + high) / 2;
if (L.r[0].key < L.r[m].key)
{
high = m -1;
} else {
low = m + 1;
}
}
// 记录后移
for (int j=i-1;j>=high+1;j--)
{
L.r[j+1] = L.r[j];
}
L.r[high+1] = L.r[0];
}
}

希尔排序(缩小增量排序)

  • 时间复杂度: 当增量序列为\(dt[k]=2^{t−k+1}−1\)时,希尔排序的时间复杂度为\(O(n^{3/2})\),其中t为排序趟数, \(1 \leq k \leq t \leq \lfloor log_2{(n+1)} \rfloor\)。还有人在大量的实验基础上推出:当n在某个特定范围内,希尔排序所需的比较和移动次数约为\(n^{1.3}\),当n→∞时,可减少到\(n(log_2n)^2\)
  • 空间复杂度: \(O(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
void ShellInsert(SqList *L, int dk)
{
for (int i=dk+1; i <=L.length; i++)
{
// 将L.r[i]插入有序增量列表
if (L.r[i].key < L.r[i-dk].key)
{
int j=0;
L.r[0] = L.r[i];
for (j=i-dk; j>0&&L.r[0].key<L.r[j].key; j-=dk)
{
L.r[j+dk] = L.r[j];
}
L.r[j+dk] = L.r[0];
}
}
}

void ShellSort(SqList *L, int dt[], int t)
{
// 按增量序列dt[0..t-1]对顺序表L作t趟希尔排序
for (int k=0; k<t; k++)
{
ShellInsert(L, dt[k]);
}
}

交换排序

冒泡排序

  • 时间复杂度: \(O(n^2)\)
  • 空间复杂度: \(O(1)\)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void BubbleSort(SqList *L)
{
int m = L.length-1;
// 用于标记某一趟排序是否发生交换
int flag = 1;
while (m>0&&flag==1)
{
flag = 0;
for (int j=1; j<=m; j++)
{
if (L.r[j].key > L.r[j+1].key)
{
flag = 1;
RedType t = L.r[j];
L.r[j] = L.r[j+1];
L.r[j+1] = t;
}
m--;
}
}
}

快速排序

快速排序是由冒泡排序改进而得到的。在冒泡排序过程中,只有相邻的两个记录进行比较,因此每次交换两个相邻记录时只能消除一个逆序,如果通过两个(不相邻)记录的一次交换,消除多个逆序,则会大大加快排序的速度

  • 时间复杂度\(O(nlog_2n)\)
  • 空间复杂度\(O(log_2n) \to O(n)\)
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
int Partition(SqList *L, int low, int high)
{
// 对子表[low...high]排序
L.r[0] = L.r[low];
KeyType pivotkey = L.r[low].key;
while (low < high)
{
while(low<high && L.r[high].key >= pivotkey) --high;
L.r[low] = L.r[high];
while(low<high && L.r[high].key <= pivotkey) ++low;
L.r[high] = L.r[low];
}
L.r[low] = L.r[0];
return low;
}

void QSort(SqList *L, int low, ing high)
{
if (low < high)
{
KeyType pivotkey = Partition(L, low, high);
Qsort(L, low, pivotkey-1);
Qsort(L, pivotkey, high);
}
}

void QuickSort(SqList *L)
{
QSort(L, 1, L.length);
}

选择排序

每一趟从待排序的记录中选择关键字最小的记录,按顺序放在已排序的记录序列的最后,直到全部排完为止

简单选择排序

  • 时间复杂度 \(O(n^2)\)
  • 空间复杂度 \(O(1)\)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void SelectSort(SqList *L)
{
for (int i=1; i<L.length; i++)
{
int k = i;
for(int j=i+1; j<=L.length; j++)
{
if (L.r[j].key < L.r[k].key) k = j;
}
if (k != i)
{
int t = L.r[i];
L.r[i] = L.r[k];
L.r[k] = L.r[t];
}
}
}

堆排序

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
// 假设r[s+1..m]已经是堆,将r[s..m]调整为以r[s]为根的大根堆
void HeapAdjust(SqList *L, int s, int m)
{
RedType rc = L.r[s];
// 沿key较大的孩子节点向下筛选
for (int j=2*s; j<=m; j++)
{
if (j<m&&L.r[j].key < L.r[j+1].key) ++j;
if (rc.key >= L.r[j].key) break;
L.r[s] = L.r[j];
s = j;
}
L.r[s] = rc;
}

void CreateHeap(SqList *L)
{
int n = L.length;
for (int i=n/2; i>0; i--)
{
HeadAdjust(L, i, n);
}
}

void HeapSort(SqList *L)
{
CreateHeap(L);
// 将堆顶记录与未经排序子序列L.r[1..i]中的最后一个记录互换
for (int i=L.length; i>1; i--)
{
RedType x = L.r[1];
L.r[1] = L.r[i];
L.r[i] = x;
}
HeapAdjust(L, 1, i-1);
}