选择排序

选择排序

基础版的选择排序实现是很简单的，算法思路如下

这里需要注意一点是，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;
        }
    }
}

下面重点是对快速排序进行学习，快速排序正常来说是泛用性最广的排序算法