//
//  main.c
//  binarySort
//
//  Created by 韩雪滢 on 10/15/16.
//  Copyright © 2016 韩雪滢. All rights reserved.
//
//复杂度O(nlogn)
#include <stdio.h>
int a[10]={21,56,43,12,3,99,56,23,2,12};
int main()
{
    int i,j,k,low,high,mid,t;
    for(i=k=1;i<sizeof a/sizeof a[0];i++)//起始认为第一个元素是有序的,high=low=k-1=0,所以k=1,
    {
        low=0;
        high=k-1;
        while(low<=high)////折半查找时，low与high相遇，则找到插入位置
        {
            mid=(low+high)/2;
            if(a[mid]>=a[i])high=mid-1;///////元素比mid小，因此在low到mid-1范围内搜索位置
            else low=mid+1;
        }
        if(high<i|| a[low]!=a[i]) ///*****************  a[low]的值为当前排序的中位值，应该是插入的位置，退出while的条件为high<low,所以if条件成立说明插入的值不在
        {
            t=a[i];//保存当前的值，
            for(j=k-1;j>=low;j--) //////插入位置是low，所以low到high=k-1范围内的元素都要向后移动
                a[j+1]=a[j]; 
            a[low]=t; //////////////low被赋值为已经被覆盖掉的a[i]，如果这里写a[i]，此时的a[i]不是之前的a[i]，已经移动过了
            k++; 
        } 
    } 
    for(j=0;j<k;j++) 
        printf("%4d",a[j]); 
    printf("\n");
    
    return 0;
}