A1098. Insertion or Heap Sort

According to Wikipedia:

Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain.

Heap sort divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element and moving that to the sorted region. it involves the use of a heap data structure rather than a linear-time search to find the maximum.

Now given the initial sequence of integers, together with a sequence which is a result of several iterations of some sorting method, can you tell which sorting method we are using?

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (<=100). Then in the next line, N integers are given as the initial sequence. The last line contains the partially sorted sequence of the N numbers. It is assumed that the target sequence is always ascending. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print in the first line either "Insertion Sort" or "Heap Sort" to indicate the method used to obtain the partial result. Then run this method for one more iteration and output in the second line the resuling sequence. It is guaranteed that the answer is unique for each test case. All the numbers in a line must be separated by a space, and there must be no extra space at the end of the line.

Sample Input 1:

10
3 1 2 8 7 5 9 4 6 0
1 2 3 7 8 5 9 4 6 0

Sample Output 1:

Insertion Sort
1 2 3 5 7 8 9 4 6 0

Sample Input 2:

10
3 1 2 8 7 5 9 4 6 0
6 4 5 1 0 3 2 7 8 9

Sample Output 2:

Heap Sort
5 4 3 1 0 2 6 7 8 9

  1 #include<cstdio>
  2 #include<iostream>
  3 #include<algorithm>
  4 using namespace std;
  5 int num[101], sequ[101], num2[101], N;
  6 void downAdjust(int adj, int N){
  7     int i = adj, j = 2 * i;
  8     while(j <= N){
  9         if(j < N && num[j] < num[j + 1]){
 10             j = j + 1;
 11         }
 12         if(num[i] < num[j]){
 13             swap(num[i], num[j]);
 14             i = j;
 15             j = 2 * i;
 16         }else{
 17             break;
 18         }
 19     }    
 20 }
 21 int heapSort(int N){
 22     int times = N;
 23     for(int i = N / 2; i >= 1; i--){
 24         downAdjust(i, N);
 25     }
 26     int find, prt = 0;
 27     for(int i = 1; i <= times; i++){
 28         find = 1;
 29         swap(num[1], num[N]);
 30         N--;
 31         downAdjust(1, N);
 32         for(int j = 1; j <= times; j++){
 33             if(num[j] != sequ[j]){
 34                 find = 0;
 35                 break;
 36             }
 37         }
 38         if(find == 1){
 39             prt = 1;
 40             continue;
 41         }
 42         if(prt == 1){
 43             printf("Heap Sort
");
 44             for(int k = 1; k <= times; k++){
 45                 if(k == times) printf("%d", num[k]);
 46                 else printf("%d ", num[k]);
 47             }
 48             return 1;
 49         }
 50     }
 51     return 0;
 52 }
 53 
 54 void insertSort(int N){
 55     int find, prt = 0;
 56     for(int i = 1; i < N; i++){
 57         find = 1;
 58         int temp = num2[i + 1];
 59         int j;
 60         for(j = i; j >= 1; j--){
 61             if(temp <= num2[j]){
 62                 num2[j + 1] = num2[j];
 63             }else break;
 64         }
 65         num2[j + 1] = temp;
 66         for(int k = 1; k <= N; k++){
 67             if(num2[k] != sequ[k]){
 68                 find = 0;
 69                 break;
 70             }
 71         }
 72         if(find == 1){
 73             prt = 1;
 74             continue;
 75         }
 76         if(prt == 1){
 77             printf("Insertion Sort
");
 78             for(int k = 1; k <= N; k++){
 79                 if(k == N) printf("%d", num2[k]);
 80                 else printf("%d ", num2[k]);
 81             }
 82             return;
 83         }
 84     }
 85 }
 86 int main(){
 87     scanf("%d", &N);
 88     for(int i = 1; i <= N; i++){
 89         scanf("%d", &num[i]);
 90         num2[i] = num[i];
 91     }
 92     for(int i = 1; i <= N; i++){
 93         scanf("%d", &sequ[i]);
 94     }
 95     int tag = heapSort(N);
 96     if(tag == 0)
 97         insertSort(N);
 98     cin >> N;
 99     return 0;
100 }

View Code

总结：

1、堆排序主要有两部分（大根堆）。

向下调整一个元素A：将A元素与其左右孩子比较，如果它小，则与其中较大的孩子交换。继续追踪这个A元素，在它的调整过的新位置上，如果它比新的孩子节点还要小，则继续交换，直到A大于自己的两个孩子（或者只有一个孩子），或A到达最低端叶节点。

void downAdjust(int adj, int N){  //adj为待调整元素下标，N为数组长度
    int i = adj, j = 2 * i;
    while(j <= N){
        if(j < N && num[j] < num[j + 1]){
            j = j + 1;
        }
        if(num[i] < num[j]){
            swap(num[i], num[j]);
            i = j;
            j = 2 * i;
        }else{
            break;
        }
    }    
}

堆排序：初始化先构造一个大根堆，即从最后一个非叶节点开始（下标N/2）直到根节点，都做一次向下调整，就得到初始的大根堆。若从小到大排序，则将堆顶元素与末端元素交换并将数组长度减一，再对新还上来的堆顶元素进行向下调整，即为一趟堆排序。

int heapSort(int N){
    int times = N;
    for(int i = N / 2; i >= 1; i--){   //构造初始大根堆
        downAdjust(i, N);
    }
    for(int i = 1; i <= times; i++){
        find = 1;
        swap(num[1], num[N]);
        N--;           //排序区间 -1
        downAdjust(1, N);
    }
    return 0;
}

2、prt是一次性的，不要在每一趟排序的循环中把将prt置0，这样就无法输出答案了。

3、堆排序下标最好从1开始。

4、注意堆排序的尾部范围每次-1。