博客

C++实现插入排序

思路：


1.从数组的第二个数据开始往前比较，即一开始用第二个数和他前面的一个比较，如果 符合条件（比前面的大或者小，自定义），则让他们交换位置。

2.然后再用第三个数和第二个比较，符合则交换，但是此处还得继续往前比较，比如有 5个数8，15，20，45, 17,17比45小，需要交换，但是17也比20小，也要交换，当不需 要和15交换以后，说明也不需要和15前面的数据比较了，肯定不需要交换，因为前 面的数据都是有序的。

3.重复步骤二，一直到数据全都排完。

//插入排序
void insertion_sort(int a[], int n)
{
    for (int i = 1; i < n; i++)
    {
        for (int j = i; j >= 1; j--)
        {
            if (a[j] < a[j - 1])
            {
                int tmp = a[j];
                a[j] = a[j - 1];
                a[j - 1] = tmp;
            }
            else
                break;
        }
    }

}

int main()
{
    int n[] = { 11,7,0,5,10,2,9 };//6
    int length = sizeof(n) / sizeof(n[0]);
    insertion_sort(n, length);
    for (int i = 0; i < length; i++)
    {
        cout << n[i] << ' ';
    }
    cout << endl;

    return 0;
}