数据结构排序的基本操作的实现

一、实验目的

(1)掌握各种排序算法的基本思想；
(2)掌握各种排序算法的实现方法。

二、实验内容

对一组数据进行排序，可选择直接插入排序、折半插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序和2-路归并排序算法实现。
要求:设计菜单，根据菜单提示进行操作。

三、算法代码

#include <iostream>
#include <iomanip>
#include <stdlib.h>
#include <time.h>
#include <cmath>
using namespace std;
#define MAXSIZE 10
typedef int KeyType;
typedef int InfoType;
typedef struct {KeyType key;InfoType otherinfo;
} RedType;
typedef struct {RedType r[MAXSIZE + 1];int length;
} SqList;//打印
void print(SqList &t) {for (int i = 1; i <= t.length; i++) {if ((i - 1) % 10 == 0)cout << endl;cout <<" "<< t.r[i].key;}cout << endl;
}//产生随机数
void producerandom(SqList &t) {srand(time(NULL));for (int i = 1; i <= MAXSIZE; i++)t.r[i].key = rand() % 100;t.length = MAXSIZE;print(t);
}//直接插入排序
void InsertSort(SqList &t) {for (int i = 2; i <= t.length; i++) {if (t.r[i].key < t.r[i - 1].key) {int j;t.r[0] = t.r[i];t.r[i] = t.r[i - 1];for (j = i - 2; t.r[j].key > t.r[0].key; j--) {t.r[j + 1] = t.r[j];}t.r[j + 1] = t.r[0];}}
}//折半插入排序
void BInsertSort(SqList &t) {for (int i = 2; i <= t.length; i++) {int low, high, m;t.r[0] = t.r[i];low = 1;high = i - 1;while (low <= high) {m = (low + high) / 2;if (t.r[0].key < t.r[m].key)high = m - 1;elselow = m + 1;}for (int j = i; j > high + 1; j--) {t.r[j] = t.r[j - 1];}t.r[high + 1] = t.r[0];}
}//希尔排序
void ShellInsert(SqList &t, int dk) {for (int i = dk + 1; i <= t.length; i++) {if (t.r[i].key < t.r[i - dk].key) {int j;t.r[0] = t.r[i];t.r[i] = t.r[i - dk];for (j = i - 2 * dk; j > 0 && (t.r[j].key > t.r[0].key); j = j - dk)t.r[j + dk] = t.r[j];t.r[j + dk] = t.r[0];}}
}
void ShellSort(SqList &t) {int temp = t.length, i, j;int *const dt = (int *)malloc(sizeof(int) * t.length);for (i = 0; temp != 0; i++) {//增量序列参考某文章,对于length<10000时的较高效率temp = temp / 3;dt[i] = temp + 1;}for (int j = 0; j <= i - 1; j++)ShellInsert(t, dt[j]);
}//冒泡排序
void BubbleSort(SqList &t) {int m, j, flag = 1;m = t.length - 1;while (m > 0 && flag) {flag = 0;for (j = 1; j <= m; j++) {if (t.r[j].key > t.r[j + 1].key) {flag = 1;t.r[0] = t.r[j];t.r[j] = t.r[j + 1];t.r[j + 1] = t.r[0];}}m--;}
}//快速排序
void QuickSort(SqList &t, int low, int high) {if (low < high) {int left = low, right = high;t.r[0] = t.r[low];while (low < high) {while (low < high && t.r[high].key >= t.r[0].key)high--;t.r[low] = t.r[high];while (low < high && t.r[low].key <= t.r[0].key)low++;t.r[high] = t.r[low];}t.r[low] = t.r[0];QuickSort(t, left, low - 1);QuickSort(t, low + 1, right);}
}
//简单选择排序
void SelectSort(SqList &t) {int min;for (int i = 1; i < t.length; i++) {min = i;for (int j = i + 1; j <= t.length; j++) {if (t.r[j].key < t.r[min].key)min = j;}if (min != i) {t.r[0] = t.r[min];t.r[min] = t.r[i];t.r[i] = t.r[0];}}
}
//筛选堆
void HeapAdjust(SqList &t, int s, int m) {t.r[0] = t.r[s];for (int i = 2 * s; i <= m; i *= 2) {if (i < m && t.r[i].key < t.r[i + 1].key)i++;if (t.r[0].key >= t.r[i].key)break;t.r[s] = t.r[i];s = i;}t.r[s] = t.r[0];
}
//创建堆
void CreateHeap(SqList &t) {int n = t.length;for (int i = n / 2; i >= 1; i--) {HeapAdjust(t, i, n);}
}
//堆排序
void HeapSort(SqList &t) {CreateHeap(t);for (int i = t.length; i >= 2; i--) {t.r[0] = t.r[1];t.r[1] = t.r[i];t.r[i] = t.r[0];HeapAdjust(t, 1, i - 1);}
}
//归并
void Merge(SqList &t, RedType *&S, int low, int high) {int i = low, k = low, mid = (low + high) / 2;int j = mid + 1;while (i <= mid && j <= high) {if (t.r[i].key <= t.r[j].key)S[k++] = t.r[i++];elseS[k++] = t.r[j++];}while (i <= mid)S[k++] = t.r[i++];while (j <= high)S[k++] = t.r[j++];for (int m = low; m <= high; m++)t.r[m] = S[m];
}
//归并排序
void MergeSort(SqList &t, RedType *&S, int low, int high) {if (low >= high) {S[low] = t.r[low];} else {int mid = (low + high) / 2;MergeSort(t, S, low, mid);MergeSort(t, S, mid + 1, high);Merge(t, S, low, high);}
}void menu() {cout << endl;cout << "    ----排序操作----    " << endl;cout << "************************" << endl;cout << "*   1---产生随机数     *" << endl;cout << "*   2---直接插入排序   *" << endl;cout << "*   3---折半插入排序   *" << endl;cout << "*   4---希尔排序       *" << endl;cout << "*   5---冒泡排序       *" << endl;cout << "*   6---快速排序       *" << endl;cout << "*   7---简单选择排序   *" << endl;cout << "*   8---堆排序         *" << endl;cout << "*   9---归并排序       *" << endl;cout << "*   0---退出           *" << endl;cout << "************************" << endl;cout << "请选择菜单（0-9）：";
}int List() {int n = -1, flag = 0;SqList T, R;RedType *S = (RedType *)malloc(sizeof(RedType) * T.length + 1);while (n != 0) {menu();cin >> n;switch (n) {case 1:cout << "产生随机数如下" ;producerandom(T);flag = 1;break;case 2:if (flag) {cout << "直接插入排序" ;R = T;InsertSort(R);print(R);} else {cout << "请先产生随机数" << endl;}break;case 3:if (flag) {cout << "折半插入排序" ;R = T;BInsertSort(R);print(R);} else {cout << "请先产生随机数" << endl;}break;case 4:if (flag) {cout << "希尔排序" ;R = T;ShellSort(R);print(R);} else {cout << "请先产生随机数" << endl;}break;case 5:if (flag) {cout << "冒泡排序";R = T;BubbleSort(R);print(R);} else {cout << "请先产生随机数" << endl;}break;case 6:if (flag) {cout << "快速排序";R = T;QuickSort(R, 1, R.length);print(R);} else {cout << "请先产生随机数" << endl;}break;case 7:if (flag) {cout << "简单选择排序" ;R = T;SelectSort(R);print(R);} else {cout << "请先产生随机数" << endl;}break;case 8:if (flag) {cout << "堆排序" ;R = T;HeapSort(R);print(R);} else {cout << "请先产生随机数" << endl;}break;case 9:if (flag) {cout << "归并排序" ;R = T;MergeSort(R, S, 1, R.length);print(R);} else {cout << "请先产生随机数" << endl;}break;case 0:cout << "退出成功" << endl;break;default:cout << "输入数字错误,请重新输入" << endl;break;}}return 0;
}int main() {List();return 0;
}

作者文坛写于2020年6月6日