闲来无事 整理下几种常见的比较排序算法。
按照以往风格，Code+Log，帮助各位看官理解及博主本人备忘🤦🏻♂️。
导读
本文粗略的给出了几种比较排序的C语言的算法实现，几乎未提及任何思路或讲解，有兴趣的同学请自行拓展。
已完成：冒泡排序、冒泡排序的优化、选择排序、快速排序。
待完成：归并排序、插入排序、堆排序。[拖延症🤦🏻♂️]
图片来自百度百科
排序的稳定性是指如果在排序的序列中，存在前后相同的两个元素的话，排序前和排序后它们的相对位置不发生变化。
正文
如无特殊声明，文中示例数组均为：
int arr[] = {2, 0, 6, 1, 9, 5, 4, 7, 8, 3};
另，部分函数中使用到了变量交换宏定义
#define swap(a, b) (a^=b, b^=a, a^=b)
关于按位异或运算符^，如有之前未了解过的同学欢迎自行百度，或等我有时间再做拓展[拖延症再次🤦🏻♂️]。
1. 冒泡排序_1.0
最基础的排序，没有之一。
Code:
void bubbleSort(int *a, int count) {
for (int i = 0; i < count - 1; i++) {
for (int j = 0; j < count - 1 - i; j++) {
if (a[j] > a[j + 1]) {
swap(a[j], a[j+1]);
}
}
// printf("OneStep : i = %d ", i); //log
// printArray(a, count); //log
}
}
Log:
OriginalArray :{ 2, 0, 6, 1, 9, 5, 4, 7, 8, 3 }
OneStep : i = 0 { 0, 2, 1, 6, 5, 4, 7, 8, 3, 9 }
OneStep : i = 1 { 0, 1, 2, 5, 4, 6, 7, 3, 8, 9 }
OneStep : i = 2 { 0, 1, 2, 4, 5, 6, 3, 7, 8, 9 }
OneStep : i = 3 { 0, 1, 2, 4, 5, 3, 6, 7, 8, 9 }
OneStep : i = 4 { 0, 1, 2, 4, 3, 5, 6, 7, 8, 9 }
OneStep : i = 5 { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
// 此时目标数组已整体有序
OneStep : i = 6 { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
OneStep : i = 7 { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
OneStep : i = 8 { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
BubbleFinished: { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
2. 冒泡排序_2.0
对冒泡排序常见的改进方法是加入标志性变量flag，用于标志某一趟排序过程中是否有数据交换。
如果进行某一趟排序时并没有进行数据交换，则说明所有数据已经有序，可立即结束排序，避免不必要的比较过程。
Code:
void bubbleSortEx(int *a, int count) {
bool flag = true;
for (int i = 0; i < count - 1 && flag; i++) {
flag = false;
for (int j = 0; j < count - 1 - i; j++) {
if (a[j] > a[j + 1]) {
swap(a[j], a[j+1]);
flag = true;
}
}
// printf("OneStep : i = %d ", i); //log
// printArray(a, count); //log
}
}
Log:
OriginalArray :{ 2, 0, 6, 1, 9, 5, 4, 7, 8, 3 }
OneStep : i = 0 { 0, 2, 1, 6, 5, 4, 7, 8, 3, 9 }
OneStep : i = 1 { 0, 1, 2, 5, 4, 6, 7, 3, 8, 9 }
OneStep : i = 2 { 0, 1, 2, 4, 5, 6, 3, 7, 8, 9 }
OneStep : i = 3 { 0, 1, 2, 4, 5, 3, 6, 7, 8, 9 }
OneStep : i = 4 { 0, 1, 2, 4, 3, 5, 6, 7, 8, 9 }
OneStep : i = 5 { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
// 此时目标数组已整体有序
OneStep : i = 6 { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
BubbleExFinished:{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
3. 选择排序
基本思想：
每趟从待排序的记录中选出关键字最小的记录，顺序放在已排序的记录序列末尾，直到全部排序结束为止。
Code:
void selectionSort(int *a, int count) {
int i, j, k;
for (i = 0; i < count - 1; i++) {
k = i;
for (j = i + 1; j < count; j++) {
if (a[k] > a[j]) {
k = j;
}
}
if (i != k) {
swap(a[i], a[k]);
}
// printf("OneStep : i = %d ", i); //log
// printArray(a, count); //log
}
}
Log:
OriginalArray : { 2, 0, 6, 1, 9, 5, 4, 7, 8, 3 }
OneStep : i = 0 { 0, 2, 6, 1, 9, 5, 4, 7, 8, 3 }
OneStep : i = 1 { 0, 1, 6, 2, 9, 5, 4, 7, 8, 3 }
OneStep : i = 2 { 0, 1, 2, 6, 9, 5, 4, 7, 8, 3 }
OneStep : i = 3 { 0, 1, 2, 3, 9, 5, 4, 7, 8, 6 }
OneStep : i = 4 { 0, 1, 2, 3, 4, 5, 9, 7, 8, 6 }
OneStep : i = 5 { 0, 1, 2, 3, 4, 5, 9, 7, 8, 6 }
OneStep : i = 6 { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
// 此时目标数组已整体有序
OneStep : i = 7 { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
OneStep : i = 8 { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
SelectFinished: { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
4. 快速排序
快速排序是对冒泡排序的一种改进方式，通过分治和递归的思想实现。
基本思想：
通过一趟排序将要排序的数据分割成独立的两部分，分割点左边都是比它小的数，右边都是比它大的数。
Code:
void quickSort(int *a, int left, int right) {
if (left >= right) {
return;
}
int i = left;
int j = right;
int key = a[i];
// printf("OneStepCycle : i = %d, j = %d $", i, j); //log
// printArray(a, kCount); //log
while (i < j) {
while (i < j && key <= a[j]) {
j--;
}
a[i] = a[j];
// printf("OneStepCycP1 : i = %d, j = %d $", i, j); //log
// printArray(a, kCount); //log
while (i < j && key >= a[i]) {
i++;
}
a[j] = a[i];
// printf("OneStepCycP2 : i = %d, j = %d $", i, j); //log
// printArray(a, kCount); //log
}
a[i] = key;
// printf("QuickOneStep : i = %d, j = %d ", i, j); //log
// printArray(a, kCount); //log
quickSort(a, left, i - 1);
quickSort(a, i + 1, right);
}
精简Log:
OriginalArray : { 2, 0, 6, 1, 9, 5, 4, 7, 8, 3 }
OneStep : i = 2, j = 2 { 1, 0, 2, 6, 9, 5, 4, 7, 8, 3 }
OneStep : i = 1, j = 1 { 0, 1, 2, 6, 9, 5, 4, 7, 8, 3 }
OneStep : i = 6, j = 6 { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
// 此时目标数组已整体有序
OneStep : i = 3, j = 3 { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
OneStep : i = 4, j = 4 { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
OneStep : i = 7, j = 7 { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
OneStep : i = 8, j = 8 { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
QuickFinished : { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
分步Log:
OriginalArray : { 2, 0, 6, 1, 9, 5, 4, 7, 8, 3 }
OneStepCycle : i = 0, j = 9 ${ 2, 0, 6, 1, 9, 5, 4, 7, 8, 3 }
OneStepCycP1 : i = 0, j = 3 ${ 1, 0, 6, 1, 9, 5, 4, 7, 8, 3 }
OneStepCycP2 : i = 2, j = 3 ${ 1, 0, 6, 6, 9, 5, 4, 7, 8, 3 }
OneStepCycP1 : i = 2, j = 2 ${ 1, 0, 6, 6, 9, 5, 4, 7, 8, 3 }
OneStepCycP2 : i = 2, j = 2 ${ 1, 0, 6, 6, 9, 5, 4, 7, 8, 3 }
OneStep : i = 2, j = 2 { 1, 0, 2, 6, 9, 5, 4, 7, 8, 3 }
OneStepCycle : i = 0, j = 1 ${ 1, 0, 2, 6, 9, 5, 4, 7, 8, 3 }
OneStepCycP1 : i = 0, j = 1 ${ 0, 0, 2, 6, 9, 5, 4, 7, 8, 3 }
OneStepCycP2 : i = 1, j = 1 ${ 0, 0, 2, 6, 9, 5, 4, 7, 8, 3 }
OneStep : i = 1, j = 1 { 0, 1, 2, 6, 9, 5, 4, 7, 8, 3 }
OneStepCycle : i = 3, j = 9 ${ 0, 1, 2, 6, 9, 5, 4, 7, 8, 3 }
OneStepCycP1 : i = 3, j = 9 ${ 0, 1, 2, 3, 9, 5, 4, 7, 8, 3 }
OneStepCycP2 : i = 4, j = 9 ${ 0, 1, 2, 3, 9, 5, 4, 7, 8, 9 }
OneStepCycP1 : i = 4, j = 6 ${ 0, 1, 2, 3, 4, 5, 4, 7, 8, 9 }
OneStepCycP2 : i = 6, j = 6 ${ 0, 1, 2, 3, 4, 5, 4, 7, 8, 9 }
OneStep : i = 6, j = 6 { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
// 此时目标数组已整体有序
OneStepCycle : i = 3, j = 5 ${ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
OneStepCycP1 : i = 3, j = 3 ${ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
OneStepCycP2 : i = 3, j = 3 ${ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
OneStep : i = 3, j = 3 { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
OneStepCycle : i = 4, j = 5 ${ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
OneStepCycP1 : i = 4, j = 4 ${ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
OneStepCycP2 : i = 4, j = 4 ${ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
OneStep : i = 4, j = 4 { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
OneStepCycle : i = 7, j = 9 ${ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
OneStepCycP1 : i = 7, j = 7 ${ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
OneStepCycP2 : i = 7, j = 7 ${ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
OneStep : i = 7, j = 7 { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
OneStepCycle : i = 8, j = 9 ${ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
OneStepCycP1 : i = 8, j = 8 ${ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
OneStepCycP2 : i = 8, j = 8 ${ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
OneStep : i = 8, j = 8 { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
QuickFinished : { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
以上。
部分图片及表述引自：静默虚空-博客园
网友评论