目錄😋

任務描述

測試說明

我的通關代碼:

測試結果：

---

任務描述

本關任務：實現二路歸并算法。

測試說明

平臺會對你編寫的代碼進行測試：

測試輸入示例：
11
18 2 20 34 12 32 6 16 5 8 1?
(說明：第一行是元素個數，第二行是待排序的原始關鍵字數據。）

輸出示例：
排序前:18 2 20 34 12 32 6 16 5 8 1?
第1趟歸并:2 18 20 34 12 32 6 16 5 8 1?
第2趟歸并:2 18 20 34 6 12 16 32 1 5 8?
第3趟歸并:2 6 12 16 18 20 32 34 1 5 8?
第4趟歸并:1 2 5 6 8 12 16 18 20 32 34?
排序后:1 2 5 6 8 12 16 18 20 32 34?

開始你的任務吧，祝你成功！

---

我的通關代碼:

#include <malloc.h>
#include <stdio.h>#define MAXL 100     //最大長度
typedef int KeyType; //定義關鍵字類型為int
typedef char InfoType;typedef struct {KeyType key;   //關鍵字項InfoType data; //其他數據項，類型為InfoType
} RecType;       //查找元素的類型int count = 1; //全局變量，記錄第幾趟歸并void CreateList(RecType R[], KeyType keys[], int n) //創建順序表
{for (int i = 0; i < n; i++) // R[0..n-1]存放排序記錄R[i].key = keys[i];
}
void DispList(RecType R[], int n) //輸出順序表
{for (int i = 0; i < n; i++)printf("%d ", R[i].key);printf("\n");
}//一次歸并：將兩個有序表R[low..mid]和R[mid+1..high]歸并為一個有序表R[low..high]中
void Merge(RecType R[], int low, int mid, int high) {/********** Begin *********/RecType *R1 = (RecType *)malloc((high - low + 1) * sizeof(RecType));int i = low, j = mid + 1, k = 0;while (i <= mid && j <= high) {if (R[i].key <= R[j].key)R1[k++] = R[i++];elseR1[k++] = R[j++];}while (i <= mid)R1[k++] = R[i++];while (j <= high)R1[k++] = R[j++];for (k = 0, i = low; i <= high; i++, k++)R[i] = R1[k];free(R1);/********** End **********/
}void MergePass(RecType R[], int length, int n) //實現一趟歸并
{/********** Begin *********/int i;for (i = 0; i + 2 * length - 1 < n; i += 2 * length)Merge(R, i, i + length - 1, i + 2 * length - 1);if (i + length - 1 < n)Merge(R, i, i + length - 1, n - 1);/********** End **********/
}void MergeSort(RecType R[], int n) //二路歸并排序算法
{/********** Begin *********/int length = 1;printf("排序前:");DispList(R, n);while (length < n) {MergePass(R, length, n);printf("第%d趟歸并:", count++);DispList(R, n);length *= 2;}printf("排序后:");DispList(R, n);/********** End **********/
}int main() {/********** Begin *********/int n;scanf("%d", &n);KeyType keys[MAXL];RecType R[MAXL];for (int i = 0; i < n; i++)scanf("%d", &keys[i]);CreateList(R, keys, n);MergeSort(R, n);/********** End **********/return 0;
}

測試結果：