前言
一種將無序數(shù)組進(jìn)行排序的方法。
歸并排序，相關(guān)定義可以參考wiki：
https://zh.wikipedia.org/wiki/%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F
主要思想有2：
- 有序數(shù)組派哲。在插入排序中也有此思想
- 合并兩兩有序數(shù)組蹭睡，通過引入額外的臨時數(shù)組實現(xiàn)状您。
本文代碼基本未優(yōu)化，是一種原始邏輯的體現(xiàn)捐韩。
環(huán)境
編輯器：vs2019
文件：.c類型
正文
代碼參考：
#include <stdio.h>
// 歸并排序，主要思想：合并兩個有序數(shù)組鹃锈，通過引入額外的臨時數(shù)組實現(xiàn)荤胁。
// 遞歸歸并排序，每一次遞歸屎债，改變一次有序數(shù)組長度仅政。
// 普通歸并排序垢油，從小到大
void merge_sort_normal(int source_array[], int source_array_length)
{
int start; // 兩兩分組的總起點(diǎn)索引
int* b = (int*)malloc(source_array_length * sizeof(int)); // 引入臨時數(shù)組， 臨時數(shù)組存放每次排序后的結(jié)果已旧。
// 分組, 每組元素數(shù)量：1, 2, 4, 8 ...
for (int gap = 1; gap < source_array_length; gap += gap)
{
// 合并兩兩分組
for (start = 0; start < source_array_length; start += gap * 2)
{
// 臨時數(shù)組的索引
int b_index = start;
// 左邊數(shù)組的起點(diǎn)索引
int start_left = start;
// 左邊數(shù)組的結(jié)束索引
int end_left = start_left + gap - 1;
// 右邊數(shù)組的起點(diǎn)索引
int start_right = start + gap;
// 右邊數(shù)組的結(jié)束索引
int end_right = start_right + gap - 1;
// 1. 當(dāng)左邊數(shù)組不滿時,或沒有右邊數(shù)組時
if (end_left >= source_array_length - 1)
{
for (; b_index < source_array_length; b_index++)
{
b[b_index] = source_array[b_index];
}
break;
}
// 2. 當(dāng)右邊數(shù)組不滿時
if (end_right > source_array_length - 1)
{
end_right = source_array_length - 1;
}
// 3. 開始合并兩數(shù)組
while (start_left <= end_left && start_right <= end_right)
{
if (source_array[start_right] > source_array[start_left])
{
b[b_index] = source_array[start_left];
b_index++;
start_left++;
}
else
{
b[b_index] = source_array[start_right];
b_index++;
start_right++;
}
}
// 4. 經(jīng)過【3】步驟的合并授霸，存在某個數(shù)組沒有完全插入臨時數(shù)組的情況
// 當(dāng)左數(shù)組未插完
while (start_left <= end_left)
{
b[b_index] = source_array[start_left];
b_index++;
start_left++;
}
// 當(dāng)右數(shù)組未插完
while (start_right <= end_right)
{
b[b_index] = source_array[start_right];
b_index++;
start_right++;
}
}
// 每次兩兩分組合并后， 都需要將臨時數(shù)組的值賦值回原數(shù)組蒸走。
if (source_array != b)
{
for (int i = 0; i < source_array_length; i++)
{
source_array[i] = b[i];
}
}
}
}
// 遞歸歸并排序狰右，從小到大
// 其中額外引入gap，初始值設(shè)為1
void merge_sort_recursive(int source_array[], int source_array_length, int gap)
{
int start;
int* b = (int*)malloc(source_array_length * sizeof(int));
for (start = 0; start < source_array_length; start += gap * 2)
{
int b_index = start;
int start_left = start;
int end_left = start_left + gap - 1;
int start_right = start + gap;
int end_right = start_right + gap - 1;
if (end_left >= source_array_length - 1)
{
for (; b_index < source_array_length; b_index++)
{
b[b_index] = source_array[b_index];
}
break;
}
if (end_right > source_array_length - 1)
{
end_right = source_array_length - 1;
}
while (start_left <= end_left && start_right <= end_right)
{
if (source_array[start_right] > source_array[start_left])
{
b[b_index] = source_array[start_left];
b_index++;
start_left++;
}
else
{
b[b_index] = source_array[start_right];
b_index++;
start_right++;
}
}
while (start_left <= end_left)
{
b[b_index] = source_array[start_left];
b_index++;
start_left++;
}
while (start_right <= end_right)
{
b[b_index] = source_array[start_right];
b_index++;
start_right++;
}
}
if (source_array != b)
{
for (int i = 0; i < source_array_length; i++)
{
source_array[i] = b[i];
}
}
gap += gap;
if (gap >= source_array_length)
{
return 0;
}
merge_sort_recursive(source_array, source_array_length, gap);
}
int* upset_array(int source_list[], int source_list_length)
{
for (int i = 0; i < source_list_length; i++)
{
int rand_index = rand() % source_list_length;
int tmp_value = source_list[i];
source_list[i] = source_list[rand_index];
source_list[rand_index] = tmp_value;
}
return source_list;
}
int main()
{
// 生成隨機(jī)測試列表
int test_list[20];
int test_list_length = sizeof(test_list) / sizeof(int);
printf("測試列表： \n");
for (int i = 0; i < test_list_length; i++)
{
test_list[i] = rand() % 100;
printf("%d ", test_list[i]);
}
printf("\n");
// 普通歸并排序
merge_sort_normal(test_list, test_list_length);
printf("普通歸并排序結(jié)果： \n");
for (int i = 0; i < test_list_length; i++)
{
printf("%d ", test_list[i]);
}
printf("\n");
// 打亂數(shù)組
upset_array(test_list, test_list_length);
printf("打亂測試列表： \n");
for (int i = 0; i < test_list_length; i++)
{
printf("%d ", test_list[i]);
}
printf("\n");
// 遞歸歸并排序
merge_sort_recursive(test_list, test_list_length, 1);
printf("遞歸歸并排序結(jié)果： \n");
for (int i = 0; i < test_list_length; i++)
{
printf("%d ", test_list[i]);
}
printf("\n");
return 0;
}
執(zhí)行結(jié)果參考：
image.png
