C之插入排序

#include<stdio.h>typedef int ElemType;void InsertSort(ElemType A[],int n);void BInsertSort(ElemType A[],int n);void ShellSort(ElemType A[],int n);void PRint_arr(ElemType A[],int n);int  main(){    int Arr[9] = {0,5,2,68,676,3,46,74,32};    int Arr_num = 8;     printf("原数组： ");    print_arr(Arr,Arr_num);//    printf("---直接插入排序---/n");//    InsertSort(Arr,Arr_num);//    print_arr(Arr,Arr_num);////    printf("---二分查找插入排序---/n");//    BInsertSort(Arr,Arr_num);//    print_arr(Arr,Arr_num);    printf("---希尔排序---/n");    ShellSort(Arr,Arr_num);    print_arr(Arr,Arr_num);    return 0;}//直接插入//将子序列按照顺序一个个排序好，不断向已经排序好的子序列中插入元素//稳定//时间复杂度n~n^2//空间复杂度1//比较和移动次数都与初始状态相关//比较最好为n-1，最坏为n(n-1)/2,平均比较n^2/4//移动最好为0，最坏为n(n+1)/2,平均移动n^2/4void InsertSort(ElemType A[],int n){    int i,j;    for( i = 2; i <= n; i ++)    {        if( A[i] < A[i-1] )        {            A[0] = A[i];            for( j = i - 1; j > 0&&A[0] < A[j]; j --)//第一个条件可以不用 j按一个长度递减，数组不会越界                A[j + 1] = A[j];            A[j + 1] = A[0];        }    }}//折半插入//直接插入的变形 在已排序好的子序列中查找待插入元素的位置，使用二分查找//稳定//时间复杂度 n*log2(n)~n^2//比较次数与初始状态无关，始终为n*log2(n)//移动次数与初始状态相关，顺序为0，逆序为n(n+1)/2，平均移动n^2/4void BInsertSort(ElemType A[],int n){    int i,j,low,high,mid;    for(i = 2; i <=n; i ++)    {        low = 0;        high = n - 1;        A[0] = A[i];        while(low <= high)        {            mid = (low + high) /2;            if(A[mid] > A[0]) high = mid - 1;            else low = mid + 1;        }        for(j = i - 1; j >= high + 1; j --)        {            A[j + 1] = A[j];        }        A[high + 1] = A[0];    }}//希尔//对排序表进行按照 i,i+dk,i+2dk···进行分割，然后进行直接插入排序//直接插入排序是步长都为1//不稳定 复杂度n^1.3~n^2void ShellSort(ElemType A[],int n){    int dk;//步长    int  count = 0;//排序次数    int i,j;    for(dk = n/2; dk >= 1; dk = dk/2)    {        ++ count;        for(i = 1 + dk; i <= n; i ++)        {            if(A[i] < A[i - dk])            {                A[0] = A[i];                for(j = i - dk; j > 0 && A[0] < A[j]; j -= dk)//j>0边界条件不可省略 j - dk可能大于小于0，数组越界                    A[j + dk] = A[j];                A[j + dk] = A[0];            }        }        printf("第%d次排序： ",count);        print_arr(A,n);//打印每次排序结果    }}void print_arr(ElemType A[],int n){    int i;    for(i = 1; i <= n; i++)    {        printf("%d ",A[i]);    }    printf("/n");}