这里总结如下算法:
这次的算法实现全都使用 C 语言,并不是说 C 有多好,只是因为 C 比较接近底层,掌握 C 的写法后,其他语言的写法也很好实现,其次,也是因为现在很多算法的讲解也使用 C。
然后,本文的算法实现可能还不够完美,虽然都经过了测试用例,但难免还有些疏忽,如有错误或是有更好的意见,欢迎提出。
从左到右,依次将较大的元素交换到后面,那么一次一次排序后,最大的元素就在数组末尾,然后不断重复。
给定一个 N 个元素的数组,冒泡法排序将:
(引用 VisuAlgo)
可视化见 VisuAlgo
#define BOOL size_t
#define FALSE 0
#define TRUE 1
// 原地排序
void bubbleSort(int *arr, int len)
{
BOOL exchanged = FALSE;
int last = len; //last 随着冒泡次数而减小
do
{
for (int i = 0; i < last; i++)
{
if (arr[i] > arr[i + 1])
{
// 交换前后项
//int 整数型可以使用这种算法,不使用中间变量
arr[i] ^= arr[i + 1];
arr[i + 1] ^= arr[i];
arr[i] ^= arr[i + 1];
// 交换过了
exchanged = TRUE;
}
}
last--;// 当 last 减到 0 时,说明已经遍历结束,结束排序
} while (exchanged && last > 0); // 如果一次冒泡后没有发生交换,说明数组已经有序,结束排序
}
从左到右,选择未被排序的数里最小的那个,与数组第一个数交换,然后第二个… 不断重复。
给定 N 个项目和 L = 0 的数组,选择排序将:
(引用 VisuAlgo)
可视化见 VisuAlgo
// 原地排序
void selectSort(int *arr, int len)
{
for (int i = 0; i < len; i++)
{
// 找出未被排序的数里最小的那个
int min = arr[i];
int minIdx = i;
for (int j = i; j < len; j++)
{
if (min > arr[j])
{
min = arr[j];
minIdx = j;
}
}
// 交换
arr[minIdx] = arr[i];
arr[i] = min;
}
}
将未排序的数依次插入到排序好的数中
插入排序类似于大多数人安排扑克牌的方式。
(引自 VisuAlgo)
可视化见 VisuAlgo
// 原地排序
void insertSort(int *arr, int len)
{
for (int i = 1; i < len; i++) // 这里默认第一个数就是排好序的,所以索引从第二个数开始
{
// 将未排序的数插入到排序好的数中
for (int j = 0; j < i; j++)
{
if (arr[i] < arr[j]) // 插入
{
// 先缓存要插入的数,因为后面要移动前面的数列,会覆盖它
int n = arr[i];
// 移动数列
for (int k = i; k > j; k--)
arr[k] = arr[k - 1];
// 放入正确的位置
arr[j] = n;
}
}
}
}
这几个排序算法比较简单,容易想到,也比较容易理解算法原理。
在数据量变大时,运行效率会非常低,不是很实用。
将待排序的数组一分为二,分别对左右数组排序,排序时再一分为二,直到分成单个元素,排序完成后再依次合并。
给定一个 N 个项目的数组,归并排序将:
(引自 VisuAlgo)
可视化见 VisuAlgo
注:需要 O (n) 的额外空间
// 借助临时数组进行排序
void merge(int *arr, int low, int mid, int high) // 归并排序子函数
{
int N = high - low + 1; // 要排序的数字个数
int *b = (int *)malloc(N * sizeof(int)); // 创建一个新的数组用来排序
int lIdx = low, rIdx = mid + 1, bIdx = 0; //lIdx-> 左边数组索引,rIdx-> 右边数组索引,bIdx-> 数组 b 的索引
// 因为在 low~mid 和 mid+1~high 之间的数都是有序的(从小到大的),所以可以这样
while (lIdx <= mid && rIdx <= high)
{
if (arr[lIdx] < arr[rIdx])
{
b[bIdx] = arr[lIdx];
lIdx++;
}
else
{
b[bIdx] = arr[rIdx];
rIdx++;
}
bIdx++;
}
// 可能左数组或右数组还有剩余项
// 比如:左数组所有数都小于右数组数的情况下
while (lIdx <= mid)
b[bIdx++] = arr[lIdx++];
while (rIdx <= high)
b[bIdx++] = arr[rIdx++];
// 现在数组 b 中是已经排好序的数,再给它们复制回 arr 中
for (int i = 0, j = low; i < N; i++, j++)
{
arr[j] = b[i];
}
free(b);
}
void mergeSort(int *arr, int low, int high) // 归并排序
{
if (low < high)
{
// 将待排序的数组一分为二,递归
int mid = (low + high) / 2;
mergeSort(arr, low, mid);
mergeSort(arr, mid + 1, high); // 注:这里的 mid+1 只要和 merge 子函数里 rIdx 的值保持相同就行
// 归并
merge(arr, low, mid, high); //mid 从这里传入,在 merge 子函数中 rIdx=mid+1
}
}
在此基础上还可以加以改进,使得归并排序在原地排序(不借用中间数组),降低空间复杂度,但是似乎会提升时间复杂度O(N log^2 N)-wikipedia。
划分步骤:
可视化见 VisuAlgo
// 原地排序
int partition(int *arr, int low, int high) // 快速排序子函数 - 划分
{
int p = arr[low]; // 选取第一个数作为枢轴点
int m = low; // 分界点,因为左右区域一开始都是空的,所以 m 要在 0 的位置
for (int i = low + 1; i <= high; i++)
{
// 如果 arr [i]>=p,什么都不用做,继续下一次循环即可 (i++)
if (arr[i] < p)
{
// 这里的算法详见 https://visualgo.net/zh/sorting?slide=12-6
m++;
// 交换 arr [m] 和 arr [i]
int tmp = arr[m];
arr[m] = arr[i];
arr[i] = tmp;
// 进入下一次循环 i++
}
}
// 交换枢轴点和分界点
arr[low] = arr[m];
arr[m] = p;
// 返回枢轴点所在位置
return m;
}
void quickSort(int *arr, int low, int high)// 快速排序
{
if (low < high) // 如果 low>high,说明已经划分为单个
{
// 先划分为左右两个区域
int m = partition(arr, low, high);
// 再递归对左右两个区域排序
// 注:m 所在位置已经在正确的位置了,所以不需要包括进去
quickSort(arr, low, m - 1);
quickSort(arr, m + 1, high);
}
}
上面是经典快速排序,使用随机快速排序只需要让 p 随机选取即可。
int partition(int *arr, int low, int high) // 快速排序子函数 - 划分
{
int pIdx = (rand() % (high - low + 1)) + low; // 随机选取 [low,high]
// 交换 arr [pIdx] 和 arr [low]
int p = arr[pIdx];
arr[pIdx] = arr[low];
arr[low] = p;
int m = low; // 分界点,因为左右区域一开始都是空的,所以 m 要在 0 的位置
for (int i = low + 1; i <= high; i++)
{
// 如果 arr [i]>=p,什么都不用做,继续下一次循环即可 (i++)
if (arr[i] < p)
{
// 这里的算法详见 https://visualgo.net/zh/sorting?slide=12-6
m++;
// 交换 arr [m] 和 arr [i]
int tmp = arr[m];
arr[m] = arr[i];
arr[i] = tmp;
// 进入下一次循环 i++
}
}
// 交换枢轴点和分界点
arr[low] = arr[m];
arr[m] = p;
// 返回枢轴点所在位置
return m;
}
void quickSort(int *arr, int low, int high) // 随机快速排序
{
srand((unsigned)time(NULL));
if (low < high) // 如果 low>high,说明已经划分为单个
{
// 先划分为左右两个区域
int m = partition(arr, low, high);
// 再递归对左右两个区域排序
// 注:m 所在位置已经在正确的位置了,所以不需要包括进去
quickSort(arr, low, m - 1);
quickSort(arr, m + 1, high);
}
}
在基于比较的排序算法中已经是最快的了(当然还可以针对不同的数据继续优化),比较实用,在数据量大的情况下表现也不错,可能是现在使用最多的排序算法。
归并排序需要额外的空间,快速排序不是稳定的排序(即它会交换同样大小的数字的顺序)。
针对小范围的自然数,统计每个数字出现的次数,然后按照从小到大依次输出。
如果要排序的项目是小范围的整数,我们可以计算每个整数(在这个小范围内)的出现频率,然后通过循环该小范围来按排序顺序输出项目。 (引自 VisuAlgo)
注:需要 O (n+k) 的额外空间
// 借助临时数组排序
void countSort(int *arr, int len, int maxNum) // 计数排序
{
int *con = (int *)calloc(maxNum + 1, sizeof(int));
for (int i = 0; i < len; i++)
{
con[arr[i]]++; // 统计每个数字出现次数
}
for (int i = 0, idx = 0; i <= maxNum; i++)
{
while (con[i]-- > 0)
{
arr[idx++] = i; // 复制回去
}
}
free(con);
}
针对范围大但数位小的自然数,创建 10 个桶 (0-9),按照指定数位,依次放入对应桶中,再放入顺序取出,对每个数位从低到高重复操作。
如果要排序的项目是大范围但小数位的整数,我们可以将计数排序(Counting Sort)思想与基数排序(Radix Sort)结合起来,以实现线性时间复杂度。 在基数排序中,我们将每个项目排序为一个 w 数字串(如果需要,我们填充小于 w 数字的前几个零的整数)。 对于最低有效位(最右边)到最高有效位(最左边),我们通过 N 个项目并将它们按照活动数字放到 10 个队列中(每个数字 [0…9] 一个),就好像 一个修改的计数排序,因为这保留了稳定性。 然后我们再次重新连接组,以便进行后续迭代。 (引自 VisuAlgo)
注:需要 O (N+k) 的额外空间
void radixSort(int *arr, int len) // 基数排序
{
int N = len / 10; // 桶初始化可以装下的元素数 & 后续每次增加量
int count[10] = {0}; // 每个桶当前装载的元素数量
int maxCount[10] = {len}; // 每个桶当前能装下的最大元素数量,0 桶设置为 len,原因见下面
// 初始化桶
int **con = (int **)malloc(10 * sizeof(int *));
// 最后遍历完所有数位后,所有的数都会过一遍 0 桶,所以一开始就设置为 len 的长度
con[0] = (int *)malloc(len * sizeof(int));
for (int i = 1; i < 10; i++)
{
con[i] = (int *)malloc(N * sizeof(int));
maxCount[i] = N;
}
// 遍历每个数位
BOOL ended = FALSE;
for (int Bit = 10; Bit <= INT_MAX && !ended; Bit *= 10)
{
ended = TRUE;
for (int i = 0; i < len; i++)
{
// 提取当前数位,并将该数放入桶中
int radix = arr[i] % Bit / (Bit / 10); // 当前数位
if (count[radix] >= maxCount[radix])
{
// 桶满了,重新分配内存空间
maxCount[radix] *= 2;
con[radix] = (int *)realloc(con[radix], maxCount[radix] * sizeof(int *));
if (con[radix] == NULL)
{
// 内存分配失败
exit(0);
}
}
con[radix][count[radix]] = arr[i];
count[radix]++;
}
for (int i = 1; i < 10; i++)
{
// 判断是否已经遍历结束
if (count[i] > 0)
{
ended = FALSE;
break;
}
}
for (int i = 0, aIdx = 0; i < 10; i++)
{
// 把桶中的元素按照放入顺序放回数组
for (int cIdx = 0; cIdx < count[i]; cIdx++)
{
arr[aIdx++] = con[i][cIdx];
}
count[i] = 0;
}
}
for (int i = 0; i < 10; i++)
{
free(con[i]);
}
free(con);
}
基于比较的算法有 O (N log N) 的时间复杂度下限,而这些不基于比较的排序可以突破这个下限,使时间复杂度降到线性,针对于特定的数据是最优解。
对数据类型的要求比较苛刻,只在一些特定的数据集时有效。
参考文章: VisuAlgo - 排序 Wikipedia - 排序算法