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

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

/*
插入排序：
插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，
从而得到一个新的、个数加一的有序数据，
算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。
插入排序的基本思想是：
每步将一个待排序的纪录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。

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


*/

//插入法排序
void InertionSort(int * arr, int num){
    if (arr == NULL)
    {
        printf("传入参数不可以为空！
");
        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("传入参数不可以为空！
");
        return;
    }
    int i = 0;
    for (int i = 0; i < num; i++)
    {
        printf("%5d", *(arr + i));
    }
    printf("
");
}

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("
原始数据----
");
    Print(arr, 10);
    //插入法排序
    printf("插入法排序之后的数据
");
    InertionSort(arr, 10);
    Print(arr, 10);
}

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