排序算法上——冒泡排序、插入排序和选择排序
1. 排序算法？
排序算法应该算是我们最熟悉的算法了，我们学的第一个算法，可能就是排序算法，而在实际应用中，排序算法也经常会被用到，其重要作用不言而喻。
经典的排序算法有：冒泡排序、插入排序、选择排序、归并排序、快速排序、计数排序、基数排序、桶排序。按照时间复杂度，可以分为以下三类。
排序算法
2. 如何分析一个排序算法？
2.1. 排序算法的执行效率
-
最好情况、最坏情况、平均情况时间复杂度。我们不仅要知道一个排序算法的最好情况、最坏情况、平均情况时间复杂度，还要知道它们分别对应的原始数据是什么样的。有序度不同的数据，对于排序算法的执行时间肯定是有影响的。
-
时间复杂度的系数、常量、低阶。时间复杂度反映的是数据规模非常大时的一个增长趋势，但实际中，我们面临的数据可能是 10 个、100 个、 1000 个这样的小数据，因此之前我们忽略的系数、常量、低阶也要考虑进来。
-
比较次数和交换（或移动）次数。基于比较的排序算法涉及到两个主要操作，一个是元素比较大小，另一个是元素交换或移动。
2.2. 排序算法的内存消耗
- 算法的内存消耗可以用空间复杂度来衡量，针对排序算法的空间复杂度，我们引入了一个新的概念，原地排序(Sorted in place)，特指空间复杂度为
的排序算法，即指直接在原有数据结构上进行排序，无需额外的内存消耗。
2.3. 排序算法的稳定性
-
排序算法的稳定性指的是，如果待排序的序列中存在值相等的数据，经过排序之后，相等元素之间原有的先后循序不变。
-
比如一组数据 2， 9， 3， 4， 8， 3，按照大小排序之后就是 2， 3， 3， 4， 8， 9，如果排序后两个 3 的顺序没有发生改变，我们就把这种算法叫作稳定的排序算法，反之就叫作不稳定的排序算法。
-
我们学习排序的时候一般都是用整数来举例，但在真正的软件开发中，待排序的数据往往不是单纯的整数，而是一组对象，我们需要按照对象的某一个键值对数据进行排序。
-
假设我们有 10 万条订单数据，要求金额从小到大排序，并且金额相同的订单按照下单时间从早到晚排序。这时候，稳定排序就发挥了其作用，我们可以先按照下单时间对数据进行排序，然后再用稳定排序算法按照订单金额重新排序。
稳定排序算法
3. 冒泡排序（Bubble Sort）？
3.1. 冒泡排序算法实现
- 冒泡排序只会操作相邻的两个数据，将其调整到正确的顺序。一次冒泡会让至少一个数据移动到它应该在的位置，冒泡 n 次，就完成了 n 个数据的排序工作。
冒泡排序
冒泡排序
- 若某一次冒泡没有数据移动，则说明数据已经完全达到有序，不用再继续执行后续的冒泡操作，针对此我们可以再对刚才的算法进行优化。
冒泡排序
- 代码实现
// O(n^2)
void Bubble_Sort(float data[], int n)
{
int i = 0, j = 0;
int temp = 0;
int flag = 0;
for(i = n-1; i > 0; i--)
{
flag = 0;
for(j = 0; j < i; j++)
{
if(data[j+1] < data[j])
{
temp = data[j];
data[j] = data[j+1];
data[j+1] = temp;
flag = 1;
}
}
if(!flag)//If no data needs to be exchanged, the sort finishes.
{
break;
}
}
}
3.2. 冒泡排序算法分析
-
冒泡排序是一个原地排序算法，只需要常量级的临时空间。
-
冒泡排序是一个稳定的排序算法，当元素大小相等时，我们没有进行交换。
-
最好情况下，数据已经是有序的，我们只需要进行一次冒泡即可，时间复杂度为
。最坏情况下，数据刚好是倒序的，我们需要进行 n 次冒泡，时间复杂度为
。
3.3. 有序度和逆序度
- 有序度是数组中具有有序关系的元素对的个数。有序元素对定义：a[i] <= a[j], 如果 i < j。
有序度
-
完全倒序排列的数组，其有序度为 0；完全有序的数组，其有序度为
，我们把这种完全有序的数组叫作满有序度。
-
逆序度和有序度正好相反，逆序元素对定义：a[i] > a[j], 如果 i < j。
-
逆序度 = 满有序度 - 有序度。排序的过程就是一个增加有序度减少逆序度的过程，最后达到满有序度，排序就完成了。
-
在冒泡排序中，每进行一次交换，有序度就加 1。不管算法怎么改进，交换次数总是确定的，即为逆序度。
-
最好情况下，需要的交换次数为 0；最坏情况下，需要的交换次数为
。平均情况下，需要的交换次数为
，而比较次数肯定要比交换次数多，而复杂度的上限是
4. 插入排序（Insertion Sort）
4.1. 插入排序算法实现
-
往一个有序的数组插入一个新的元素时，我们只需要找到新元素正确的位置，就可以保证插入后的数组依然是有序的。
插入元素
-
插入排序就是从第一个元素开始，把当前数据的左侧看作是有序的，然后将当前元素插入到正确的位置，依次往后进行，直到最后一个元素。
-
对于不同的查找插入点方法（从头到尾、从尾到头），元素的比较次数是有区别的，但移动次数是确定的就等于逆序度。
-
代码实现
// O(n^2)
void Insertion_Sort(float data[], int n)
{
int i = 0, j = 0;
int temp = 0;
for(i = 1; i < n; i++)
{
temp = data[i];
for(j = i; j > 0; j--)
{
if(temp < data[j-1])
{
data[j] = data[j-1];
}
else// The data ahead has been sorted correctly.
{
break;
}
}
data[j] = temp; // insert the data
}
}
4.2. 插入排序算法分析
-
插入排序是一个原地排序算法，只需要常量级的临时空间。
-
插入排序是一个稳定的排序算法，当元素大小相等时，我们不进行插入。
-
最好情况下，数据已经是有序的，从尾到头进行比较的话，每次我们只需要进行一次比较即可，时间复杂度为
-
在数组中插入一个元素的平均时间复杂度为
5. 选择排序（Selection Sort）
5.1. 选择排序算法实现
-
选择排序就是从第一个元素开始，从当前数据的右侧未排序区间中选取一个最小的元素，然后放到左侧已排序区间末尾，依次往后进行，直到最后一个元素。
选择排序
-
代码实现
// O(n^2)
void Selection_Sort(float data[], int n)
{
int i = 0, j = 0, k = 0;
int temp = 0;
for(i = 0; i < n-1; i++)
{
k = i;
for(j = i+1; j < n; j++)
{
if(data[j] < data[k])
{
k = j;
}
}
if(k != i)
{
temp = data[i];
data[i] = data[k];
data[k] = temp;
}
}
}
5.2. 选择排序算法分析
-
选择排序是一个原地排序算法，只需要常量级的临时空间。
-
选择排序的最好情况时间复杂度、最坏情况时间复杂度和平均情况时间复杂度都为
-
选择排序是一个不稳定的排序算法，因为每次都要从右侧未排序区间选择一个最小值与前面元素交换，这种交换会打破相等元素的原始位置。
6. 为什么插入排序比冒泡排序更受欢迎？
交换排序和插入排序的时间复杂度都为
- 前面分析，插入排序的移动次数等于逆序度，冒泡排序的交换次数等于逆序度，但冒泡排序每次交换需要进行三次赋值操作，而插入排序每次移动只需要一次赋值操作，其相应的真实运行时间也会更短。
冒泡排序中数据的交换操作：
if (a[j] > a[j+1]) { // 交换
int tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
flag = true;
}
插入排序中数据的移动操作：
if (a[j] > value) {
a[j+1] = a[j]; // 数据移动
} else {
break;
}
7. 小结
三种排序算法对比
- 冒泡排序和选择排序在实际中应用很少，仅仅停留在理论层次即可，选择排序算法还是挺有用的，而且其还有很大的优化空间，比如希尔排序。
获取更多精彩，请关注「seniusen」!
seniusen
