选择排序

选择排序(Selection Sort)也是一种比较简单的排序算法。

基本思想

找到数组中最小的那个元素，将其与数组的第一个元素交换位置；
在剩下的元素中找到最小的元素，将其与数组中的第二个元素交换位置。
即不断地选择剩余元素中的最小值。

实现

#include <stdio.h>

#define MAXSIZE 100

typedef struct
{
    int a[MAXSIZE + 1];  //a[1]~a[MAXSIZE]存储元素
    int length;
}Sqlist;


void swap(Sqlist* L, int i, int j)
{
    int temp = L->a[i];
    L->a[i] = L->a[j];
    L->a[j] = temp;
}

/*升序排列*/
void Sele_Sort(Sqlist* L)
{
    for (int i = 1; i < L->length; i++)
    {
        //将a[i]和a[i+1...N]中最小的元素交换
        int min = i;        //最小元素的索引
        for (int j = i + 1; j <= L->length; j++)
        if (L->a[j] < L->a[min])
        {
                min = j;
        }
        swap(L,i,min);
    }
}

int main(int argc, char** argv)
{
    Sqlist L;

    scanf("%d", &(L.length));
    for (int i = 1; i <= L.length; i++)
        scanf("%d", &(L.a[i]));

    Sele_Sort(&L);

    for (int i = 1; i <= L.length; i++)
        printf("%d ", L.a[i]);
    printf("\n");

    return 0;
}

复杂度

选择排序需要N次交换以及\(\frac{N^2}{2}\)次比较，数据移动次数与数组大小呈线性关系，移动次数是最少的。
时间复杂度\(O(n^2)\)。

堆排序

将顺序表看做一棵完全二叉树，大根堆就是父结点值大于两孩子结点，所以根结点存放最大值。
构造初始堆需要从最后一个非叶结点的子树开始，向下筛选，如果根结点值小于孩子结点，将根结点值与\(max(左孩子，右孩子)\)交换：

建好堆后，输出堆顶元素即为最大值，通常将堆底元素送入堆顶，此时破坏了大根堆性质，将堆顶元素向下调整，保持大根堆：

//parent->要下沉元素下标
void Adjustdown(int* A, int len, int parent)
{
    int tmp = A[parent];  //保存要下沉的元素

    for (int child = 2 * parent + 1; child < len; child = 2 * parent + 1)
    {
        //如果右孩子存在且比左孩子大，定位到右孩子
        if (child + 1 < len && A[child] < A[child + 1])
        {
            child++;
        }

        //父结点大于孩子结点，下沉结束
        if (A[child] <= tmp)
            break;

        //将孩子调整到父结点
        A[parent] = A[child];
        parent = child;  //修改parent以便继续向下筛选
    }

    A[parent] = tmp; //将被筛选的结点放在最终位置
}

//构建二叉堆
void BuildMaxHeap(int* A, int len)
{
    //从最后一个非叶结点开始，向上调整
    for (int i = len / 2 - 1; i >= 0; i--)
    {
        Adjustdown(A, len, i);
    }
}

int* Heapsort(int* A, int len)
{
    BuildMaxHeap(A, len);
    //从小到大排序
    for (int i = len - 1; i >= 0; i--)
    {
        swap(A[0], A[i]);  //把堆顶元素与最后一个元素交换
        Adjustdown(A, i, 0);  //将剩余的元素整理成堆
    }

    return A;
}

性能：建立初始堆\(O(n)\)，每次向下调整的复杂度\(O(h)\)，共有\(n-1\)次调整，故时间复杂度\(O(nlogn)\)。
一般求前\(K\)大元素都采用堆排序，因为只需要调整\(K\)次，故\(O(Klogn)\)，而快排要将所有元素排完后才能取出前\(K\)个。

选择排序

原文：https://www.cnblogs.com/EIMadrigal/p/12129755.html