选择排序和计数排序
选择排序
定义
选择排序是一种简单直观的算法>排序算法。它的基本思想是在每一趟遍历中找到未排序部分中的最小元素，并将其放到正确的位置上。
操作步骤
初始化：设数组长度为 n。
外层循环：控制需要选择的位置 i，从 0 到 n-2。
在每一轮 i 中，假设前 i 个元素已经排好序，剩下的部分是从 i 到 n-1 的子数组。
内层循环：在当前未排序的部分中找到最小（大）值的位置 min_index(max_index)。
初始化 min_index(max_index) 为 i。
遍历从 i+1 到 n-1 的每个元素 j。
如果 arr[j] < arr[min_index]，则更新 min_index = j。
交换：将找到的最小（大）值与第 i 个位置的元素进行交换。
通过重复上述步骤，每一趟外层循环都会将一个最小（大）的未排序元素放到其正确的位置上，直到整个数组排序完成。
排序过程
遍历序列，找到数组中最大值（9），并将其与首元素（3）交换。
从第 2 个元素开始，遍历序列，找到剩下序列中的最大值（8），将其与第 2 个元素（8）交换。注意：此时最大元素本身就在第 2 个元素位置，所以无需交换。
从第 3 个元素开始，遍历序列，找到剩下序列中的最大值（7），将其与第 3 个元素（5）交换。
从第 4 个元素开始，遍历序列，找到剩下序列中的最大值（7），将其与第 4 个元素（5）交换。
从第 5 个元素开始，遍历序列，找到剩下序列中的最大值（6），将其与第 5 个元素（2）交换。
从第 6 个元素开始，遍历序列，找到剩下序列中的最大值（5），将其与第 6 个元素（2）交换。
从第 7 个元素开始，遍历序列，找到剩下序列中的最大值（3），将其与第 7 个元素（3）交换。
前面的数字全部顺序已排列好，最后 1 个元素肯定已正确排序。
代码实现
/**
* @ 选择排序
* @ arr - 待排序的数组 num - 数组元素个数
* @ 要求从大到小排序数据
* */
void selection_sort(int *arr, int num)
{
int i, j, tmp;
int max_index; /* 记录最大值位置 */
for (i=0; i<num-1; i++) {
max_index = i;
/* 1. 查找最大值位置 */
for (j=i+1; j<num; j++) {
if (arr[j] > arr[max_index])
max_index = j;
}
/* 若需要交换，则将最大值移动到前面 */
if (max_index != i) {
tmp = arr[max_index];
arr[max_index] = arr[i];
arr[i] = tmp;
}
}
}
技术点
若前面所有数据排序完成，最末位元素也一定是有序的，所以外层循环可以只有循环 0 至 n-2。
内层循环开始时，先将目标值幅值给当前遍历的首元素，所以内层循环只需从当前循环第 2 个元素开始遍历即可。
增加位置判定，若当前处理位置上元素已经是正确的最小（大）值，则不需要执行交换操作。
运行结果
总结
选择排序通过每趟找到一个最小元素并放到正确位置的方式完成排序。虽然其实现简单，但时间复杂度较高，适用于数据规模较小的场景。对于大规模数据，建议采用更高效的算法>排序算法如快速排序、归并排序等。
计数排序
定义
计数排序是一种基于线性复杂度的非比较型算法>排序算法。它通过统计每个元素出现的次数，并根据这些统计信息来构建有序数组。
操作步骤
确定范围：找出数组中的最小值和最大值，以确定需要创建的计数数组（桶）的大小。
初始化计数数组：创建一个长度为（最大值 - 最小值 + 1）的数组，用于记录每个元素的出现次数。
统计次数：遍历原数组，对于每个元素每出现一次，将其在计数数组中的对应位置 +1。
构建有序数组：根据计数数组中记录的信息，将每个元素按顺序放入结果数组中的正确位置。
排序过程
遍历 arr 序列，找到数组中最大值（9）和最小值（2），得到数据范围 range = 9 -2 + 1 = 8。
申请计数数组 cnt[range] 空间，初始化所有元素为0，用于统计 arr 数组中各元素个数。
从左往右开始遍历 arr 序列，point 指向首元素（3），这时将计数数组中对应 3 的位置计数值 +1。
继续向后遍历 arr 数组，并统计各元素出现次数，直到 arr 数组整个遍历完成。
从右向左遍历 cnt 数组，将数据依据计数次数依次输出到 arr 数组中。
释放 cnt 数组空间。
代码实现
/**
* @ 计数排序
* @ arr - 待排序的数组 num - 数组元素个数
* @ start_pos - 待处理元素起始位置 gap - 间隔
* @ 要求从大到小排序数据
* */
void count_sort(int *arr, int num)
{
int max, min; /* 用于记录数组中的最大值和最小值 */
int *cnt = NULL, i, idx, cnt_num, offset;
/* 1. 遍历数组，找到数组中最小值和最大值 */
max = arr[0];
min = arr[0];
for (i=1; i<num; i++) {
if (arr[i] > max)
max = arr[i];
if (arr[i] < min)
min = arr[i];
}
/* 2. 获得数组中包含数据不同元素个数 */
cnt_num = max - min + 1;
/* 3. 依据不同元素个数申请空间，用于统计各元素数量，初始化各元素数量为0 */
cnt = (int *)malloc(cnt_num * sizeof(int));
if (cnt == NULL) {
printf("malloc error...\n");
return;
}
memset(cnt, 0, cnt_num * sizeof(int));
/* 4. 遍历arr数组，统计所有元素出现次数，并记录到cnt数组中 */
for (i=0; i<num; i++)
cnt[arr[i] - min]++;
/* 5. 遍历cnt数组，依据数据出现频率，将数据输出到arr数组中 */
idx = 0;
for (i=cnt_num; i>0; i--) {
while (cnt[i-1] > 0) {
arr[idx++] = i - 1 + min;
cnt[i-1]--;
}
}
/* 6. 销毁cnt数组，释放空间 */
free(cnt);
cnt = NULL;
}
技术点
以上程序同样也适用序列中包含负数的情况。
通过动态内存分配和释放，避免了不必要的空间浪费。
运行结果
总结
计数排序是一种简单而高效的算法>排序算法，尤其适用于数值范围较小且稳定的场景。与比较型算法>排序算法（如快速排序、归并排序）相比，它在特定情况下表现出色。然而，当面对大范围的数值或内存受限的环境时，计数排序可能并不是最佳选择。
完整代码
/**
* @Filename : selection_count_sort.c
* @Revision : $Revision: 1.00 $
* @Author : Feng(更多编程相关的知识和源码见微信公众号：不只会拍照的程序猿，欢迎订阅)
* @Description : 选择排序和计数排序
**/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX_NUM 8
/**
* @ 打印数组
* @ arr - 待打印的数组 num - 数组元素个数
* */
void print_arr(int *arr, int num)
{
int i;
for (i=0; i<num; i++)
printf("%02d ", arr[i]);
printf("\n");
}
/**
* @ 选择排序
* @ arr - 待排序的数组 num - 数组元素个数
* @ 要求从大到小排序数据
* */
void selection_sort(int *arr, int num)
{
int i, j, tmp;
int max_index; /* 记录最大值位置 */
for (i=0; i<num-1; i++) {
max_index = i;
/* 1. 查找最大值位置 */
for (j=i+1; j<num; j++) {
if (arr[j] > arr[max_index])
max_index = j;
}
/* 2. 若需要交换，则将最大值移动到前面 */
if (max_index != i) {
tmp = arr[max_index];
arr[max_index] = arr[i];
arr[i] = tmp;
}
printf("第%d次排序: ", i+1);
print_arr(arr, num);
}
}
/**
* @ 计数排序
* @ arr - 待排序的数组 num - 数组元素个数
* @ start_pos - 待处理元素起始位置 gap - 间隔
* @ 要求从大到小排序数据
* */
void count_sort(int *arr, int num)
{
int max, min; /* 用于记录数组中的最大值和最小值 */
int *cnt = NULL, i, idx, cnt_num, offset;
/* 1. 遍历数组，找到数组中最小值和最大值 */
max = arr[0];
min = arr[0];
for (i=1; i<num; i++) {
if (arr[i] > max)
max = arr[i];
if (arr[i] < min)
min = arr[i];
}
printf ("数组中最大值和最小值分别为: %d %d\n", max, min);
/* 2. 获得数组中包含数据不同元素个数 */
cnt_num = max - min + 1;
/* 3. 依据不同元素个数申请空间，用于统计各元素数量，初始化各元素数量为0 */
cnt = (int *)malloc(cnt_num * sizeof(int));
if (cnt == NULL) {
printf("malloc error...\n");
return;
}
memset(cnt, 0, cnt_num * sizeof(int));
/* 4. 遍历arr数组，统计所有元素出现次数，并记录到cnt数组中 */
for (i=0; i<num; i++)
cnt[arr[i] - min]++;
printf("统计数组内容: ");
print_arr(cnt, cnt_num);
/* 5. 遍历cnt数组，依据数据出现频率，将数据输出到arr数组中 */
idx = 0;
for (i=cnt_num; i>0; i--) {
while (cnt[i-1] > 0) {
arr[idx++] = i - 1 + min;
cnt[i-1]--;
}
}
/* 6. 销毁cnt数组，释放空间 */
free(cnt);
cnt = NULL;
}
/**
* @ 排序执行函数
* @ opr - 算法函数 arr - 待排序数组 num - 数组元素个数
* */
void sort_handle(void (*opr)(int *, int), int *arr, int num)
{
printf("排序前数组内容: ");
print_arr(arr, num);
opr(arr, num);
printf("排序后数组内容: ");
print_arr(arr, num);
}
int buf1[] = {3, 8, 5, 7, 2, 6, 9, 7};
int buf2[] = {3, 8, 5, 7, 2, 6, 9, 7};
int main(void)
{
printf ("----------选择排序---------\n");
sort_handle(selection_sort, buf1, MAX_NUM);
printf ("----------计数排序---------\n");
sort_handle(count_sort, buf2, MAX_NUM);
return0;
}
运行结果
