/*
 * FileName:          bidir_insertion_sort.c
 * Author:            Antigloss at http://stdcpp.cn
 * LastModifiedDate:  2005-11-12 12:00
 * Purpose:           Bidirection Insertion Sort
 */

#include <stdio.h>
#include <stddef.h>

#define ARR_SIZE 10

/* 函数原型 */
void bidir_insert( int keys[], int temp[], const size_t i );

int main(void)
{
    size_t i;
    int keys[ARR_SIZE] = { 1050, 100, 150, 20, 9000, 5110, 3008, 1450, 5220, 500 };
    int temp[ARR_SIZE];  /* 辅助数组 */
   
    /* 进行二路插入排序 */
    bidir_insert(keys, temp, ARR_SIZE);
    /* 输出排序结果 */
    for ( i = 0; i < ARR_SIZE; ++i ) {
        printf("%d ", keys[i]);
    }
   
    printf("\nPress ENTER to quit...\n");
    getchar();
    return 0;
}

/* Begin of bidir_insert 05-11-12 12:00 */
void bidir_insert( int keys[], int temp[], const size_t arr_size )
{
     size_t i, first, final = first = 0;
    
     temp[0] = keys[0]; /* 将第一个元素放入辅助数组 */
     /* 利用辅助数组 temp 进行二路插入排序 */
     for ( i = 1; i < arr_size; ++i ) {
         if ( temp[final] <= keys[i] ) {            
             temp[++final] = keys[i];
         } else if ( keys[i] <= temp[first] ) {
             first = (first - 1 + arr_size) % arr_size;
             temp[first] = keys[i];
         } else {
             size_t index;
            
             for ( index = (final - 1 + arr_size) % arr_size; ;
                   index = (index - 1 + arr_size) % arr_size ) {
                 if ( temp[index] <= keys[i] ) {
                     size_t mid = final++;
                     /* 元素后移 */
                     while ( mid != index ) {
                         temp[(mid + 1) % arr_size] = temp[mid];
                         mid = (mid - 1 + arr_size) % arr_size;
                     }
                     temp[(index + 1) % arr_size] = keys[i];
                    
                     break;
                 }
             }
         }
     }
    
     /* 将 temp 的内容按顺序复制到 keys 中 */
     for ( i = 0; i < arr_size; ++i ) {
         keys[i] = temp[first];
         first = (first + 1) % arr_size;
     }
}  /* End of bidir_insert */

本文版权归 蚂蚁的 C/C++ 标准编程 以及 作者 antigloss 共同所有，转载请注明原作者和出处。谢谢。