插入类排序算法-直接插入排序、希尔排序

1.直接插入排序

void InsertSort(int k[], int n)
{
    int i, j;
    int temp;
    for (i = 1; i < n; i++) {
        temp = k[i];
        j = i-1;
        
        while (j >= 0 && temp < k[j]) {
            k[j+1] = k[j];
            j--;
        }
        k[j+1] = temp;
    }
}

2.希尔排序

void ShellSort(int k[], int n)
{
    int i,j;
    int temp;
    
    int gap = n;
    
    do {
        gap = gap/3 + 1;
        
        for (i = gap; i < n; i++) {
            temp = k[i];
            j = i - gap;
            
            while (j >= 0 && temp < k[j]) {
                k[j+1] = k[j];
                j = j - gap;
            }
            
            k[j+gap] = temp;
        }
    } while (gap > 1);
    
}