基础算法：选择排序和插入排序的实现代码

本文的copyleft归[e-mail]所有，使用GPL发布，可以自由拷贝，转载。但转载请保持文档的完整性，注明原作者及原链接，严禁用于任何商业用途。
作者：[e-mail]
博客：linuxfocus.blog.chinaunix.net  

从最最基础的算法开始温习，不考虑通用性，都是对整数数组进行排序。——各位兄弟，原谅我重新制作车轮吧。。。。

1. 选择排序

思想是通过每次选择最小值，次小值，次次小值等，将其置换到对应的位置，从而依次选择，最后实现最终的排序。

void selection_sort(int *array, int size)
{
    int i, j, t, min;

     

     /* 依次选择最小值， 最后一个元素不需要比较 */

    for (i = 0; i < size-1; ++i) {
        min = i;
        /* 找出本次的最小值 */
        for (j = i+1; j < size; ++j) {
            if (array[j] < array[min]) {
                min = j;
            }
        }

        /* 需要置换 */
        if (min != i) {
            /* 置换本次最小值 */
            t = array[min];
            array[min] = array[i];
            array[i] = t;
        }
    }
}

2. 插入排序

思想是视元素左侧的所有元素为已排序的，然后将该元素插入到合适的位置，从而维持左侧所有元素有序。这样依次进行，当遍历完所有元素时，则排序完成

void insertion_sort(int *array, int size)
{
    int i, j, t;

     /* 从第二个元素开始进行插入排序 */

    for (i = 1; i < size; ++i) {
        /* 因为可能需要将前面已排序元素后移，所有需要记住当前元素值 */
        t = array[i];
        /* 找到当前元素在已排序元素中插入的位置 */
        for (j = i-1; j >=0; --j) {
            if (array[j] > t) {
                /* 后移该元素 */
                array[j+1] = array[j];
            }
            else {
                /* 找到了合适的位置 */
                break;
            }
        }
        array[j+1] = t;
    }
}