1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<time.h>
4
5 #define MAX1 10
6 #define MAX2 10
7
8
9 #define SWAP(x,y) {int t; t = x; x = y; y = t;}
10
11 int partition(int[], int , int );
12 void quicksort(int[] , int ,int);
13 void mergesort(int[], int, int[], int, int[]);
14
15 int main(void) {
16 int number1[MAX1] = {0};
17 int number2[MAX1] = {0};
18 int number3[MAX1+MAX2] = {0};
19 int i;
20 srand(time(NULL));
21 printf("排序前：");
22 printf("\nnumber1[]：");
23 for(i = 0; i < MAX1; i++) {
24 number1[i] = rand() % 100;
25 printf("%d ", number1[i]);
26 }
27 printf("\n");
28
29 printf("\nnumber2[]：");
30 for(i = 0; i < MAX2; i++) {
31 number2[i] = rand() % 100;
32 printf("%d ", number2[i]);
33 }
34
35 printf("\n=====================================\n");
36
37 // 先排序兩筆資料
38 quicksort(number1, 0, MAX1-1);
39 quicksort(number2, 0, MAX2-1);
40 printf("\n排序后：");
41 printf("\nnumber1[]：");
42 for(i = 0; i < MAX1; i++) {
43 //number1[i] = rand() % 100;
44 printf("%d ", number1[i]);
45 }
46 printf("\n");
47 printf("\nnumber2[]：");
48 for(i = 0; i < MAX2; i++) {
49 //number2[i] = rand() % 100;
50 printf("%d ", number2[i]);
51 }
52 mergesort(number1, MAX1, number2, MAX2, number3);
53 printf("\n合併後：");
54 for(i = 0; i < MAX1+MAX2; i++)
55 printf("%d ", number3[i]);
56 printf("\n");
57
58 return 0;
59 }
60
61 int partition(int number[], int left, int right) {
62 int i, j, s;
63 s = number[right];
64 i = left - 1;
65 for(j = left; j < right; j++) {
66 if(number[j] <= s) {
67 i++;
68 SWAP(number[i], number[j]);
69 }
70 }
71 SWAP(number[i+1], number[right]);
72 return i+1;
73 }
74
75
76 void quicksort(int number[], int left, int right) {
77 int q;
78 if(left < right) {
79 q = partition(number, left, right);
80 quicksort(number, left, q-1);
81 quicksort(number, q+1, right);
82 }
83 }
84
85
86 //合并排序
87 void mergesort(int number1[], int M, int number2[],
88 int N, int number3[]) {
89 int i = 0, j = 0, k = 0;
90
91 while(i < M && j <N){
92 if(number1[i] <= number2[j]){
93 number3[k++] = number1[i++];
94 }
95 else{
96 number3[k++] = number2[j++];
97 }
98 }
99
100 while(i < M){
101 number3[k++] = number1[i++];
102 }
103 while(j < N){
104 number3[k++] = number2[j++];
105 }
106 }
107
108
109