概述
排序分为内部排序和外部排序两种，本文讨论内部排序，即将数据存放于内存中进行排序的算法，分别为冒泡排序、插入排序、归并排序和快速排序。关于外部排序，在这进行了讨论，本文不再赘述。
冒泡排序
冒泡排序应该是所以接触算法的人所第一个了解的排序算法，之所以如此正因为其易懂。
整体思路就是两两比较，将较大的数据往后移动，所以每一次循环，最后一个必定是最大的，即已经完成排序，如下图所示。
由于冒泡排序效率太低，实际应用不广泛，在此不做太多讨论，代码如下：
1
2
3
4
5
6
7
void bubble_sort(int dat[], int n) {
for (int i = n-1; i >= 0; i--) {
for (int j = 0; j < i; j++) {
if (dat[j] > dat[j + 1]) swap(&dat[j], &dat[j + 1]);
}
}
}
插入排序
插入排序其思路与打牌时理牌的思路相同，即将每个元素与之前的元素交换，直至小于前一个元素。
由于交换次数过多，而每次调用swap函数会导致额外的时间花销，所以这里采用用tmp先记录要要排序的那个元素，然后每次交换时只将后一个元素赋值前一个元素，直到找到正确的位置，将tmp赋值给它，从而避免使用swap。代码如下：
1
2
3
4
5
6
7
8
9
10
void insert_sort(int dat[], int n) {
int tmp,j;
for (int p = 1; p < n; p++) {
tmp = dat[p];
for (j = p; j > 0 && dat[j-1] > tmp; j--) {
dat[j] = dat[j-1];
}
dat[j ] = tmp;
}
}
归并排序
归并排序思路主要为将数组分成数个小数组，然后对其排序，之后再将每两个小数组合并，从而完成对整个数组的排序。该算法是经典的利用分治思想的算法。
所以分为以下三个部分：
1
2
3
4
5
6
//入口函数，负责创建临时数组
void merge_sort(int dat[], int n);
//利用递归对小数组进行排序
void Msort(int dat[],int tmp[], int left, int right);
//将两个小数组合并
void Merge(int dat[],int tmp[], int leftStart, int rightStart, int rightEnd);
其中最为重要的就在于Merge函数，思路主要是先不断比较小数组前面的元素，直到将其中一个小数组全部拷贝至tmp中。
再将另一个数组剩下的元素拷贝至tmp中，最后把tmp复制到原数组中。
具体代码如下：
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
void merge_sort(int dat[], int n) {
int * tmp = new int[n];
Msort(dat, tmp, 0, n-1);
delete tmp;
}
void Msort(int dat[],int tmp[], int left, int right) {
int center = (left + right) / 2;
if (left < right) {
Msort(dat, tmp, left, center);
Msort(dat, tmp, center + 1, right);
Merge(dat, tmp, left, center + 1, right);
}
}
void Merge(int dat[],int tmp[], int leftStart, int rightStart, int rightEnd) {
int *Aptr = &dat[leftStart], *Bptr = &dat[rightStart],*ptr=&tmp[leftStart];
int leftEnd = rightStart - 1;
//拷贝其中一个数组
while (Aptr <= &dat[leftEnd] && Bptr <= &dat[rightEnd]) {
if (*Aptr < *Bptr) {
*ptr++ = *Aptr++;
}
else {
*ptr++ = *Bptr++;
}
}
//拷贝剩余数组内所有元素
while (Aptr <= &dat[leftEnd])
*ptr++ = *Aptr++;
while (Bptr <= &dat[rightEnd])
*ptr++ = *Bptr++;
//拷贝回原数组
for (int i = leftStart; i <= rightEnd; i++)
dat[i] = tmp[i];
}
快速排序
快速排序主要思想为先选取枢纽元，然后将比其小的放至其左侧，比其大的放至右侧，然后再分别以递归的方式对左右两侧元素处理。
图中黄色为枢纽元，绿色为比枢纽元小的部分，紫色为比其大的部分。
图中采用第一个元素为枢纽元，下面代码中采用随机元素作为枢纽元，比起前一个方法较为安全，还有一个做法是使用中值进行分割，会在之后进行讨论。具体代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void quick_sort(int dat[], int n) {
Qsort(dat, 0, n - 1);
}
void Qsort(int dat[], int left,int right) {
if (right - left < 1) return;
int pivot = rand() % (right - left) + left;
swap(&dat[left], &dat[pivot]);
int j = left + 1;
for (int i = left + 1; i <= right; i++) {
if (dat[i] < dat[left]) swap(&dat[i], &dat[j++]);
}
swap(&dat[left], &dat[--j]);
Qsort(dat,left, j-1);
Qsort(dat, j+1,right);
}
总结
在这里我们所讨论的所有算法均以比较作为基础，所以都被称为比较排序。关于非比较排序在此进行了讨论。在所有内部排序方法中，快速排序可以说是内部排序中最好的方法，当待排数据随机时所需平均时间最短。
图片和gif根据 visualgo.net 制作