C语言排序算法之选择排序(直接选择排序,堆排序)

　　#define _CRT_SECURE_NO_WARNINGS

　　#include

　　//打印数据

　　void Printf(int* a, int n)

　　{

　　for (int i = 0; i < n; ++i)

　　{

　　printf("%d ", a[i]);

　　}

　　}

　　//交换,传地址

　　void Swap(int* child, int* parent)

　　{

　　int tmp = *child;

　　*child = *parent;

　　*parent = tmp;

　　}

　　//向下调整算法

　　//从根节点开始，如果是建立小堆选出左右孩子中小的那一个，跟父亲比较，如果比父亲小就交换

　　void AdjustDwon(int* a, int n, int root)//建小堆

　　{

　　int parent = root;//父亲节点

　　int child = parent * 2 + 1;//默认是左孩子

　　while (child < n)//叶子节点下标不会超过数组总下标数n

　　{

　　//选出左右孩子中最小的那一个

　　if (child+1 < n&& a[child + 1] < a[child])

　　{

　　child += 1;//用a[child]与父亲节点a[parent]比较

　　}

　　if (a[child] < a[parent])

　　{

　　//交换,传地址

　　Swap(&a[child], &a[parent]);

　　//交换后，将child,作为根节点继续向下调整，持续建堆

　　parent = child;

　　//新的左孩子

　　child = parent * 2 + 1;

　　}

　　else

　　{

　　break;//如果不用交换，直接结束循环

　　}

　　}

　　}

　　//堆的建立

　　//大堆要求：树中所有的父亲都>=孩子,根是最大的

　　//小堆要求：书中所有的父亲都<=孩子,根是最小的

　　//建大堆排升序，建小堆排降序

　　//建堆的时间复杂度是O(N);

　　void HeapSort(int *a,int n)

　　{

　　//找父亲节点

　　for (int i=(n-1-1)/2;i>=0;--i)

　　{

　　//向下调整算法

　　AdjustDwon(a,n,i);

　　}

　　//大堆或小堆建立完毕，排序

　　//用主根节点与最后一个节点交换位置

　　int end = n - 1;

　　while (end>0)

　　{

　　//交换，传地址

　　Swap(&a[0],&a[end]);

　　//继续向下调整

　　AdjustDwon(a,end,0);

　　--end;

　　}

　　}

　　//选择排序—堆排序

　　int main()

　　{

　　int a[10] = {9,2,5,4,3,1,6,7,8,0};

　　//堆的建立

　　HeapSort(a,sizeof(a) / sizeof(a[0]));

　　//打印数据

　　Printf(a,sizeof(a) / sizeof(a[0]));

　　return 0;

　　}