void inssort(int *A, int n, int incr) { for(int i = incr; i < n; i += incr) for(int j = i; (j >= incr) && (A[j] < A[j - incr]); j -= incr) swap(A[j], A[j - incr]); }

这是一个简单的插入排序算法，用于对数组A进行排序。该算法的基本思路是将数组分为已排序和未排序两部分，每次从未排序部分中取出一个元素，在已排序部分中找到合适的位置插入该元素，使得已排序部分依然保持有序。incr参数表示步长，即每次选取未排序部分中的元素时，跳过incr个元素。这样可以提高排序的效率，特别是对于大规模数据比较有用。

相关问题

请将代码中的InsSort、ShellSort 、SelectSort、QKSort四个函数的函数体补充完整。代码如下： //直接插入排序 void InsSort(int r[], int length) /* 对记录数组r做直接插入排序，length为数组中待排序记录的数目*/ { /*添加代码*/ } /* InsSort */ //希尔排序 void ShellSort(int r[], int length, int delt[], int n) /*对记录数组r做希尔排序，length为数组r的长度，delta 为增量数组，n为delta[]的长度 */ { int i; /*添加代码 for(i=0 ; i<=n-1; ++i) */ } //简单选择排序 void SelectSort(int r[], int length) /*对记录数组r做简单选择排序，length为数组的长度*/ { /*添加代码*/ } /* SelectSort */ //快速排序 void QKSort(int r[],int low, int high ) /*对记录数组r[low..high]用快速排序算法进行排序*/ { int pos; if(low<high) { /*添加代码*/ } }

//直接插入排序
void InsSort(int r[], int length)
{
int i, j, temp;
for(i=1; i<length; ++i)
{
temp = r[i];
for(j=i-1; j>=0 && r[j]>temp; --j)
{
r[j+1] = r[j];
}
r[j+1] = temp;
}
}

//希尔排序
void ShellSort(int r[], int length, int delt[], int n)
{
int i, j, k, gap, temp;
for(k=0; k<n; ++k)
{
gap = delt[k];
for(i=gap; i<length; ++i)
{
temp = r[i];
for(j=i-gap; j>=0 && r[j]>temp; j-=gap)
{
r[j+gap] = r[j];
}
r[j+gap] = temp;
}
}
}

//简单选择排序
void SelectSort(int r[], int length)
{
int i, j, min, temp;
for(i=0; i<length-1; ++i)
{
min = i;
for(j=i+1; j<length; ++j)
{
if(r[j] < r[min])
{
min = j;
}
}
if(min != i)
{
temp = r[i];
r[i] = r[min];
r[min] = temp;
}
}
}

//快速排序
void QKSort(int r[], int low, int high)
{
int i = low, j = high, pivot = r[low];
while(i < j)
{
while(i < j && r[j] >= pivot)
{
--j;
}
if(i < j)
{
r[i++] = r[j];
}

while(i < j && r[i] <= pivot)
{
++i;
}
if(i < j)
{
r[j--] = r[i];
}
}
r[i] = pivot;

if(low < i-1)
{
QKSort(r, low, i-1);
}
if(i+1 < high)
{
QKSort(r, i+1, high);
}
}

#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);
    }
}