选择排序
选择排序
基础版的选择排序实现是很简单的，算法思路如下
这里需要注意一点是，maxi可能会和begin重叠，导致交换begin和min的时候产生bug，因此只需要在前面补充一下条件即可
void SelectSort(int* a, int n)
{
int begin = 0, end = n - 1;
while (begin < end)
{
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;
}
}
Swap(&a[begin], &a[mini]);
// 如果maxi和begin重叠，修正一下即可
if (begin == maxi)
{
maxi = mini;
}
Swap(&a[end], &a[maxi]);
++begin;
--end;
}
}
堆排序
堆排序前面文章有过详细讲解，这里就不多赘述了
直接上代码实现
void Swap(int* p, int* c)
{
int tmp = *p;
*p = *c;
*c = tmp;
}
void AdjustDown(int* a, int n, int parent)
{
int child = parent * 2 + 1;
while (child < n)
{
if (child + 1 < n && a[child + 1] > a[child])
{
child++;
}
if (a[parent] < a[child])
{
Swap(&a[parent], &a[child]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void HeapSort(int* a, int n)
{
// 建堆
for (int i = (n - 2) / 2; i >= 0; i--)
{
AdjustDown(a, n, i);
}
// 堆排序
int end = n - 1;
while (end)
{
Swap(&a[0], &a[end]);
AdjustDown(a, end, 0);
end--;
}
}
交换排序
冒泡排序
入门出学的第一个排序，效率很低
void BubbleSort(int* a, int n)
{
for (int i = 0; i < n - 1; i++)
{
int flag = 0;
for (int j = 0; j < n - i - 1; j++)
{
if (a[j] > a[j + 1])
{
flag = 1;
int tmp = a[j];
a[j] = a[j + 1];
a[j + 1] = tmp;
}
}
if (flag == 0)
{
break;
}
}
}
下面重点是对快速排序进行学习，快速排序正常来说是泛用性最广的排序算法
