目录
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 |