插入排序

插入排序

按照计划,接下来开始实现书中的一些算法。今天是比较简单的插入排序法,但是也不是一次就成功,可见再简单的算法,也需要真正实践才能确保没有问题。

主要问题是处在插入排序需要找到一个key,用于标记当前需要插入的值。其原理想象起来也简单,就是想插入扑克牌一样,把目标扑克牌插入一个已经排序好的牌中,所以需要一个key来标记当前要插入的牌。而平时写冒泡比较多,所以很习惯的就写了两个for循环,然后才发现不太好往下面写了,其实第二循环换成while更加顺畅。

#include 

void InsertionSort(int array[], int length){
    int i = 1;
    int j = 0;
    for(; i < length; i++){
        int key = array[i];
        j = i - 1;
        while(j >= 0 && array[j] > key){
            array[j+1] = array[j];
            j--;
        }
        array[j+1] = key;
    }
}

int main(int argc, char** argv){
    int array[] = {8, 7, 6, 5, 4, 3, 2, 1};
    int length = 8;
    int i = 0;
    printf("before sort\n");
    for(; i < length; i++){
        printf("%d ", array[i]);
    }
    printf("\n");
    InsertionSort(array, length);
    printf("after sort\n");
    for(i = 0; i < length; i++){
        printf("%d ", array[i]);
    }
    printf("\n");
}

Leave a Reply

Your email address will not be published. Required fields are marked *