数据结构 排序（插入排序）

//排序--插入排序法
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<time.h>

/*
选择排序（Selection sort）是一种简单直观的排序算法。
它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，
存放在序列的起始位置，直到全部待排序的数据元素排完。 
选择排序是不稳定的排序方法（比如序列[5， 5， 3]第一次就将第一个[5]与[3]交换，导致第一个5挪动到第二个5后面）。


选择排序和冒泡排序的区别
选择排序是创建一个有序数组A，
第一轮：选中无序数组B中的第一个元素 按顺序放入有序数组A中，并且把该元素从无序数组B中删除
第二轮：选中无序数组B中的第一个元素 按顺序放入有序数组A中，并且把该元素从无序数组B中删除

冒泡排序：
第一轮：将数组中的元素两两比较，通过相邻元素的交换，将当前没有排好序中的最大（小）移到数组的最右（左）端
*/

//插入法排序
void InertionSort(int * arr, int num){
    if (arr==NULL)
    {
        printf("传入参数不可以为空！\n");
        return;
    }
    int i = 0, j = 0,k=0,temp=0;
    for (i = 1; i < num; i++)
    {
        //当i=1时，有序数组里只有一个元素
        k = i;
        //此时k是无序数组里的第一个元素 想要插入有序数组 
        temp = arr[k];
        //此时i-1是有序数组中的最大下标  arr[j]就是有序数组中的最大值  与要插入的数据进行比较
        for (j = i - 1; j >= 0 && arr[j]>temp; j--)
        {
            //进入该循环  说明插入的元素  要比 有序数组中的最大元素要小  
            //可以将有序中的元素向后移动一位  留出位置  来存放被插入的元素
            arr[j + 1] = arr[j];//此时有序数组扩充一个单位  无序数组删除一个单位
            //此时 要插入的位置k也就向前移动一位   再次经过循环 如果k前移一位之后 插入元素大于有序数组位置j的元素
            //那么k的要插入的位置就是j+1---不走循环 k就不会自增了  
            k = j;
        }
        arr[k] = temp;
    }
}

//打印数组
void Print(int * arr,int num){
    if (arr == NULL)
    {
        printf("传入参数不可以为空！\n");
        return;
    }
    int i = 0;
    for (int i = 0; i < num; i++)
    {
        printf("%5d", *(arr + i));
    }
    printf("\n");
}

void Test(){
    int i = 0;
    int arr[10] = { 0 };
    //定义时间类型变量
    time_t ts;
    //生成随机数种子
    srand((unsigned int)time(&ts));
    for (i = 0; i < 10; i++)
    {
        arr[i] = (int)(rand() % 100);
    }
    //打印数组
    printf("\n原始数据----\n");
    Print(arr, 10);
    //插入法排序
    printf("插入法排序之后的数据\n");
    InertionSort(arr, 10);
    Print(arr, 10);
}

void main(){
    Test();
    system("pause");
}