#define _CRT_SECURE_NO_WARNINGS 1
/************************************************
         * @Title:> 选择排序
         * @Description:> 蛮力法实现选择排序
         * @author:> HuaGe
         * @date:> 2020/10/26  15:48
 ***********************************************/
#include <stdio.h>
#include <stdlib.h>

//减治法思想实现插入排序
void insertSort(int a[],int length)
{
    //变量j用于标记已知数组中元素的下标，value用于存储待插入的数。
    int j, value;
    //第一个元素已经有序，所以从第二个元素起作为待插入元素
    for (int i = 1; i < length-1; i++)     
    {
        printf("第%d次插入：", i);
        //输出排序后的数组
        for (int k = 0; k < i; k++)
        {
            printf("%d\t", a[k]);
        }
        printf("\n");
        //保存待插入元素的值
        value = a[i];             
        j = i - 1;
        //在已经排好序的序列中从右向左开始与待插入元素比较
        while (j >= 0 && a[j] > value)     
        {
            //若大于，此元素右移一位
            a[j + 1] = a[j]; 
            //继续向左移动，比较下一个元素，直到找到小于待插入元素的元素
            j--;                                  
        }
        //找到小于待插入元素的元素（或者到了数组的最左边），在它的右边插入待插入元素。
        a[j + 1] = value;  
    }
}

int main()
{
    //创建一个数组
    int arr[] = { 1,4,2,6,4,7 };
    //求出数组长度
    int length = sizeof(arr) / sizeof(arr[0]);
    printf("最初数组：");
    for (int i = 0; i < length; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
    //调用排序函数
    insertSort(arr,length);
    //输出排序后的数组
    printf("最后一次插入结果：");
    for (int i = 0; i < length; i++)
    {
        printf("%d\t", arr[i]);
    }
    return 0;
}

//
//#include<stdio.h>
//#include<string.h>
//
////用蛮力法实现选择排序
//void selectSort(int* array,int length)
//{
//  for (int i = 0; i < length; i++) {
//      //假设位置为i的是要比较的最小值
//      int index = i;
//      //遍历比较（找后面是否有比i更小的数）
//      for (int j = i + 1; j < length; j++) {
//          if (array[j] < array[index]) {
//              index = j;
//          }
//      }
//      if (index != i) {
//          int temp = array[i];
//          array[i] = array[index];
//          array[index] = temp;
//      }
//      printf("第%d次排序：", i);
//      //输出排序后的数组
//      for (int k = 0; k <= length-1; k++)
//      {
//          printf("%d\t", array[k]);
//      }
//      printf("\n");
//
//  }
//}
//
//int main()
//{
//  //创建一个数组
//  int arr[] = { 1,4,2,6,4,7 };
//  //求出数组长度
//  int length = sizeof(arr) / sizeof(arr[0]);
//  printf("最初数组：");
//  for (int i = 0; i < length; i++)
//  {
//      printf("%d ", arr[i]);
//  }
//  printf("\n");
//  //调用排序函数
//  selectSort(&arr[0],length);
//  //输出排序后的数组
//  printf("最终数组：");
//  for (int i = 0; i < length; i++) {
//      printf("%d ", arr[i]);
//  }
//
//  return 0;
//}