/*

* =========================================================

* Filename: insertion.c

* Description: Insertion sort is a simple sorting algorithm

* that works the way we sort playing cards in our hands

*

* =========================================================

*/

#include <stdio.h>

void insertionSort(int arr[],int n);

void printArray(int arr[],int n);

int main()

{

int arr[] = {12, 11, 13, 5, 6};

int n = sizeof(arr)/sizeof(arr[0]);

insertionSort(arr, n);

printArray(arr, n);

return 0;

}

void insertionSort(int arr[],int n){

int i,j,unsort;

for(i = 0 ;i < n;i++){

unsort = arr[i];

j = i - 1;

while(j >= 0 && unsort < arr[j]){//两个操作可以在一起的,我sb的放到两个循环中

arr[j + 1] = arr[j];

j--;

}

arr[j + 1] = unsort;

/* int position = j + 1;

* if(position != i)

* for(j = i-1 ;j >= position;j--)

* arr[j + 1] = arr[j];//take arr[j] to arr[j + 1]

* arr[position] = unsort;

*/

}

}

void printArray(int arr[],int n){

int i = 0;

while(i < n){

printf("%d%s",arr[i],(i == n-1)?"\n":" ");

i++;

}

}