?? 二路歸并排序.c
字號:
#include "datastru.h"
#include <stdio.h>
void merge(RECNODE *r, int low, int m, int high)
{/*兩相鄰的有序表(一個從low到m;另一個從m+1到high)合并為一個有序表(從low到high)*/
RECNODE r1[MAXSIZE]; /*合并時用的緩沖向量*/
int i, j, k;
i = low;
j = m + 1;
k = 0;
while(i <= m && j <= high) /*兩相鄰的有序表合并*/
if(r[i].key <= r[j].key)
{r1[k] = r[i]; i++; k++;}
else
{r1[k] = r[j]; j++; k++;}
while(i <= m) /*有序表剩余部分處理*/
{r1[k] = r[i]; i++; k++;}
while(j <= high) /*有序表剩余部分處理*/
{r1[k] = r[j]; j++; k++;}
for(i = low, k = 0; i <= high; i++, k++)/*緩沖向量r1復制到原來的r中*/
r[i] = r1[k];
}
void merge_one(RECNODE *r, int lenth, int n)
{/*二路歸并中的"一趟歸并"算法*/
int i = 0;
while(i + 2 * lenth - 1 < n)
{merge(r, i, i + lenth - 1, i + 2 * lenth - 1);/*兩子序列長度相等的*/
i = i + 2 * lenth;} /*情況下調用merge*/
if(i + lenth - 1 < n - 1)
merge(r, i, i + lenth - 1, n - 1); /*序列中的余留部分處理*/
}
void mergesort(RECNODE *r, int n)
{/*二路歸并排序算法*/
int lenth = 1; /*有序子序列長度初始值 = 1*/
while(lenth < n)
{merge_one(r, lenth, n); /*調用"一趟歸并"的算法*/
lenth = 2 * lenth;} /*有序子序列長度加倍*/
}
main( )
{ RECNODE a[MAXSIZE];
int i, j, k, len;
printf("\n\n輸入待排序數據(整數,以空格隔開,0 結束) : "); k = 0; scanf("%d",&j);
while(j != 0) { k++; a[k-1].key = j; scanf("%d",&j); }
len = k;
printf("\n排序前 : ");
for (i = 0; i < len; i++) printf(" %d",a[i].key);
printf("\n");
mergesort (a,len);
printf("\n");
printf("\n\n排序后 : ");
for (i = 0; i < len; i++) printf(" %d",a[i].key);
printf("\n");
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -