插入排序

// insertion_sort.h not with template#include <iostream>#include <stdint.h>// INSERTION-SORT(A)// for j = 2 to A.length//     key = A[j]//     // Insert A[j] into sorted sequence A[1..j - 1].//     i = j - 1//     while i > 0 and a[i] > key//         a[i + 1] = a[i]//         i = i - 1//     a[i + 1] = key// allow the same keyvoid insertion_sort(uint64_t* A, uint64_t const n){       uint64_t key;    int64_t i;    // j = 2 to A.length(j 1 to n - 1)    for (uint64_t j = 1; j < n; j++) // j begin with A[1]    {        key = A[j];        i = j - 1;                   // i begin with A[0]        while (i >= 0 && A[i] > key)        {            A[i + 1] = A[i];            i--;        }        A[i + 1] = key;    }}// insertion_sort.cpp#include "insertion_sort.h"#ifdef __linux#include <stdio.h>#endifint main(){    uint64_t array[6] = { 5, 2, 4, 6, 1, 3 };    for (uint64_t i = 0; i < sizeof(array) / sizeof(uint64_t); i++)    {        std::cout << array[i] << " ";    }    std::cout << std::endl;    insertion_sort(array, sizeof(array) / sizeof(uint64_t));    for (uint64_t i = 0; i < sizeof(array) / sizeof(uint64_t); i++)    {        std::cout << array[i] << " ";    }    std::cout << std::endl;    getchar();    return 0;}

插入排序模版

// 插入排序 insertion_sort_t.h#include <iostream>#include <string>// INSERTION-SORT(A)// for j = 2 to A.length//     key = A[j]//     // Insert A[j] into sorted sequence A[1..j - 1].//     i = j - 1//     while i > 0 and a[i] > key//         a[i + 1] = a[i]//         i = i - 1//     a[i + 1] = keytemplate <class Type> void insert_sort_t(Type * const a, int const & n){    Type key;    // j赋值为1因为是从第二个元素开始插入排序    // j<n因为n代表着待排序的数组元素的个数，n-1为最后一个元素    for (int j = 1; j < n; j++)    {        key = a[j];    // 等待插入的元素为a[j]        int i = j - 1; // a[0...j-1]为已经有序的部分，a[j+1...n-1]为还没有排序的部分        // 我们首先要比较的是a[j]与a[j-1]        while ((i >= 0) && (a[i] > key))        {            a[i + 1] = a[i]; // 所有比a[j]大的元素后移一位            i--;        }        a[i + 1] = key;      // 将a[j]放到正确的位置上去    }}// insertion_sort_t.cpp#include "insertion_sort_t.h"#ifdef __linux#include <stdio.h>#endifint main(){    int a[6] = { 5, 2, 4, 6, 1, 3 };    insert_sort_t(a, 6);    for (int i = 0; i < 6; i++)    {        std::cout << a[i] << " ";    }    std::cout << std::endl;    std::string b[4] = { "hello", "China", "haha",  "I Love China"};    insert_sort_t(b, 4);    for (int i = 0; i < 4; i++)    {        std::cout << b[i] << " ";    }    std::cout << std::endl;    getchar();    return 0;}

算法导论2.1 插入排序