C版的迷你程序——插入排序算法 迷你枪战精英小程序视频全部

插入排序--Insertion Sort也是一种简单直观的排序算法，通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，需要从后向前扫描，需要反复把已排序元素逐步向后挪位，为最新元素提供插入的空间。

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <sys/time.h>

void ShowSortPro(int arr[], int len)
{
    int i;
    for (i=0; i<len; i++)
        printf("%6d ", arr[i]);
    printf(" \n");
}

// 
// 选择排序
// 输入参数：数组
//           数组的长度
//
void InsertionSort(int arr[], int len)
{
    int i, j, temp;
    for (i=1; i<len; i++){
        printf("======================================================== %d\n", i);
        temp = arr[i];
        for (j=i; j>0 && arr[j-1]>temp; j--){    // 在已排序序列中从后向前扫描，找到相应位置并插入
            arr[j] = arr[j-1];
            ShowSortPro(arr, len);
        }
        arr[j] = temp;
        printf("====================================================\n");
        ShowSortPro(arr, len);
        printf("======================================================== %d\n", i);
    }
}


void main() {
    int arr[] = { 65, 75, 59, 26, 92, 19, 8, 67 };
    int len;

    // sizeof是运算符，不是函数
    // sizeof能求得静态分配内存的数组的长度,即占用内存的大小，以byte为单位
    len = (int) sizeof(arr) / sizeof(arr[0]);
    //printf("%ld \n", sizeof(arr));
    //printf("%ld \n", sizeof(arr[0]));

    ShowSortPro(arr, len);
    printf("============================================================START\n");
    InsertionSort(arr, len);
    printf("============================================================END\n");
    ShowSortPro(arr, len);
}

这里只是测试编译器对代码进行自动优化编译和不优化的耗时比较，这个算法的耗时其实也会受到原始数据序列性影响，所以代码把随机数的种子取消了，编译优化不优化处理同样的数据。要注意优化后程序的结果要正确耗时比较才有意义。下面有冒泡和选择排序的测试，仅仅参考下：

选择的排序算法

冒泡的排序

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <sys/time.h>

void ShowSortPro(int arr[], int len)
{
    int i;
    for (i=0; i<len; i++)
        printf("%6d ", arr[i]);
    printf(" \n");
}

// 
// 选择排序
// 输入参数：数组
//           数组的长度
//
void InsertionSort(int arr[], int len)
{
    int i, j, temp;
    for (i=1; i<len; i++){
        //printf("======================================================== %d\n", i);
        temp = arr[i];
        for (j=i; j>0 && arr[j-1]>temp; j--){    // 在已排序序列中从后向前扫描，找到相应位置并插入
            arr[j] = arr[j-1];
            //ShowSortPro(arr, len);
        }
        arr[j] = temp;
        //printf("====================================================\n");
        //ShowSortPro(arr, len);
        //printf("======================================================== %d\n", i);
    }
}


#define N 16*1024
int arrtime[N];
int arrtimecopy[N];
void main() {
    int len=15;
    int i;
    //srand((unsigned)time(NULL));
    for (i = 0; i < N; i++)
        arrtime[i] = rand()%32768;
    for (i = 0; i < N; i++)
        arrtimecopy[i] = arrtime[i];
    
    struct timeval start_time, end_time;
    unsigned  int spend_us = 0;
    ShowSortPro(arrtime, len);
    printf("============================================================START\n");
    gettimeofday(&start_time, NULL);
    InsertionSort(arrtime, N);
    gettimeofday(&end_time, NULL);
    spend_us +=  end_time.tv_usec-start_time.tv_usec+1000000*(end_time.tv_sec-start_time.tv_sec);
    printf("============================================================END\n");
    ShowSortPro(arrtime, len);
    printf("1 \t spend %ld us \n", (end_time.tv_usec-start_time.tv_usec+1000000*(end_time.tv_sec-start_time.tv_sec)));
    
    for (i=0; i<N; i++)
        arrtime[i] = arrtimecopy[i];
    
    ShowSortPro(arrtime, len);
    printf("============================================================START\n");
    gettimeofday(&start_time, NULL);
    InsertionSort(arrtime, N);
    gettimeofday(&end_time, NULL);
    spend_us +=  end_time.tv_usec-start_time.tv_usec+1000000*(end_time.tv_sec-start_time.tv_sec);
    printf("============================================================END\n");
    ShowSortPro(arrtime, len);
    printf("2 \t spend %ld us \n", (end_time.tv_usec-start_time.tv_usec+1000000*(end_time.tv_sec-start_time.tv_sec)));

    
    for (i=0; i<N; i++)
        arrtime[i] = arrtimecopy[i];
    
    ShowSortPro(arrtime, len);
    printf("============================================================START\n");
    gettimeofday(&start_time, NULL);
    InsertionSort(arrtime, N);
    gettimeofday(&end_time, NULL);
    spend_us +=  end_time.tv_usec-start_time.tv_usec+1000000*(end_time.tv_sec-start_time.tv_sec);
    printf("============================================================END\n");
    ShowSortPro(arrtime, len);
    printf("3 \t spend %ld us \n", (end_time.tv_usec-start_time.tv_usec+1000000*(end_time.tv_sec-start_time.tv_sec)));

    
    for (i=0; i<N; i++)
        arrtime[i] = arrtimecopy[i];
    
    ShowSortPro(arrtime, len);
    printf("============================================================START\n");
    gettimeofday(&start_time, NULL);
    InsertionSort(arrtime, N);
    gettimeofday(&end_time, NULL);
    spend_us +=  end_time.tv_usec-start_time.tv_usec+1000000*(end_time.tv_sec-start_time.tv_sec);
    printf("============================================================END\n");
    ShowSortPro(arrtime, len);
    printf("4 \t spend %ld us \n", (end_time.tv_usec-start_time.tv_usec+1000000*(end_time.tv_sec-start_time.tv_sec)));
    

    for (i=0; i<N; i++)
        arrtime[i] = arrtimecopy[i];
    
    ShowSortPro(arrtime, len);
    printf("============================================================START\n");
    gettimeofday(&start_time, NULL);
    InsertionSort(arrtime, N);
    gettimeofday(&end_time, NULL);
    spend_us +=  end_time.tv_usec-start_time.tv_usec+1000000*(end_time.tv_sec-start_time.tv_sec);
    printf("============================================================END\n");
    ShowSortPro(arrtime, len);
    printf("5 \t spend %ld us \n", (end_time.tv_usec-start_time.tv_usec+1000000*(end_time.tv_sec-start_time.tv_sec)));
    printf("T \t spend %f us \n", spend_us/5.0);
}