数据结构排序——选择排序与堆排序（c语言实现）

void Swap(int* x, int* y)
{
  int tmp = *x;
  *x = *y;
  *y = tmp;
}
void SelectSort(int* a, int n)//升序
{
  for (int i = 0; i < n-1; i++)//n个数据，排n-1次
  {
    int mini = i;//0到i-1都已经排好，下一个就放在i这个位置上
    for (int j = i+1; j < n; j++)//从i到n-1找最小的，因为本身是i，所以j可以中i+1开始
    {
      if (a[minf] > a[j])
      {
        minf = j;//找到小的就来替换
      }
    }
    Swap(&a[minf], &a[i]);
  }
}
int main()
{
  int a[] = { 9,1,2,5,7,4,8,6,3,5,1,2,3,5,1,8,3 };
  printf("排序前：");
  for (int i = 0; i < sizeof(a) / sizeof(int); i++)
  {
    printf("%d ", a[i]);
  }
  printf("\n");
  SelectSort(a, sizeof(a) / sizeof(int));
  printf("排序后：");
  for (int i = 0; i < sizeof(a) / sizeof(int); i++)
  {
    printf("%d ", a[i]);
  }
  printf("\n");
  return 0;
}

void SelectSort(int* a, int n)//升序
{
  int begin = 0, end = n - 1;
  while (begin < end) //begin=end时就已经排好了
  {
    int mini = begin, maxi = begin;//不知道会指向哪里，所以要每次都初始化
    for (int i = begin + 1; i <= end; i++)//从begin到end找最大和最小
    {
      if (a[i] < a[mini])
      {
        mini = i;
      }
      if (a[i] > a[maxi])
      {
        maxi = i;
      }
    }
    Swap(&a[begin], &a[mini]);//最小跟begin换
    if (begin == maxi)//有可能begin位置就是此时最大的，maxi=begin，要是交换了，maxi值就不对了
    {
      maxi = mini;//让maxi仍是最大的数据的索引（此时数据被换到mini所指）
    }
    Swap(&a[end], &a[maxi]);
    begin++;
    end--;
  }
}

#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"
void Swap(HPDataType* p1, HPDataType* p2)
{
  HPDataType tmp = *p1;
  *p1 = *p2;
  *p2 = tmp;
}
void AdjustUp(HPDataType* a, int child)
{
  int father = (child - 1) / 2;
  while (child > 0)
  {
    if (a[child] > a[father])
    {
      Swap(&a[child], &a[father]);
      //更新下标
      child = father;
      father = (father - 1) / 2;
    }
    else
    {
      break;//一旦符合小堆了，就直接退出
    }
  }
}
void AdjustDown(HPDataType* a, int n, int father)
{
  int child = father * 2 + 1;//假设左孩子大
  while (child < n)
  {
    if (child + 1 < n && a[child] < a[child + 1])
    {
      child++;
    }
    if (a[child] > a[father])
    {
      Swap(&a[child], &a[father]);
      father = child;
      child = father * 2 + 1;
    }
    else
    {
      break;
    }
  }
}
void HeapSort(int* arr, int n)//升序
{
  //先建大堆
  for (int i = 0; i < n; i++)
  {
    AdjustUp(arr, i);
  }
  int a = n - 1;
  while (a > 0)
  {
    //此时最大的是堆顶，堆顶跟最后一个交换
    Swap(&arr[0], &arr[a]);
    //现在最大的已经在最后了，不考虑它，把新塔顶降下来，重新编程大堆
    AdjustDown(arr, a, 0);
    a--;
  }
}
int main()
{
  int arr[]= { 4,6,2,1,5,8,2,9 };
  for (int i = 0; i < sizeof(arr) / sizeof(int); i++)
  {
    printf("%d ", arr[i]);
  }
  printf("\n");
  HeapSort(arr, sizeof(arr) / sizeof(int));
  for (int i = 0; i < sizeof(arr) / sizeof(int); i++)
  {
    printf("%d ", arr[i]);
  }
}