Question

用请编写递归函数，输出1，2，3，….n的全排列（n小于10），并观察n逐步增大时程序的运行时间。

用请编写递归函数，输出1，2，3，….n的全排列（n小于10），并观察n逐步增大时程序的运行时间。用c语言

Answer 1

#include <stdio.h>
#include <time.h>

void init(int a[], int length);
void p(int a[], int length, int i);
void swap(int a[], int i, int j);
void print(int a[], int length);

int main() {
  int i = 0, length;
  clock_t start, end;
  int a[10];
  double t[10];
  for (i = 0; i < 10; i++) {
    length = i + 1;
    init(a, length);
    start = clock();
    p(a, length, 0);
    printf("\n");
    end = clock();
    t[i] = (double) (end - start) / CLOCKS_PER_SEC;
  }
  printf("分别耗时：\n");
  for (i = 0; i < 10; i++) {
    printf("%f\n", t[i]);
  }
  return 0;
}

void init(int a[], int length) {
  int i = 0;
  for (i = 0; i < length; i++) {
    a[i] = i + 1;
  }
}

void p(int a[], int length, int i) {
  int j = 0;
  if (i == length - 1) {
    print(a, length);
    return;
  }

  p(a, length, i + 1);

  for (j = i + 1; j < length; j++) {
    swap(a, i, j);
    p(a, length, i + 1);
    swap(a, i, j);
  }
}

void swap(int a[], int i, int j) {
  int temp = a[i];
  a[i] = a[j];
  a[j] = temp;
}

void print(int a[], int length) {
  int i = 0;
  for (i = 0; i < length; i++) {
    printf("%d ", a[i]);
  }
  printf("\n");
}