insortionsort.cpp

一個簡單的insortionSort程式。把陣列分成兩部分來排序。

#include<stdio.h>
#include<stdlib.h>
#define SIZE 10//the array size
void insortionSort(int array[], const int n);//subprogram  

int main()
{   
    int array[SIZE] = {1,4,7,20,5,6,55,88,100,200};
    int i;
    
    insortionSort(array,SIZE);    
    
    for(i=0;i<=9;i++)//print out the sorted array
       printf("%d\n", array[i]);
    
    printf("\n");
    
    system("PAUSE"); 
    
    return 0; 
}
    
 
void insortionSort(int array[], const int n)//subprogram for insertion sort 
{
     int i, j, temp1, temp2;
     int low, high, mid;//for binary search
     
     for(i=0;i<n;i++){
        low = 0;
        high = i;
        temp1 = array[i];
        
        while(low<high){
        mid = (low+high)/2;
        
        if(temp1 >= array[mid])
           low = mid+1;
        else
           high = mid;
        }//while end
            
       for(j=i;j>low;j--){//exchange 
          temp2 = array[j-1];
          array[j-1] = array[j];
          array[j] = temp2;
          }//for end
       
       array[low]=temp1;
         
   }//for end

}//subprogram end