dataStructures/sort/InsertSort/main.cpp

//
// Created by tangs on 2018/11/16.
//


#include <iostream>

using namespace std;

// 书上的实现方式，其中只能排序1 ~ n-1 个元素， 第0个元素被当做中间变量。
void InsertSort(int A[], int n) {
    int i, j;
    for (i = 2; i < n; i++) {
        if (A[i] < A[i - 1]) {
            A[0] = A[i];
            for (j = i - 1; A[0] < A[j]; --j) {
                A[j + 1] = A[j];
            }
            A[j + 1] = A[0];
        }
    }
}

// 自己实现，不占用数组空间来当中间变量。
void InsertSortBySelf(int A[], int n) {
    int i, j, temp;
    for (i = 1; i < n; i++) {
        if (A[i] < A[i - 1]) {
            temp = A[i];
            for (j = i - 1; A[j] > temp && j >= 0; j--) {
                A[j + 1] = A[j];
            }
        }
        A[j + 1] = temp;
    }
}

int main() {
    int A1[] = {6, 1, 5, 2, 1, 9, 10, 24, 7, 0};
    InsertSort(A1, 10);

    // print:
    // 0 0 1 1 2 5 7 9 10 24
    for (int i = 0; i < 10; i++) {
        cout << A1[i] << " ";
    }
    cout << endl;

    // --------------------------------------------------------------------------

    int A2[] = {6, 1, 5, 2, 1, 9, 10, 24, 7, 0};
    InsertSortBySelf(A2, 10);

    // print:
    // 0 1 1 2 5 6 7 9 10 24
    for (int i = 0; i < 10; i++) {
        cout << A2[i] << " ";
    }
    cout << endl;

    return 0;
}