整体思想:
从数组中选出最小值和最大值放在起始位置,直到排序完成
具体步骤:
图示:
代码:
void SelectSort(int* a, int n)
{
//数组的范围
int begin = 0, end = n - 1;
while (begin < end)//控制范围
{
// maxi和mini是下标,从begin开始,因为begin会变化
int maxi = begin, mini = begin;
//找最大元素的下标和最小元素的下标
for (int i = begin; i <= end; i++)//注意找的范围
{
if (a[i] > a[maxi])
{
maxi = i;
}
if (a[i] < a[mini])
{
mini = i;
}
}
//最小值与begin的位置交换
Swap(&a[begin], &a[mini]);
//特殊情况,如果maxi与begin重叠,此时最大值的下标在mini
if (begin == maxi)
{
maxi = mini;
}
//最大值与end的位置交换
Swap(&a[end], &a[maxi]);
//缩小范围
++begin;
--end;
}
}
特性总结:
计数排序采用相对映射的思想,开辟一块空间,该空间的范围为待排序的数组的最大值和最小值之差加1,并且每个元素初始化为0,然后待排序的数组只要是出现的元素就在临时空间对应的位置计数,最后从小到大恢复原来的元素重新放入数组,完成排序。
思路:
图示:
代码:
void CountSort(int* a, int n)
{
//找最大值和最小值
int max = a[0], min = a[0];
for (int i = 0; i < n; i++)
{
if (a[i] > max)
{
max = a[i];
}
if (a[i] < min)
{
min = a[i];
}
}
//最大值与最小值的差
int range = max - min + 1;
//开空间,每个元素为0,后面要计数
int* count = (int*)calloc(range, sizeof(int));
if (count == nullptr)
{
perror("calloc fail");
exit(-1);
}
//给出现的元素计数
for (int i = 0; i < n; i++)
{
count[a[i] - min]++;
}
//从小到大重新放入数组,完成排序
int j = 0;
for (int i = 0; i < range; i++)
{
while (count[i]--)//该位置有元素
{
a[j++] = i + min;//恢复原来的元素,依次放入数组
}
}
free(count);
}
特性总结: