c语言三种插入排序算法_c语言编写程序实现插入排序算法

一、直接插入排序：前面基本有序，小的往前插入

#include <stdio.h>
 
 
int *Sort(int A[],int n){
/*直接插入排序精简版*/
    int i,j;
    for ( i = 1; i <= n; i++ )
        if ( A[i] < A[i-1] ){
            A[0] = A[i];
            for ( j = i; A[0] < A[j-1]; --j )
                A[j] = A[j-1];
            
            A[j] = A[0];
 
        }
    return A;
}
 
 
int main() {
 
    int a[] = {0,0,11,4,3,6,2,7,5,8,9,10,1}; //A[0]第一个是哨兵
    int lens = sizeof(a)/sizeof(a[0]); //字节总数/单个字节数
    int *b = Sort(a,lens);
    printf(" lens = %d ",lens);
    for (int i = 1; i < lens; ++i) { // A[0]第一个是哨兵
        printf("%d  ",b[i]);
    }
    return 0;
}

二、折半插入排序：前面基本有序，小的使用折半方式往前插入

#include <stdio.h>
int *Sort(int A[],int n){
/*直接插入排序精简版*/
    int i,j,low,high,mid,temp;
    for(i=1;i<n;i++){
        temp = A[i];
        low = 0;
        high = i - 1;
        while(low<=high){
            mid = (low+high)/2;
            if (A[mid] > temp) high = mid-1;
            else low = mid + 1;
        }
        for (j=i-1;j>=low;j--);
            A[j+1] = A[j];
        if(low!=i)
            A[low] = temp;
    };
   
    return A;
}
 
 
int main() {
 
    int a[] = {8,6,9,2,4,1,0}; //A[0]第一个是哨兵
    int lens = sizeof(a)/sizeof(a[0]); //字节总数/单个字节数
    int *b = Sort(a,lens);
    printf(" lens = %d ",lens);
    for (int i = 0; i < lens; ++i) { // A[0]第一个是哨兵
        printf("%d  ",b[i]);
    }
    return 0;
}