插入排序
InsertionSort.h
#ifndef __INSERTIONSORT_H_FE
#define __INSERTIONSORT_H_FE
// 插入排序
void insertion_sort(int *a, int len);
#endif
InsertionSort.cpp
void insert_item(int *a, int max_index, int item);
// 插入排序
void insertion_sort(int *a, int len)
...{
for (int i = 0; i < len; i++) ...{
insert_item(a, i, a[i]);
}
}
// 在已排序数组中插入一个新的元素
// 以不降顺序排序
void insert_item(int *a, int max_index, int item)
...{
int i = 0;
// 将大于即将插入的数据的元素位置往后移一位
for (i = max_index - 1; (i >= 0) && (item < a[i]); i--) ...{
a[i + 1] = a[i];
}
// 在正确的位置插入元素
a[i + 1] = item;
}
归并排序
MergeSort.h
#ifndef __MERGESORT_H_FE
#define __MERGESORT_H_FE
// 归并排序
void merge_sort(int *a, int low, int high);
// 归并插入排序
void merge_insertion_sort(int *a, int low, int high);
// 使用静态链表的归并排序
void merge_sort_link(int *a, int low, int high, int *link, int &head);
#endif
MergeSort.cpp
#include
#include
#include "InsertionSort.h"
void merge(int *a, int low, int middle, int high);
void merge_link(int *a, int *link, int &head, int h1, int h2);
// 归并排序
void merge_sort(int *a, int low, int high)
...{
int middle = 0;
// 将待排序数组分成两组，分别进行排序后再进行合成
if (low < high) ...{
// 分组策略为从数组中间分开
middle = (int) ((low + high) / 2);
// 先对前半部分进行递归地分组排序
merge_sort(a, low, middle);
// 对后半部分进行递归分组排序
merge_sort(a, middle + 1, high);
// 将之前已排序的前后两组合成最终排序的数组
merge(a, low, middle, high);
}
}
// 归并插入排序
// 与直接的归并排序不同的是，在数组规模较小的时候，直接使用插入排序，减小递归的开销
void merge_insertion_sort(int *a, int low, int high)
...{
int middle = 0;
// 当数组规模小到一定规模（16）的时候使用插入排序，避免过多的递归调用
if ((high - low + 1) > 16) ...{
// 分组策略为从数组中间分开
middle = (int) ((low + high) / 2);
// 先对前半部分进行递归地分组排序
merge_sort(a, low, middle);
// 对后半部分进行递归分组排序
merge_sort(a, middle + 1, high);
// 将之前已排序的前后两组合成最终排序的数组
merge(a, low, middle, high);
}
else ...{
// 对小数组使用插入排序
insertion_sort((a + low), (high - low + 1));
}
}
// 对前后两部分已排序数组进行合成
void merge(int *a, int low, int middle, int high)
...{
int *b = NULL;
// a1指向a中前半部分已排序数组的开头
// a2指向a中后半部分已排序数组的开头
// bp指向临时数组b的开头
int a1 = low, a2 = middle + 1, bp = 0;
// 为临时数组b申请空间，大小为 high - low + 1
if ((b = new int[high - low + 1]) == NULL) ...{
printf("memory out.");
exit(1);
}
// 当前后两个分组都还有元素的时候，按照他们的大小顺序放入b中
// 直到某一分组没有元素为止
while ((a1 <= middle) && (a2 <= high)) ...{
// 如果前半部分的头元素小于后半部分的头元素
// 则将前半部分的头元素放入b中，位置变量递增
if (a[a1] <= a[a2]) ...{
b[bp++] = a[a1++];
}
// 否则将后半部分的头元素放入b中，位置变量递增
else ...{
b[bp++] = a[a2++];
}
}
// 如果前半部分的元素已经取完了，则可能后半部分还有元素剩余
if (a1 > middle) ...{
// 将后半部分剩余的元素一次放入b中
while (a2 <= high) ...{
b[bp++] = a[a2++];
}
}
// 如果后半部分的元素取完了，则可能前半部分还有元素剩余
else if (a2 > high) ...{
// 将前半部分剩余的元素一次放入b中
while (a1 <= middle) ...{
b[bp++] = a[a1++];
}
}
// 将临时数组b中的元素拷贝回a中相应的位置中
for (bp = 0; bp < high - low + 1; bp++) ...{
a[low + bp] = b[bp];
}
// 释放临时数组b
if (b != NULL) ...{
delete[] b;
}
}
// 使用静态链表的归并排序
// 最终修改head的值，使其指向静态链表指示的数组的开始位置
void merge_sort_link(int *a, int low, int high, int *link, int &head)
...{
int middle = 0;
// h1和h2是子数组的静态链表的头
// 当递归调用返回的时候，他们将正确的指向部分数组的静态链表的头
int h1 = 0, h2 = 0;
// 两路归并
if (low < high) ...{
// 从数组中间将数组分成两部分，分别排序后归并
middle = (int) ((low + high) / 2);
// 递归调用归并函数，得到前半子数组的静态链表头，并正确填写前半子数组对应的link中的值
merge_sort_link(a, low, middle, link, h1);
// 递归调用归并函数，得到后半子数组的静态链表头，并正确填写后半子数组对应的link中的值
merge_sort_link(a, middle + 1, high, link, h2);
// 将两部分排好序的数组的静态链表合并，并正确返回合并后的大数组对应的静态链表的头
merge_link(a, link, head, h1, h2);
}
else ...{
// 当子数组只有一个元素的时候，静态链表的头指向该元素本身
head = low;
}
}
// 合并两个子数组的静态链表（修改静态链表的值），并返回合并后的大数组对应的静态链表的头
void merge_link(int *a, int *link, int &head, int h1, int h2)
...{
// 其中，i和j分别指向两个子数组的静态链表的头
// 并不断地往后移，直到有一个头指向子数组的末尾
// k为当前静态链表link中写的位置，对应于数组中当前取下来的最后一个元素的索引
int i = h1, j = h2, k = 0;
// 首先获取合并后的大数组的第一个元素的索引，并让静态链表的头指向该元素
if (a[i] < a[j]) ...{
head = i;
k = i;
i = link[i];
}
else ...{
head = j;
k = j;
j = link[j];
}
// 不断根据两个子数组的静态链表的指示，从两个子数组中按大小顺序摘下元素
// 直到有一个子数组摘空为止
while ((i != -1) && (j != -1)) ...{
if (a[i] < a[j]) ...{
// 使该元素的前驱元素的对应的静态链表单元指向该元素
link[k] = i;
// 下一个应该更新的静态链表单元就是目前摘下的这个元素对应的单元
k = i;
// 子数组的头元素向后移，移向子数组中的下一个元素
// 静态链表中与该元素索引对应的单元中存储的是该元素的后继元素的索引
i = link[i];
}
else ...{
link[k] = j;
k = j;
j = link[j];
}
}
// 两个子数组有一个摘空后
// 将另一个子数组剩余的元素的静态链表直接挂接在摘得的最后一个元素对应的静态链表单元中
if (i == -1) ...{
link[k] = j;
}
else ...{
link[k] = i;
}
}
快速排序
QuickSort.h
#ifndef __QUICKSORT_H_FE
#define __QUICKSORT_H_FE
// 快速排序
void quick_sort(int *a, int left, int right);
// 快速插入排序
void quick_insertion_sort(int *a, int left, int right);
#endif
QuickSort.cpp
#include "InsertionSort.h"
int sel_pivot(int *a, int left, int right);
void swap(int *a, int i, int j);
void partition(int *a, int left, int &pivot_pos);
// 快速排序
void quick_sort(int *a, int left, int right)
...{
// 中枢元的位置
int pivot_pos = 0;
if (left < right) ...{
// 从待排序的数组中选取中枢元的位置
pivot_pos = sel_pivot(a, left, right);
// 将中枢元与数组末元素互换,也就是将中枢元放到数组末尾
if (pivot_pos != right) ...{
swap(a, pivot_pos, right);
pivot_pos = right;
}
// 根据选定的中枢元,对数组进行partition，并返回partition之后的中枢元的位置
partition(a, left, pivot_pos);
// 对中枢元前面部分的数组递归的进行快排
quick_sort(a, left, pivot_pos - 1);
// 对中枢元后面部分的数组递归的进行快排
quick_sort(a, pivot_pos + 1, right);
}
}
// 快速插入排序
// 与直接的快排不同的是，在数组规模较小的时候，直接使用插入排序，减少递归的开销
void quick_insertion_sort(int *a, int left, int right)
...{
int pivot_pos = 0;
// 当数组规模小于等于10的时候使用插入排序
if ((right - left + 1) <= 10) ...{
insertion_sort((a + left), (right - left + 1));
}
else ...{
pivot_pos = sel_pivot(a, left, right);
if (pivot_pos != right) ...{
swap(a, pivot_pos, right);
pivot_pos = right;
}
partition(a, left, pivot_pos);
quick_insertion_sort(a, left, pivot_pos - 1);
quick_insertion_sort(a, pivot_pos + 1, right);
}
}
// 从待排序数组中选取中枢元，并返回中枢元在原数组中的位置
// 选取的规则是，从数组的头、尾以及中间元素之间，选择它们的中值
int sel_pivot(int *a, int left, int right)
...{
int middle = (int)((left + right) / 2);
int temp[3] = ...{a[left], a[middle], a[right]};
insertion_sort(temp, 3);
if (temp[1] == a[left]) ...{
return left;
}
else if (temp[1] == a[middle]) ...{
return middle;
}
else ...{
return right;
}
}
// 交换数组中的两个元素
void swap(int *a, int i, int j)
...{
// 当两个元素是同一个元素时，不必也不能使用异或的方式进行交换
// 不然元素的值将变成零
if (i != j) ...{
a[i] ^= a[j];
a[j] ^= a[i];
a[i] ^= a[j];
}
}
// partition算法
// 根据选取的中枢元的值，将数组分成两组
// 中枢元前面的子数组元素的值都小于等于中枢元
// 中枢元后面的子数组元素的值都大于等于中枢元
void partition(int *a, int left, int &pivot_pos)
...{
int i = left, j = pivot_pos - 1;
int pivot_val = a[pivot_pos];
do ...{
// i从左往右查，直到遇到一个大于等于中枢元的元素停止
while (a[i] < pivot_val) ...{
i++;
}
// j从右往左查，直到遇到一个小于等于中枢元的元素停止
while (a[j] > pivot_val) ...{
j--;
}
// 将i指向的大于等于中枢元的元素与j指向的小于等于中枢元的元素交换位置
// 因为原来i指向的元素在左边，而j指向的元素在右边
// 通过交换，将所有小于等于中枢元的元素放到数组左边，将所有大于等于中枢元的元素放到数组右边
// 交换的前提是，i指针还在j指针的左边，也就是i if (i < j) ...{
swap(a, i, j);
i++;
j--;
}
} while (i < j); // 当i在j的右边的时候循环结束，此时，i指向数组中大于等于中枢元的第一个元素
// 将中枢元与数组中第一个大于等于中枢元的元素交换
// 使得中枢元位于数组中间
// 中枢元左边的所有数组元素都小于等于中枢元
// 中枢元右边的所有数组元素都大于等于中枢元
swap(a, i, pivot_pos);
// 更新中枢元的位置指针
pivot_pos = i;
}
用一个测试程序来测试归并排序，使用静态链表的归并排序，快速排序，以及经过改进快速排序的效率。
#include
#include
#include
#include
#include "MergeSort.h"
#include "QuickSort.h"
// 相同待排序随机数组的组数
// 几组相同的待排序随机数组用于测试不同排序算法之间的效率差别
#define ARRAY_GROUP_NUM 5
#define ROUND_NUM 6
void print_array(int *a, int len);
void print_array_link(int *a, int *link, int head, int endflag);
int main(void)
...{
// 指针数组用于指向几组相同数据的待排序数组
int *arr[ARRAY_GROUP_NUM] = ...{ NULL };
// 每组数据的长度
int len = 0;
// 用于计时，单位毫秒
DWORD tick_count = 0;
// 数组的静态链表，用于使用静态链表的归并排序
int *arr_link = NULL;
// 静态链表的头位置
int arr_link_head = 0;
srand((unsigned int)time(NULL));
len = 1000;
// 一共进行ROUND_NUM轮测试，每一轮数组的规模都增加五倍，初始规模为1000
for (int round = 0; round < ROUND_NUM; round++) ...{
// 为每组数组动态地分配空间
for (int i = 0; i < ARRAY_GROUP_NUM; i++) ...{
if ((arr[i] = new int[len]) == NULL) ...{
printf("Memory out. ");
return 1;
}
}
// 为静态链表分配空间，大小与数组元素相同
if ((arr_link = new int[len]) == NULL) ...{
printf("Memory out. ");
return 1;
}
// 为每组数组赋予相同的随机元素值，用于排序
for (int i = 0; i < len; i++) ...{
for (int j = 0; j < ARRAY_GROUP_NUM; j++) ...{
arr[j][i] = rand();
}
// 初始化静态链表，-1表示指向空（因为数组元素从零开始，所以不能用零来指向空）
arr_link[i] = -1;
}
// 以下是对各种排序算法的效率比较
// 首先是普通的归并排序
printf(" Sorting %d numbers with merge_sort... ", len);
tick_count = ::GetTickCount();
merge_sort(arr[0], 0, len - 1);
tick_count = ::GetTickCount() - tick_count;
printf("Total time: %d ms ", tick_count);
// 当数组小于一定规模时使用插入排序的归并排序
printf("Sorting %d numbers with merge_insertion_sort... ", len);
tick_count = ::GetTickCount();
merge_insertion_sort(arr[1], 0, len - 1);
tick_count = ::GetTickCount() - tick_count;
printf("Total time: %d ms ", tick_count);
// 使用静态链表的归并排序
printf("Sorting %d numbers with merge_sort_link... ", len);
tick_count = ::GetTickCount();
merge_sort_link(arr[2], 0, len - 1, arr_link, arr_link_head);
tick_count = ::GetTickCount() - tick_count;
printf("Total time: %d ms ", tick_count);
// 普通的快速排序
printf("Sorting %d numbers with quick_sort... ", len);
tick_count = ::GetTickCount();
quick_sort(arr[3], 0, len - 1);
tick_count = ::GetTickCount() - tick_count;
printf("Total time: %d ms ", tick_count);
// 当数组小于一定规模时使用插入排序的快速排序
printf("Sorting %d numbers with quick_insertion_sort... ", len);
tick_count = ::GetTickCount();
quick_insertion_sort(arr[4], 0, len - 1);
tick_count = ::GetTickCount() - tick_count;
printf("Total time: %d ms ", tick_count);
// 释放申请的临时存储数组的空间
for (int i = 0; i < ARRAY_GROUP_NUM; i++) ...{
if (arr[i] != NULL) ...{
delete[] arr[i];
}
}
// 释放申请的临时静态链表的空间
if (arr_link != NULL) ...{
delete[] arr_link;
}
// 每一轮数组的规模就增加五倍
len *= 5;
}
system("pause");
return 0;
}
// 打印数组的值
void print_array(int *a, int len)
...{
for (int i = 0; i < len; i++) ...{
printf("%d ", a[i]);
}
printf(" ");
}
// 根据静态链表的指向的顺序打印数组
void print_array_link(int *a, int *link, int head, int endflag)
...{
int i = head;
while (i != endflag) ...{
printf("%d ", a[i]);
i = link[i];
}
printf(" ");
}
