典型的なソートアルゴリズム(C言語実装)

「データ構造(C言語版)」の最後の実験作業(ソート)は、以下のように要求される.
データ構造実験5:並べ替え要求:1、直接挿入並べ替え;2、shellソート;3、簡単にソートを選択する;4、クイックソート;5、スタックの順序付け(選択);
私(@tongtongxyz)の宿題を共有しましょう.

/***************************************
 *  Filename: sort.cpp                 *
 *  Function:                    *
 *  Author: TongtongXyz                *
 *  Weibo: @tongtongxyz                *
 *  Date: 20130112                     *
 ***************************************/
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100    //     
typedef int KeyType;
typedef int InfoType;
typedef struct{
    KeyType key;
    InfoType otherinfo;
}RedType;
typedef struct{
    RedType r[MAXSIZE+1];
    int length;
}SqList;
typedef SqList HeapType;
void InsertSort(SqList &L){
    //      
    int i, j;
    for(i = 2; i <= L.length; ++i){
        if(L.r[i].key < L.r[i-1].key){
            L.r[0] = L.r[i];
            L.r[i] = L.r[i-1];
            for(j = i - 2; L.r[0].key < L.r[j].key; --j){
                L.r[j+1] = L.r[j];
            }
            L.r[j+1] = L.r[0];
        }
    }
}
void SortOutput(SqList &L){
    printf("             ：
");
    for(int i = 1; i <= L.length; i++){
        printf("%d  ", L.r[i].key);
    }
    printf("

");
}
void SortInput(SqList &L, KeyType key){
    L.r[++L.length].key = key;
}
void ShellInsert(SqList &L, int dk){
    int i, j;
    for(i = dk + 1; i <= L.length; ++i){
        if(L.r[i].key < L.r[i-dk].key){
            L.r[0] = L.r[i];
            for(j = i - dk; j > 0 && L.r[0].key < L.r[j].key; j -= dk){
                L.r[j+dk] = L.r[j];
            }
            L.r[j+dk] = L.r[0];
        }
    }
}
void ShellSort(SqList &L, int dlta[], int t){
    //shell  
    int k;
    for(k = 0; k < t; ++k){
        dlta[k] = 2^(t-k+1) - 1;
        ShellInsert(L, dlta[k]);
    }
}
int SelectMinKey(SqList L, int i){
    KeyType minkey;
    for(minkey = i; i <= L.length; i++){
        if(L.r[minkey].key > L.r[i].key){
            minkey = i;
        }
        //minkey = ((L.r[i].key < L.r[i+1].key) ? i : (i+1));
    }
    return minkey;
}
void SelectSort(SqList &L){
    //      
    int i, j;
    for(i = 1; i < L.length; ++i){
        j = SelectMinKey(L, i);
        if(i != j){
            L.r[0] = L.r[i];
            L.r[i] = L.r[j];
            L.r[j] = L.r[0];
        }
    }
}
int Partition(SqList &L, int low, int high){
    KeyType pivotkey;
    L.r[0] = L.r[low];
    pivotkey = L.r[low].key;
    while(low < high){
        while(low < high && L.r[high].key >= pivotkey){
            --high;
        }
        L.r[low] = L.r[high];
        while(low < high && L.r[low].key<= pivotkey){
            ++low;
        }
        L.r[high] = L.r[low];
    }
    L.r[low] = L.r[0];
    return low;
}
void Qsort(SqList &L, int low, int high){
    KeyType pivotloc;
    if(low < high){
        pivotloc = Partition(L, low, high);
        Qsort(L, low, pivotloc - 1);
        Qsort(L, pivotloc + 1, high);
    }
}
void QuickSort(SqList &L){
    //    
    Qsort(L, 1, L.length);
}
void HeapAdjust(HeapType &H, int s, int m){
    RedType rc;
    int j;
    rc = H.r[s];
    for(j = 2 * s; j <= m; j *= 2){
        if(j < m && H.r[j].key < H.r[j+1].key){
            ++j;
        }
        if(!(rc.key < H.r[j].key)){
            break;
        }
        H.r[s] = H.r[j]; s = j;
    }
    H.r[s] = rc;
}
void HeapSort(HeapType &H){
    //   
    int i;
    for(i = H.length/2; i > 0; --i){
        HeapAdjust(H, i, H.length);
    }
    for(i = H.length; i > 1; --i){
        H.r[0] = H.r[1];
        H.r[1] = H.r[i];
        H.r[i] = H.r[0];
        HeapAdjust(H, 1, i - 1);
    }
}
int main(void){
    SqList L;
    L.length = 0;
    int t = 4;    //shell    t
    int dlta[t];   //shell    dlta[]
    KeyType key;
    while(1){
        int option;
        printf("       ：
1.       ;
2. shell   
3.       
4.     
5.    
 ：“ctrl+c”    ，“ctrl+z”       EOF
          :");
        scanf("%d", &option);
        printf("        ( EOF  )     ：");
        while(scanf("%d", &key) != EOF){
        SortInput(L, key);
    }
        switch(option){
            case 1 :
                InsertSort(L);
                break;
            case 2 :
                ShellSort(L, dlta, t);
                break;
            case 3 :
                SelectSort(L);
                break;
            case 4 :
                QuickSort(L);
                break;
            case 5 :
                HeapSort(L);
                break;
            default:
                printf("        ，     ！
");
        }
        SortOutput(L);
    }
    return 0;
}