////  main.c//  InsertionSortList////  Created by weilian on 14/12/12.//  Copyright (c) 2014年 weilian. All rights reserved.//#include <stdio.h>#include <stdlib.h>typedef struct ListNode *List;typedef List ptrNode;//节点的定义struct ListNode{    int Element;    struct ListNode *Next;};void InsertSort(int A[] , int N);//插入排序的数组版本void ListInsertSort(List A);   //插入排序的链表版本void ListInsert(int N , List H);//链表操作，生成一个链表int main(int argc, const char * argv[]) {        int A[15] = {1,2,3,4,5,6,7,8,9,10,28,15,0,20,2};    List H = malloc( sizeof(struct ListNode));    if (H ) {        H->Element = 0 ;        H->Next = NULL ;            }    //生成一个链表    for (int i = 0 ; i < 15 ; i++) {        ListInsert(A[i] , H);    }    //链表的插入排序    ListInsertSort(H);        //打印排好序的链表    List h = H->Next;    while (h) {        printf("%d ", h->Element);        h = h->Next;    }            //下面被注释的部分，是数组插入排序的测试版本    //int A[15] = {1,2,3,4,5,6,7,8,9,10,28,15,0,20,2};    //InsertSort( A , 15);    //for (int i = 0 ; i < 15; i++) {    //  printf("%d ", A[i]);    //}    return 0;} // 插入排序的数组实现版本void InsertSort(int A[] , int N){    int i , j ;    int Tmp ;        for (i = 1 ; i < N ; i++) {        Tmp = A[i];        /* 这段代码是错误的，不过我还没发现错在哪        for ( j = i ; j>= 1 ; j--) {            if (A[j-1] > Tmp)                A[j] = A[j-1];        }                  */                for (j = i ; j > 0 && A[j-1] > Tmp ; j --)               A[j] = A[j-1];        A[j] = Tmp ;    }}//插入排序的链表版本// 其基本思想是：TheCurrentPosition从第二个节点开始，直到最后一个节点// 每到一个节点，TheHeadList 就从第一节点开始往后走，寻找第一个大于此节点的节点// 然后思想和插入排序一样，往后交换数据就可以了// 运用归纳法证明自己的程序是正确的// 网上的实现版本是再建一个表头，用双表来实现，从当前表取出一个节点// 然后运用链表的插入操作来实现排序。// 都差不多void ListInsertSort(List A){    if (A == NULL ||A->Next == NULL)        return ;        List TheHeadOfList , TheCurrentPosition;    int Tmp , Tmp2;        TheHeadOfList = A->Next; // 这个指针始终指向第一个节点        TheCurrentPosition = TheHeadOfList->Next;    while (TheCurrentPosition) {        // 寻找第一个大于TheCurrentPosition的值        while (TheHeadOfList->Element < TheCurrentPosition->Element               && TheHeadOfList != TheCurrentPosition )            TheHeadOfList = TheHeadOfList->Next;        Tmp = TheCurrentPosition->Element;        //从当前节点往后交换数据        while (TheHeadOfList != TheCurrentPosition->Next) {            Tmp2 = TheHeadOfList->Element;            TheHeadOfList->Element = Tmp;            Tmp = Tmp2;            TheHeadOfList = TheHeadOfList->Next;                    }        //以上完成后，进入下一个节点，TheHeadList初始为初始节点        TheCurrentPosition = TheCurrentPosition->Next;        TheHeadOfList = A->Next;                    }}//链表的插入操作void ListInsert(int N , List H){    ptrNode TmpNode;        TmpNode = (ptrNode) malloc(sizeof(struct ListNode));    TmpNode->Element = N ;    TmpNode->Next = H->Next;    H->Next = TmpNode;        }