插入排序--《编程珠玑》

如百度百科：有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外，而第二部分就只包含这一个元素。在第一部分排序后，再把这个最后元素插入到此刻已是有序的第一部分里的位置。

简而言之，就是将一个数据很好的插入已经有序的数列中，当然，依然是递增或是递减；

思想：首先第一个数据肯定是有序的，由第二个数据开始处理，进行插入排序：

以上述4个简单的数据为例，首先默认3是有序的，从第二个数据1开始，插入排序之后为1 3，接下来对第三个数据4进行排序...依次类推：

核心代码：

for(int i = 1; i < n; i++)
    {
        for(int j = i; j > 0 && a[j - 1] > a[j]; j--)
            swap(a[j - 1], a[j]);
    }

for(int i = 1; i < n; i++)
    {
        for(int j = i; j > 0 && a[j - 1] > a[j]; j--)
        {
            temp = a[j];
            a[j] = a[j - 1];
            a[j - 1] = temp;
        }
    }

int j;
    for(int i = 1; i < n; i++)
    {
        temp = a[i];
        for(j = i; j > 0 && a[j - 1] > a[j]; j--)
            a[j] = a[j - 1];
        a[j] = temp;
    }

顺序如上...完整代码：

#include <iostream>
#include <algorithm>

using namespace std;

void sort(int a[], int n)
{
    int temp;
    int j;
    for(int i = 1; i < n; i++)  //sort3
    {
        temp = a[i];
        for(j = i; j > 0 && a[j - 1] > a[j]; j--)
            a[j] = a[j - 1];
        a[j] = temp;
    }
    /*for(int i = 1; i < n; i++)  //sort2
    {
        for(int j = i; j > 0 && a[j - 1] > a[j]; j--)
        {
            temp = a[j];
            a[j] = a[j - 1];
            a[j - 1] = temp;
        }
    }*/
    /*for(int i = 1; i < n; i++)  //sort1
    {
        for(int j = i; j > 0 && a[j - 1] > a[j]; j--)
            swap(a[j - 1], a[j]);
    }*/
}

void display(int a[], int n)
{
    for(int i = 0; i < n; i++)
        cout << a[i] << "  ";
    cout << endl;
}

int main()
{
    int a[] = {3, 1, 2, 4, 8, 9};
    int n = sizeof(a) / sizeof(int);
    sort(a, n);

    display(a, n);
    return 0;
}

插入排序--《编程珠玑》,布布扣,bubuko.com

插入排序--《编程珠玑》

原文：http://blog.csdn.net/xjm199/article/details/22733437