合併排序法

實作：CJavaPythonScalaRuby

• C
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX1 10
#define MAX2 10
#define SWAP(x,y) {int t; t = x; x = y; y = t;}

int partition(int[], int, int);
void quickSort(int[], int, int);
void mergeSort(int[], int, int[], int, int[]);

int main(void) {
srand(time(NULL));

int number1[MAX1] = {0};
int number2[MAX1] = {0};
int number3[MAX1+MAX2] = {0};

printf("排序前：");
printf("\nnumber1[]：");
int i;
for(i = 0; i < MAX1; i++) {
number1[i] = rand() % 100;
printf("%d ", number1[i]);
}
printf("\nnumber2[]：");
for(i = 0; i < MAX2; i++) {
number2[i] = rand() % 100;
printf("%d ", number2[i]);
}

// 先排序兩筆資料
quickSort(number1, 0, MAX1-1);
quickSort(number2, 0, MAX2-1);

printf("\n排序後：");
printf("\nnumber1[]：");
for(i = 0; i < MAX1; i++)
printf("%d ", number1[i]);
printf("\nnumber2[]：");
for(i = 0; i < MAX2; i++)
printf("%d ", number2[i]);

// 合併排序
mergeSort(number1, MAX1, number2, MAX2, number3);

printf("\n合併後：");
for(i = 0; i < MAX1+MAX2; i++)
printf("%d ", number3[i]);

printf("\n");

return 0;
}

int partition(int number[], int left, int right) {
int s = number[right];
int i = left - 1;
int j;
for(j = left; j < right; j++) {
if(number[j] <= s) {
i++;
SWAP(number[i], number[j]);
}
}
SWAP(number[i+1], number[right]);
return i+1;
}

void quickSort(int number[], int left, int right) {
if(left < right) {
int q = partition(number, left, right);
quickSort(number, left, q-1);
quickSort(number, q+1, right);
}
}

void mergeSort(int number1[], int M, int number2[],
int N, int number3[]) {
int i = 0, j = 0, k = 0;
while(i < M && j < N) {
if(number1[i] <= number2[j])
number3[k++] = number1[i++];
else
number3[k++] = number2[j++];
}

while(i < M)
number3[k++] = number1[i++];
while(j < N)
number3[k++] = number2[j++];
}

• Java
public class Sort {
// number1、number2 必須排序過
public static int[] merge(int[] number1, int[] number2) {
int[] number3 = new int[number1.length + number2.length];

int i = 0, j = 0, k = 0;
while(i < number1.length && j < number2.length) {
if(number1[i] <= number2[j])
number3[k++] = number1[i++];
else
number3[k++] = number2[j++];
}

while(i < number1.length)
number3[k++] = number1[i++];
while(j < number2.length)
number3[k++] = number2[j++];

return number3;
}
}

• Python
def sort(nb1, nb2):
if len(nb1) == 0: return nb2
elif len(nb2) == 0: return nb1
elif nb1[0] < nb2[0]: return [nb1[0]] + sort(nb1[1:], nb2)
else: return [nb2[0]] + sort(nb1, nb2[1:])

number1 = [4,13,6,6,2,7,2,9,29]
number2 = [4,13,6,6,2,7,2,9,29]
number1.sort()
number2.sort()
print(sort(number1, number2))

• Scala
object Sort {
def merge(nb1: List[Int], nb2: List[Int]): List[Int] =
(nb1, nb2) match {
case (Nil, _) => nb2
case (_, Nil) => nb1
}
}

Sort.merge(List(1,2,3,4,5,6,7), List(1,2,3,4,5,6,7)).foreach(print)

• Ruby
def sort(nb1, nb2)
if nb1.empty?
return nb2
elsif nb2.empty?
return nb1
elsif nb1[0] < nb2[0]
return [nb1[0]] + sort(nb1[1..-1], nb2)
else
return [nb2[0]] + sort(nb1, nb2[1..-1])
end
end