希尔排序，冒泡排序，堆排序等各种排序算法

#include"Sort.h" #include<iostream> using namespace std; int main() { int moving_times = 0, compare_times = 0; int r1[12] = { 1,2,3,4,5,6,7,8,9,10,12,30 }; //正序序列 int r2[13] = { 30,12,10,9,8,7,6,5,4,3,2,1 }; //逆序序列 int r3[12] = { 5,3,7,2,9,10,12,4,30,8,1,6 }; //乱序序列 int R[13]; //用于排序的序列 for (int i = 1; i < 13; i++) R[i] = r1[i - 1]; //R为正序序列 cout << "测试数据为正序时：\n" << endl; InsertSort(R, 12); //直接插入排序 cout << "直接插入排序的排序结果：" << endl; for (int i = 1; i < 13; i++) cout << R[i] << " "; cout << endl; cout << endl; //由于第一组数据是顺序，因此每次排序不用重新初始化R ShellInsert(R, 12); //希尔排序 cout << "希尔排序的排序结果：" << endl; for (int i = 1; i < 13; i++) cout << R[i] << " "; cout << endl; cout << endl; BubbleSort(R, 12); //冒泡排序 cout << "冒泡排序的排序结果：" << endl; for (int i = 1; i < 13; i++) cout << R[i] << " "; cout << endl; cout << endl; Qsort(R, 1, 12, &moving_times, &compare_times); //快速排序 cout << "快速排序的比较次数：" << compare_times << endl; cout << "快速排序的移动次数：" << moving_times << endl; cout << "快速排序的排序结果：" << endl; for (int i = 1; i < 13; i++) cout << R[i] << " "; cout << endl; cout << endl; SelectSort(R, 12); //选择排序 cout << "选择排序的排序结果：" << endl; for (int i = 1; i < 13; i++) cout << R[i] << " "; cout << endl; cout << endl; compare_times = 0; moving_times = 0; MergeSort(R, R, 12, &compare_times, &moving_times); //归并排序 cout << "归并排序的比较次数：" << compare_times << endl; cout << "归并排序的移动次数：" << moving_times << endl; cout << "归并排序的排序结果：" << endl; for (int i = 1; i < 13; i++) cout << R[i] << " "; cout << endl; cout << endl; compare_times = 0; moving_times = 0; BigHeapSort(R, 12, &compare_times, &moving_times); //大根堆排序 cout << "大根堆的比较次数：" << compare_times << endl; cout << "大根堆的移动次数：" << moving_times << endl; cout << "大根堆排序的结果：" << endl; for (int i = 1; i < 13; i++) cout << R[i] << " "; cout << endl; cout << endl; compare_times = 0; moving_times = 0; SmallHeapSort(R, 12, &compare_times, &moving_times); //小根堆排序 cout << "小根堆的比较次数：" << compare_times << endl; cout << "小根堆的移动次数：" << moving_times << endl; cout << "小根堆排序的结果：" << endl; for (int i = 1; i < 13; i++) cout << R[i] << " "; cout << endl; cout << endl; //由于小根堆排序输出的是逆序，因此不需要重新初始化R cout << "测试数据为逆序时：\n" << endl; InsertSort(R, 12); //直接插入排序 cout << "直接插入排序的排序结果：" << endl; for (int i = 1; i < 13; i++) cout << R[i] << " "; cout << endl; cout << endl; for (int i = 1; i < 13; i++) R[i] = r2[i - 1]; ShellInsert(R, 12); //希尔排序 cout << "希尔排序的排序结果：" << endl; for (int i = 1; i < 13; i++) cout << R[i] << " "; cout << endl; cout << endl; for (int i = 1; i < 13; i++) R[i] = r2[i - 1]; BubbleSort(R, 12); //冒泡排序 cout << "冒泡排序的排序结果：" << endl; for (int i = 1; i < 13; i++) cout << R[i] << " "; cout << endl; cout << endl; for (int i = 1; i < 13; i++) R[i] = r2[i - 1]; compare_times = 0; moving_times = 0; Qsort(R, 1, 12, &moving_times, &compare_times); //快速排序 cout << "快速排序的比较次数：" << compare_times << endl; cout << "快速排序的移动次数：" << moving_times << endl; cout << "快速排序的排序结果：" << endl; for (int i = 1; i < 13; i++) cout << R[i] << " "; cout << endl; cout << endl; for (int i = 1; i < 13; i++) R[i] = r2[i - 1]; SelectSort(R, 12); //选择排序 cout << "选择排序的排序结果：" << endl; for (int i = 1; i < 13; i++) cout << R[i] << " "; cout << endl; cout << endl; for (int i = 1; i < 13; i++) R[i] = r2[i - 1]; compare_times = 0; moving_times = 0; MergeSort(R, R, 12, &compare_times, &moving_times); //归并排序 cout << "归并排序的比较次数：" << compare_times << endl; cout << "归并排序的移动次数：" << moving_times << endl; cout << "归并排序的排序结果：" << endl; for (int i = 1; i < 13; i++) cout << R[i] << " "; cout << endl; cout << endl; for (int i = 1; i < 13; i++) R[i] = r2[i - 1]; compare_times = 0; moving_times = 0; BigHeapSort(R, 12, &compare_times, &moving_times); //大根堆排序 cout << "大根堆的比较次数：" << compare_times << endl; cout << "大根堆的移动次数：" << moving_times << endl; cout << "大根堆排序的结果：" << endl; for (int i = 1; i < 13; i++) cout << R[i] << " "; cout << endl; cout << endl; for (int i = 1; i < 13; i++) R[i] = r2[i - 1]; compare_times = 0; moving_times = 0; SmallHeapSort(R, 12, &compare_times, &moving_times); //小根堆排序 cout << "小根堆的比较次数：" << compare_times << endl; cout << "小根堆的移动次数：" << moving_times << endl; cout << "小根堆排序的结果：" << endl; for (int i = 1; i < 13; i++) cout << R[i] << " "; cout << endl; cout << endl; for (int i = 1; i < 13; i++) R[i] = r3[i - 1]; cout << "测试数据为乱序时：\n" << endl; InsertSort(R, 12); //直接插入排序 cout << "直接插入排序的排序结果：" << endl; for (int i = 1; i < 13; i++) cout << R[i] << " "; cout << endl; cout << endl; for (int i = 1; i < 13; i++) R[i] = r3[i - 1]; ShellInsert(R, 12); //希尔排序 cout << "希尔排序的排序结果：" << endl; for (int i = 1; i < 13; i++) cout << R[i] << " "; cout << endl; cout << endl; for (int i = 1; i < 13; i++) R[i] = r3[i - 1]; BubbleSort(R, 12); //冒泡排序 cout << "冒泡排序的排序结果：" << endl; for (int i = 1; i < 13; i++) cout << R[i] << " "; cout << endl; cout << endl; for (int i = 1; i < 13; i++) R[i] = r3[i - 1]; compare_times = 0; moving_times = 0; Qsort(R, 1, 12, &moving_times, &compare_times); //快速排序 cout << "快速排序的比较次数：" << compare_times << endl; cout << "快速排序的移动次数：" << moving_times << endl; cout << "快速排序的排序结果：" << endl; for (int i = 1; i < 13; i++) cout << R[i] << " "; cout << endl; cout << endl; for (int i = 1; i < 13; i++) R[i] = r3[i - 1]; SelectSort(R, 12); //选择排序 cout << "选择排序的排序结果：" << endl; for (int i = 1; i < 13; i++) cout << R[i] << " "; cout << endl; cout << endl; for (int i = 1; i < 13; i++) R[i] = r3[i - 1]; compare_times = 0; moving_times = 0; MergeSort(R, R, 12, &compare_times, &moving_times); //归并排序 cout << "归并排序的比较次数：" << compare_times << endl; cout << "归并排序的移动次数：" << moving_times << endl; cout << "归并排序的排序结果：" << endl; for (int i = 1; i < 13; i++) cout << R[i] << " "; cout << endl; cout << endl; for (int i = 1; i < 13; i++) R[i] = r3[i - 1]; compare_times = 0; moving_times = 0; BigHeapSort(R, 12, &compare_times, &moving_times); //大根堆排序 cout << "大根堆的比较次数：" << compare_times << endl; cout << "大根堆的移动次数：" << moving_times << endl; cout << "大根堆排序的结果：" << endl; for (int i = 1; i < 13; i++) cout << R[i] << " "; cout << endl; cout << endl; for (int i = 1; i < 13; i++) R[i] = r3[i - 1]; compare_times = 0; moving_times = 0; SmallHeapSort(R, 12, &compare_times, &moving_times); //小根堆排序 cout << "小根堆的比较次数：" << compare_times << endl; cout << "小根堆的移动次数：" << moving_times << endl; cout << "小根堆排序的结果：" << endl; for (int i = 1; i < 13; i++) cout << R[i] << " "; cout << endl; cout << endl; system("pause"); return 1; }