|
目录
1. 冒泡排序
1.1. 算法讲解
1.2. 代码实现
2. 选择排序
2.1. 算法讲解
2.2. 代码实现
3 插入排序
2.1. 算法讲解
2.2. 代码实现
4 希尔排序
2.1. 算法讲解
2.2. 代码实现
5 归并排序
2.1. 算法讲解
2.2. 代码实现
6 快速排序
6.1. 算法讲解
6.2. 代码实现
7 堆排序
2.1. 算法讲解
2.2. 代码实现
8 计数排序
2.1. 算法讲解
2.2. 代码实现
9 桶排序
2.1. 算法讲解
2.2. 代码实现
10 基数排序
2.1. 算法讲解
2.2. 代码实现
附录
1. 10大经典排序算法性能分析
2. C/C++的内置排序函数
2.1. c++的`sort`函数
2.1.1. 函数简述
2.1.2. `cmp`叙述
2.1.3. 代码实现
2.2 c语言的`qsort`函数
2.1.1. 函数简述
2.1.2. `cmp`叙述
2.1.3. 代码实现
1. 冒泡排序
冒泡排序，顾名思义，就是出头的被排序。其算法复杂度为O( n 2 n^{2} n2)，空间复杂度为O( 1 1 1)。
1.1. 算法讲解
将第j个元素和后面的元素依次对比，如果大于序列为j+1的元素，就进行交换。
作为对比的基础元素j取值范围为"0 => size - 2"。因为j + 1不可超过size - 1。因而，需要进行对比的j有size - 1个，这个组别用字母i表示。
当排序到第i组元素时候，需要做对比的就只需size - i - 1个。以第一次对比为例子，从第一个到最后一个元素都和相邻的两两对比交换，因此这组所有数中最大的已经交换到了最后一位。所以下一次，就不需要考虑它了。第二次，这一组最大的交换到了倒数第二位…。因此需要做对比的就只需size - i - 1个。
1.2. 代码实现
void BubbleSort(int a[], int size)
{
for (int i = 0; i
int temp = 0;
if (a[j] > a[j + 1])
{
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
}
2. 选择排序
选择排序也是非常直观的，唯一的好处可能就是不占用额外的内存空间。算法复杂度为O( n 2 n^{2} n2)，空间复杂度为O( 1 1 1)。
2.1. 算法讲解
选择排序认为前i个元素是排序好的，因此将后面的元素排序即可。i的取值范围为0 => size - 1。
对排序第i个元素的那一组，将i的下标暂存(MIN)，并认为这个元素是最小的(a[MIN])。如果后面的元素有比次元素小得，将**a[MIN]**更新为更小的元素，并将所记录的最小元素下标(MIN)也更新。
在这一组遍历结束，如果MIN不是初始值0了，意味着这一组的第一个元素不是最小的，那么将这个最小的元素和第一个元素做交换，以保证从开头到这个元素的这一段是已经排序好的。
将第2步，第3步重复进行直至所有。
2.2. 代码实现
void SelectSort(int a[], int size)
{
int MIN = 0;
for (int i = 0; i
if (a[j]
int temp = 0;
temp = a[i];
a[i] = a[MIN];
a[MIN] = temp;
}
}
}
3 插入排序
插入排序就好像打扑克牌整理牌组一样，从后面看起，如果此牌小于前面整理好的牌，就插入前面，因而前面整理好的牌，在被插入的后面的，依次后移一位。 可以说插入排序是远离最直观的，算法复杂度为O( n 2 n^{2} n2) ，空间复杂度为O( 1 1 1)。
2.1. 算法讲解
排序分为若干组进行，其中的一组为从第i个元素开始，直到最后一个元素为止。
由于每进行一次排序，前面的都已经排序完成，因此只需对比这第i个元素是不是比前面i-1个元素小就行。
若第i个元素小于前面i-1个元素中的第j个元素，就首先将这第i个元素记录下来，然后把从第j个元素到第i-1个元素依次后移，最后再把记录下来的元素，插入第j个位置。
将此步骤进行循环即可。
2.2. 代码实现
void InsertSort(int a[], int size)
{
int i, j, temp;
for (i = 1; i |