#include <stdio.h> #include <stdlib.h> #define TRUE 1 #define FALSE 0 typedef int KeyType; typedef int OtherType; typedef struct { KeyType key; OtherType other_data; }RecordType; void InsSort(RecordType r[], int length) { int i,j; for (i=2; i<=length; i++) { r[0]=r[i]; j=i-1; while (r[0].key< r[j].key ) { r[j+1]= r[j]; j=j-1; } r[j+1]=r[0]; } } void sift(RecordType r[], int k, int m) { RecordType t; int i,j; int x; int finished; t= r[k]; x=r[k].key; i=k; j=2*i; finished=FALSE; while( j<=m && !finished ) { if (j<m && r[j].key< r[j+1].key ) j=j+1; if ( x>= r[j].key) finished=TRUE; else { r[i] = r[j]; i=j; j=2*i; } } r[i] =t; } void crt_heap(RecordType r[], int length ) { int i,n; n= length; for ( i=n/2; i >= 1; --i) sift(r,i,n); } void HeapSort(RecordType r[],int length) { int i,n; RecordType b; crt_heap(r, length); n= length; for ( i=n ; i>= 2; --i) { b=r[1]; r[1]= r[i]; r[i]=b; sift(r,1,i-1); } } int main() { int i,j; RecordType r[20]; int len; printf("请输入待排序记录的长度:"); scanf("%d",&len); for(i=1;i<=len;i++) { printf("请输入第%d个记录元素:",i); fflush(stdin); scanf("%d",&j); r[i].key = j; } for(i=1;i<=len;i++) printf("%d ",r[i].key); printf("\n"); InsSort(r,len); for(i=1;i<=len;i++) printf("%d ",r[i].key); printf("\n"); HeapSort(r,len); for(i=1;i<=len;i++) printf("%d ",r[i].key); printf("\n"); return 0; }分别补充希尔排序和快速排序算法

补充希尔排序算法：

void ShellSort(RecordType r[], int length) {
    int i, j, gap;
    RecordType temp;
    for (gap = length / 2; gap > 0; gap /= 2) {
        for (i = gap; i < length; i++) {
            temp = r[i];
            for (j = i - gap; j >= 0 && r[j].key > temp.key; j -= gap) {
                r[j + gap] = r[j];
            }
            r[j + gap] = temp;
        }
    }
}

补充快速排序算法：

int Partition(RecordType r[], int low, int high) {
    RecordType pivot = r[low];
    while (low < high) {
        while (low < high && r[high].key >= pivot.key) {
            high--;
        }
        r[low] = r[high];
        while (low < high && r[low].key <= pivot.key) {
            low++;
        }
        r[high] = r[low];
    }
    r[low] = pivot;
    return low;
}

void QuickSort(RecordType r[], int low, int high) {
    if (low < high) {
        int pivotpos = Partition(r, low, high);
        QuickSort(r, low, pivotpos - 1);
        QuickSort(r, pivotpos + 1, high);
    }
}