[C/C++ 演算法]- 合併排序法

[C/C++ 演算法]- 合併排序法

[C/C++ 演算法]- 合併排序法

剛才找資料時發現一個C/C++的教學網站,趕快發揮(C/P)的長才將它備份來,有需要的同好,歡迎來(C/P)一下^^。

拷貝來源:
http://openhome.cc/Gossip/AlgorithmGossip/
http://openhome.cc/Gossip/AlgorithmGossip/MergeSort.htm

#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++];
} 

 

 

One thought on “[C/C++ 演算法]- 合併排序法

  1. 排序法的性能評估指標:

    穩定:如果a原本在b前面,而a=b,排序之後a仍然在b的前面。

    不穩定:如果a原本在b的前面,而a=b,排序之後a可能會出現在b的後面。

    時間複雜度:對排序數據的總的操作次數。反映當n變化時,操作次數呈現什麼規律。

    空間複雜度:是指算法在計算機內執行時所需存儲空間的度量,它也是數據規模n的函數。

    PS. 個人認為目前最為推薦 [ 效率(速度)&額外記憶體使用量&穩定度 ] 的排序法 – 归并排序/歸併排序/合併排序 (Merge Sort)

發表迴響

你的電子郵件位址並不會被公開。 必要欄位標記為 *