算法导论读书笔记之插入

    插入排序如同打扑克牌时，对扑克牌进行整理的过程。其特点是不需要额外的存储空间，属于in-place

排序.

insertSort.c

#include "insertSort.h"

void insertSort(int *A, int len)
{
        int i, j, temp;

        if(NULL == A || len < 1)
        {
                return;
        }
        for(i = 1;i < len;i++)
        {
                for(j = i - 1;j >= 0;j--)
                {
                        if(A[j + 1] < A[j])
                        {
                                temp = A[j + 1];
                                A[j + 1] = A[j];
                                A[j] = temp;
                        }
                        else
                        {
                                break;
                        }
                }
        }
}

insertSort.h

#ifndef INSERT_SORT_H
#define INSERT_SORT_H

#include
#include

void insertSort(int *A, int len);

#endif

main.c

#include "insertSort.h"
#include
#include

void print_array(int *A, int len)
{
        int i;
        for(i = 0;i                 printf("%d ", *(A++));
        printf("\n");
}

int main()
{
        int i, len;
        int *A;

        printf("len = ");
        scanf("%d", &len);
       
        if( (A = (int *)malloc(sizeof(int) * len)) == NULL)
        {
                perror(strerror(errno));
                return 1;
        }
        for(i = 0;i < len;i++)
        {
                A[i] = rand() % 100;
        }

        printf("Before insert sorting : ");
        print_array(A, len);

        insertSort(A, len);

        printf("After insert sorting : ");
        print_array(A, len);
       
        return 0;
}