常见排序算法之选择排序——直接选择排序、堆排序

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
//交换
void Swap(int* mini, int* maxi)
{
  int tmp = *mini;
  *mini = *maxi;
  *maxi = tmp;
}
//打印
void Print(int* a, int n)
{
  for (int i = 0; i < n; i++)
  {
    printf("%d ", a[i]);
  }
}
//直接选择排序
void SelectSort(int *a,int n)
{
  //下标
  int begin = 0;
  int end = n - 1;
  while (begin < end)
  {
    int mini = begin, maxi = end;
    //选出最大的给maxi，选出最小的给mini
    for (int i=begin;i<=end;++i)
    {
      if (a[i]>a[mini])//升序
      {
        mini = i;   //改两个if的符号即可实现升序、降序转换。
      }
      if (a[i] <a[maxi])
      {
        maxi = i;
      }
    }
    //交换
    Swap(&a[begin],&a[mini]);
        //因为还有一种特殊情况，就是begin跟maxi重叠，然后执行第一次交换之后，maxi记录的是最小值
        if (begin == maxi)
    {
      maxi = mini;
    }
    Swap(&a[end], &a[maxi]);
    ++begin;
    --end;
  }
}
////直接选择排序
//void SelectSort(int* a, int n)//(升序)
//{
//  for (int j=0;j<n-1;j++)//整体遍历
//  {
//    for (int i=j+1;i<n;i++)//遍历比较
//    {
//      if (a[j] > a[i])//比较交换
//      {
//        int tmp = a[j];
//        a[j] = a[i];
//        a[i] = tmp;
//      }
//    }
//  }
//}
int main()
{
  int a[10] = { 3,5,9,7,4,2,1,6,0,8 };
  SelectSort(a, sizeof(a) / sizeof(a[0]));
  //打印
  Print(a, sizeof(a) / sizeof(a[0]));
  return 0;
}

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
//打印数据
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;
}