PTA 7-15 希尔排序

本题目要求读入N个整数，采用希尔排序法进行排序，采用增量序列{5，3，1}，输出完成增量5和增量3后的5子排序和3子排序结果。

输入格式:

输入不超过100的正整数N和N个整数（空格分隔）。

输出格式:

输出两行，第一行为5子排序结果，第二为3子排序结果。数据间用一个空格分隔。

为简便起见，最后一个元素后也有一个空格。

输入样例:

8
8 1 6 5 4 2 3 7

输出样例:

2 1 6 5 4 8 3 7 
2 1 6 3 4 8 5 7 

代码实现：

#include <stdio.h>  
void shellSort(int arr[], int n, int gap) {  for (int i = gap; i < n; i += 1) {  int temp = arr[i];  int j;  for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {  arr[j] = arr[j - gap];  }  arr[j] = temp;  }  
}  
int main() {  int N;  scanf("%d", &N);  int arr[100];  for (int i = 0; i < N; i++) {  scanf("%d", &arr[i]);  }  if (N >= 5) {  shellSort(arr, N, 5);   for (int i = 0; i < N; i++) {  printf("%d ", arr[i]);  }  printf("\n");  } else {  for (int i = 0; i < N; i++) {  printf("%d ", arr[i]);  }  printf("\n");  }   if (N >= 3) {  shellSort(arr, N, 3);  for (int i = 0; i < N; i++) {  printf("%d ", arr[i]);  }  printf("\n");  } else {  }  return 0;  
}

 代码语言为C++