【改良插入排序】

/*
說明：
插入排序法由未排序的後半部分前端取出一個值，插入已排序前半部分的適當位置，概念簡單但速度不快。
排序要加快的基本原則之一，是讓後一次的排序進行時，儘量利用前一次排序後的結果，以加快排序的速度，Shell排序法即是基於此一概念來改良
插入排序法。

解法：
略 
*/

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

#define MAX 10
#define SWAP(x, y) {int t; t = x; x = y; y = t;}

void shellsort(int[]);

int main(void){
    int number[MAX] = {0};
    int i; 
    
    srand(time(NULL));
    
    printf("排序前: \n");
    for(i = 0; i < MAX; i++){
        number[i] = rand() % 100;
        printf("%d ", number[i]);
    }  
    
    shellsort(number);
     
//    system("pause");
    return 0;
}

void shellsort(int number[]){
    int i, j, k, gap, t;
    
    gap = MAX / 2;
    
    printf("\n排序後: \n");
    while(gap > 0){
        for(k = 0; k < gap; k++){
            for(i = k + gap; i < MAX; i += gap){
                for(j = i - gap; j >= k; j -= gap){
                    if(number[j] > number[j + gap]){
                        SWAP(number[j], number[j + gap]);
                    }
                    else{
                        break;
                    }
                } 
            }
        }
        
        printf("\n gap = %d: ", gap);
        for(i = 0; i < MAX; i++){
            printf("%d ", number[i]);
        }
        printf("\n");
        
        gap /= 2;
    }
}