数据结构——选择排序

#include<stdio.h>
void SelectSort(int* array, int size);//直接选择排序
void SelectSortOP(int* array, int size);//直接选择排序改进版
void Swap(int* num1, int* num2);//整数交换
void Printf_Array(int* array, int size);//数组打印
void TestSelectSort();//测试函数
int main() {
  TestSelectSort();
  return 0;
}
void TestSelectSort() {//测试函数
  int array[] = { 5,3,2,8,7,6,9,4,1,0 };
  int length = sizeof(array) / sizeof(array[0]);
  printf("排序前：");
  Printf_Array(array, length);
  SelectSort(array, length);
  printf("\n排序后：");
  Printf_Array(array, length);
  printf("\n\n改进版：\n");
  int _array[] = { 12,15,14,19,18,11,17,16,13,10 };
  int _length = sizeof(_array) / sizeof(_array[0]);
  printf("排序前：");
  Printf_Array(_array, _length);
  SelectSortOP(_array, _length);
  printf("\n排序后：");
  Printf_Array(_array, _length);
  printf("\n");
}
void SelectSort(int* array, int size) {//直接选择排序
  for (int i = 0; i < size - 1; i++) {//排n-1趟（只剩最后一个元素时，不需要再排序）
  int maxPos = 0;
  for (int j = 0; j < size - i; j++) {//找出剩余序列中最大元素的下标
    if (array[j] > array[maxPos]) {
    maxPos = j;
    }
  }
  if (maxPos != size - i - 1) {//最大元素不在序列最后位置
    Swap(&array[size-i-1], &array[maxPos]);//将最大元素交换到序列末尾位置
  }
  }
}
void SelectSortOP(int* array, int size) {//直接选择排序改进版
  int begin = 0;
  int end = size - 1;
  while (begin < end) {//至少还有两个元素
  int minPos = begin; //每趟同时找最大元素和最小元素
  int maxPos = begin;
  int index = begin + 1;
  while (index <= end) {
    if (array[index] > array[maxPos]) {//maxPos标记较大的元素
    maxPos = index;
    }
    if (array[index] < array[minPos]) {//minPos标记较小的元素
    minPos = index;
    }
    index++;
  }
  if (minPos == end) {//若最小值恰好在末尾，交换最大值时会把最小值交换到maxPos标记的位置，所以提前改变minPos的标记位置
    minPos = maxPos;
  }
  if (maxPos != end) {//将最大的元素交换到末尾
    Swap(&array[maxPos], &array[end]);
  }
  if (minPos != begin) {//将最小的元素交换到前面
    Swap(&array[minPos], &array[begin]);
  }
  end--;
  begin++;
  }
}
void Swap(int* num1, int* num2) {//整数交换
  int temp = *num1;
  *num1 = *num2;
  *num2 = temp;
}
void Printf_Array(int* array, int size) {//数组打印
  for (int i = 0; i < size; i++) {
  printf("%d ", array[i]);
  }
}