实验内容：
输入一组关键字序列，分别实现下列排序算法:
1.编写函数，实现简单选择排序、直接插入排序和冒泡排序算法。
2.编写函数，实现希尔排序算法。
3.编写函数，实现快速排序算法。
4.编写函数，实现堆排序算法。
5.编写函数，实现折半插入排序算法。
6.编写一个主函数，在主函数中设计一个简单的菜单，分别调试上述算法。
源码：
#include <iostream>
#include <string>
using namespace std;#define MAXSIZE 100 /*参加排序元素的最大个数*/typedef struct list
{int key;
}RedType;typedef struct
{RedType r[MAXSIZE + 1];int length; /*参加排序元素的实际个数*/
}SqList;// 创建字符序列
void CreateList(SqList& L) {cout << "请依次输入元素：" << endl;for (int i = 1;i < L.length + 1;i++){cout << "第" << i << "个" << '\t';cin >> L.r[i].key;}
}// 打印字符序列
void PrintList(SqList& L)
{cout << "排序后的元素序列为：";for (int i = 1;i < L.length + 1; i++){cout << L.r[i].key;}cout << endl;
}// 简单选择排序
void slectOrder(SqList& L) {int min;for (int i = 1; i < L.length + 1;i++){min = i;for (int j = i + 1;j < L.length + 1;j++) { // 从无序区选取最小元素if (L.r[min].key > L.r[j].key) {min = j; // 用k标记无序区中的最小元素}}if (min != i){L.r[0] = L.r[i]; // R[0]临时存放R[i]L.r[i] = L.r[min]; // 将最小元素K放入有序区中正确的位置L.r[min] = L.r[0];}}PrintList(L);
}// 直接插入排序
void insertOrder(SqList& L) {int i, j;for (i = 1;i < L.length + 1;i++){L.r[0] = L.r[i]; // 临时存放要比较的数j = i - 1; // 有序区最后一个元素while (j >= 0 && L.r[0].key < L.r[j].key){ // 如果当有序区的元素（从最后一个依次向前）大于要插入的元素L.r[j + 1] = L.r[j]; // 元素后移，以便于腾出一个位置插入tmpj--;}L.r[j + 1] = L.r[0]; // 在j+1位置处插入tmp，即R[j+1]}PrintList(L);
}// 冒泡排序
void bubleOrder(SqList& L) {for (int i = 1; i < L.length + 1; i++) {for (int j = 1; j < L.length + 1 - i; j++) {if (L.r[j].key > L.r[j + 1].key) {L.r[0] = L.r[j];L.r[j] = L.r[j + 1];L.r[j + 1] = L.r[0];}}}PrintList(L);
}// 希尔排序
void shellOrder(SqList& L) {int i, j, d;d = L.length + 1 / 2; // 增量初始值while (d > 0) // 循环到增量d=1为止{ for (i = d + 1;i < L.length + 1;i++) // 对所有间隔d的位置进行排序{L.r[0] = L.r[i]; // 将i位置的元素暂时存放在0号位置j = i - d;while (j >= 1 && L.r[0].key < L.r[j].key){L.r[j + d] = L.r[j]; // 对相隔d位置的元素组进行排序j = j - d; // 依次和前面的相隔d的倍数的位置进行比较并排序}L.r[j + d] = L.r[0]; // 插入元素}d = d / 2; // 减小增量}PrintList(L);
}// 快速排序
int Partition(SqList& L, int low, int high) {int pivotkey = L.r[low].key;while (low < high) {while (low < high && L.r[high].key >= pivotkey) {high--;}L.r[0] = L.r[low];L.r[low] = L.r[high];L.r[high] = L.r[0];while (low < high && L.r[low].key <= pivotkey) {low++;}L.r[0] = L.r[low];L.r[low] = L.r[high];L.r[high] = L.r[0];}return low;
}void QSort(SqList &L, int low, int high) {int pivotloc;if (low < high) {pivotloc = Partition(L, low, high);QSort(L, low, pivotloc - 1);QSort(L, pivotloc + 1, high);}
}void QuickSort(SqList &L) {QSort(L, 1, L.length);PrintList(L);
}// 堆排序
void Sift(SqList& L, int low, int high) // R[low...high]将其调整成堆结构
{int i = low, j = 2 * i; // R[j]是R[i]的左孩子L.r[0] = L.r[i];while (j < high){if (j < high && L.r[j].key < L.r[j + 1].key) { // 当左孩子小于右孩子时循环j++;}if (L.r[0].key < L.r[j].key) // 如果双亲节点小于孩子节点{L.r[i] = L.r[j]; // 将R[j]调整到双亲结点位置上i = j; // 修改i和j的值，以便继续向下前进j = 2 * i;}else { // 如果双亲节点都大于孩子节点，筛选结束break; }}L.r[i] = L.r[0]; // 将被筛选节点放入到最终位置
}void HeapSort(SqList& L)
{int i;for (i = L.length + 1 / 2; i >= 1; i--)Sift(L, i, L.length); // 循环建立初始堆for (i = L.length;i >= 2;i--) // 进行n-1次循环，完成堆排序{L.r[0] = L.r[1]; // 将第一个元素与当前区间内的元素进行互换L.r[1] = L.r[i];L.r[i] = L.r[0];Sift(L, 1, i - 1); // 筛选R[i]节点，得到i-1个节点的堆}PrintList(L);
}// 折半插入排序
void BInsertSort(SqList& L)
{int i, j, low, high, mid;for (i = 1; i < L.length + 1; i++){L.r[0] = L.r[i]; // 将L.R[i]暂时存放在L.R[0]low = 1;high = i - 1; // 在R[low...high]中查找需要插入的位置while (low <= high){mid = (low + high) / 2; // 取中间位置进行比较if (L.r[0].key < L.r[mid].key) { // 当需要插入的元素在小于中间元素时high = mid - 1; // 缩小查找范围R[low...mid-1]}else { // 当需要插入的元素在大于等于中间元素时low = mid + 1; // 缩小查找范围R[mid+1...high]}}/*当找到合适的位置时，high = low = mid;则元素应该插入到high的后面；那么high后面的元素应该后移，low应该插入到high+1。*/for (j = i - 1; j >= high + 1; j--) { // 元素后移L.r[j + 1] = L.r[j];}L.r[high + 1] = L.r[0]; // 插入元素}PrintList(L);
}int main() {// 根据输入字符序列创建排序序列SqList L;cout << "请输入元素个数: ";cin >> L.length;CreateList(L);// 输入操作序号int num;cout << "1．简单选择排序" << endl;cout << "2．直接插入排序" << endl;cout << "3．冒泡排序" << endl;cout << "4．希尔排序" << endl;cout << "5．快速排序" << endl;cout << "6．堆排序" << endl;cout << "7. 折半插入排序" << endl;cout << "8．退出";cout << endl;while (true){cout << "请输入您要选择的计算: " << endl;cin >> num;switch (num){case 1: {cout << "简单选择排序:" << endl;slectOrder(L);cout << endl;}break;case 2: {cout << "直接插入排序:" << endl;insertOrder(L);cout << endl;}break;case 3:{cout << "冒泡排序:" << endl;bubleOrder(L);cout << endl;}break;case 4: {cout << "希尔排序:" << endl;shellOrder(L);cout << endl;}break;case 5: {cout << "快速排序:" << endl; QuickSort(L);cout << endl;}break;case 6:{cout << "堆排序:" << endl; HeapSort(L);cout << endl;}break;case 7:{cout << "折半插入排序:" << endl; BInsertSort(L);}break;case 8:{cout << "退出成功！" << endl;system("pause");return 0;}break;default:{cout << "输入有误！请重新输入！" << endl;}}}system("pause");return 0;
}
一、实验目的
1. 掌握常见的排序算法(插入排序、交换排序、选择排序、归并排序、基数排序等)的思想、特点及其适用条件
2. 熟练掌握常见的排序算法的程序实现
二、问题分析及数据结构设计
1. 问题分析：
输入一组关键字序列，实现下列排序算法:简单选择排序、直接插入排序、冒泡排序、希尔排序、快速排序、堆排序、折半插入排序算法。需要我们掌握堆的数据结构，二分法等，知道排序的递归和非递归算法的实现。
2. 数据结构设计：
参加排序元素的最大个数：MAXSIZE 100；
排序元素类型：list，别名RedType，包括元素值：key--整型；
排序序列类型：SqList，包含length--整型，表示参加排序元素的实际个数、
r[MAXSIZE + 1]--RedType类型，存放待排序的元素。
（其中r[0]为哨兵，不参与实际排序，实际排序的元素从r[1]开始）
三、算法设计（伪代码表示）
1. 输入字符序列 创建待排序序列
Function createList(SqList& L)
Begin
For i = 1 -> 序列长度 + 1；i++
cin >> 序列.第i个元素.值key
End
2. 打印字符序列
Function PrintList(SqList& L)
Begin
For i = 1 -> 序列长度 + 1；i++
cout >> 序列.第i个元素.值key
End
3. 简单选择排序
Function SelectOrder(SqList& L)
Begin
For i = 1 -> 序列长度 + 1；i++
最小下标 = i
For j = i + 1 -> 序列长度 + 1；j++
IF 序列.最小下标的元素.值key > 序列.第j个元素.值key
最小值 = j
IF 最小下标 != i
序列.第0个元素 = 序列.第i个元素
序列.第i个元素 = 序列.最小下标的元素
序列.最小下标的元素 = 序列.第0个元素
PrintList(SqList L)
End
4. 直接插入排序
Function InsertOrder(SqList& L)
Begin
For i = 1 -> 序列长度 + 1；i++
序列.第0个元素 = 序列.第i个元素
j = i - 1
WHILE j >= 0 && 序列.第0个元素.值key < 序列.第j个元素.值key
序列.第j + 1个元素 = 序列.第j 个元素
j--
序列.第j + 1个元素 = 序列.第0个元素
PrintList(SqList L)
End
5. 冒泡排序
Function bubleOrder(SqList& L)
Begin
For i = 1 -> 序列长度 + 1；i++
For j = 1 -> 序列长度 + 1；j++
IF 序列.第j个元素.值key > 序列.第j + 1个元素.值key
序列.第0个元素.值key > 序列.第j 个元素.值key
序列.第j个元素.值key > 序列.第j + 1个元素.值key
序列.第j + 1个元素.值key > 序列.第0个元素.值key
PrintList(SqList L)
End
6. 希尔排序
Function shellOrder(SqList& L)
Begin
d = 序列.长度 + 1 / 2
WHILE d > 0
For i = d + 1 -> 序列.长度 + 1；i++
序列.第0个元素 = 序列.第i个元素
j = i - d
WHILE j >= 1 && 序列.第0个元素.值key < 序列.第j个元素.值key
序列.第j + d个元素 = 序列.第j个元素
j = j - d
序列.第j + d个元素 = 序列.第0个元素
d = d / 2
PrintList(SqList L)
End
7. 快速排序
7.1
Function Partition(SqList& L, int low, int high)
Begin
Pivotkey = 序列.左指针所在元素.值key
WHILE 左指针 < 右指针
WHILE 左指针 < 右指针 && 序列.右指针所在元素.值key >= 序列.左指针所在元素.值key
右指针左移
序列.第0个元素 = 序列.左指针所在元素
序列.左指针所在元素 = 序列.右指针所在元素
序列.右指针所在元素 = 序列.第0个元素
WHILE 左指针 < 右指针 && 序列.左指针所在元素.值key <= 序列.左指针所在元素.值key
左指针右移
序列.第0个元素 = 序列.右指针所在元素
序列.右指针所在元素 = 序列.左指针所在元素
序列.左指针所在元素 = 序列.第0个元素
Return low
End
7.2
Function Qsort(SqList& L, int low, int high)
Begin
IF 左指针 < 右指针
Pivotloc = Partition(L，low，high)
Qsort(L，low，Pivotloc - 1)
Qsort(L，Pivotloc + 1，high)
End
7.3
Function QuickSort(SqList& L)
Begin
Qsort(L，1，序列.长度)
PrintList(SqList L)
End
8. 堆排序
8.1
Function Sift(SqList& L, int low, int high)
Begin
I = low
J = 2 * i
序列.第0个元素 = 序列.第i个元素
WHILE j < high
IF j < high && 序列.第j个元素.值key < 序列.第j + 1个元素.值key
J++
IF 序列.第0个元素.值key < 序列.第j个元素.值key
序列.第i个元素 = 序列.第j个元素
I = j
J = 2 * i
ELSE break
序列.第i个元素 = 序列.第0个元素
End
8.2
Function HeapSort(SqList& L)
Begin
For i = 序列.长度 + 1 / 2 -> i = 1；i--
Sift(L，i，序列.长度)
For i = 序列.长度 -> 2；i--
序列.第0个元素 > 序列.第1 个元素
序列.第1个元素 > 序列.第i个元素
序列.第i个元素 > 序列.第0个元素
Sift(L，1，i - 1)
PrintList(SqList L)
End
9. 折半插入排序
Function BInsertSort(SqList& L)
Begin
For i = 1 -> 序列.长度 + 1；i++
序列.第0个元素 = 序列.第i个元素
区间下限 = 1
区间上限 = i - 1
WHILE 区间下限 <= 区间上限
中间位置 = 下限 + 上限 / 2
IF 序列.第0个元素.值key < 序列.中间元素.值key
上限 = 中间位置 - 1
ELSE
下限 = 中间位置 + 1
For j = i - 1 -> 上限 + 1；j--
序列.第j + 1个元素 = 序列.第j个元素
序列.上限 + 1个元素 = 序列.第0个元素
PrintList(SqList L)
End
四、功能模块程序流程图
1. 菜单
说明：菜单功能首先提示用户输入数字。
输入数字1，代表简单选择排序，提示用户输入元素个数，以及第几个元素，以此建立排序序列，最后输出序列的简单排序的结果；
输入数字2，代表直接插入排序，提示用户输入元素个数，以及第几个元素，以此建立排序序列，最后输出序列的直接插入排序的结果；
输入数字3，代表冒泡排序，提示用户输入元素个数，以及第几个元素，以此建立排序序列，最后输出序列的冒泡排序的结果；
输入数字4，代表希尔排序，提示用户输入元素个数，以及第几个元素，以此建立排序序列，最后输出序列的希尔排序的结果；
输入数字5，代表快速排序，提示用户输入元素个数，以及第几个元素，以此建立排序序列，最后输出序列的快速排序的结果；
输入数字6，代表堆排序，提示用户输入元素个数，以及第几个元素，以此建立排序序列，最后输出序列的堆排序的结果；
输入数字7，代表折半插入排序，提示用户输入元素个数，以及第几个元素，以此建立排序序列，最后输出序列的折半插入排序的结果；
输入数字8，系统退出，提示用户“退出成功！”；
输入其他数字，提示用户"输入有误！请重新输入！"。
2. 简单选择排序
说明：该函数目的为对序列进行简单选择排序，提示用户输入元素个数，以及第几个元素，以此建立排序序列，最后输出序列的简单选择排序的结果。
3. 直接插入排序
说明：该函数目的为对序列进行直接插入排序，提示用户输入元素个数，以及第几个元素，以此建立排序序列，最后输出序列的直接插入排序的结果。
4. 冒泡排序
说明：该函数目的为对序列进行冒泡排序，提示用户输入元素个数，以及第几个元素，以此建立排序序列，最后输出序列的冒泡排序的结果。
5. 希尔排序
说明：该函数目的为对序列进行希尔排序，提示用户输入元素个数，以及第几个元素，以此建立排序序列，最后输出序列的希尔排序的结果。
6. 快速排序
说明：该函数目的为对序列进行快速排序，提示用户输入元素个数，以及第几个元素，以此建立排序序列，最后输出序列的快速排序的结果。
7. 堆排序
说明：该函数目的为对序列进行堆排序，提示用户输入元素个数，以及第几个元素，以此建立排序序列，最后输出序列的堆排序的结果。
8. 折半插入排序
说明：该函数目的为对序列进行折半插入排序，提示用户输入元素个数，以及第几个元素，以此建立排序序列，最后输出序列的折半插入排序的结果。
五、实验结果
1. 简单选择排序：
分析：输入数字1后进入该对刚刚输入的排序序列进行简单选择排序的功能。首先提示用户输入元素个数，以及第几个元素，以此建立排序序列，最后输出序列的简单选择排序的结果。接着提示用户继续选择想要的计算。
2. 直接插入排序：
分析：输入数字2后进入该对刚刚输入的排序序列进行直接插入排序的功能。首先提示用户输入元素个数，以及第几个元素，以此建立排序序列，最后输出序列的直接插入排序的结果。接着提示用户继续选择想要的计算。
3. 冒泡排序：
分析：输入数字3后进入该对刚刚输入的排序序列进行冒泡排序的功能。首先提示用户输入元素个数，以及第几个元素，以此建立排序序列，最后输出序列的冒泡的结果。接着提示用户继续选择想要的计算。
4. 希尔排序：
分析：输入数字4后进入该对刚刚输入的排序序列进行希尔排序的功能。首先提示用户输入元素个数，以及第几个元素，以此建立排序序列，最后输出序列的希尔排序的结果。接着提示用户继续选择想要的计算。
5. 快速排序：
分析：输入数字5后进入该对刚刚输入的排序序列进行快速排序的功能。首先提示用户输入元素个数，以及第几个元素，以此建立排序序列，最后输出序列的快速排序的结果。接着提示用户继续选择想要的计算。
6. 堆排序：
分析：输入数字6后进入该对刚刚输入的排序序列进行堆排序的功能。首先提示用户输入元素个数，以及第几个元素，以此建立排序序列，最后输出序列的堆排序的结果。接着提示用户继续选择想要的计算。
7. 折半插入排序：
分析：输入数字7后进入该对刚刚输入的排序序列进行折半插入排序的功能。首先提示用户输入元素个数，以及第几个元素，以此建立排序序列，最后输出序列的折半插入排序的结果。接着提示用户继续选择想要的计算。
8. 退出：
分析：输入数字8后进入该退出系统的功能，提示用户退出成功。退出成功后，不会再出现提示用户继续输入想要选择的运算。
9. 输入其他数字：
分析：输入其他数字后进提示用户输入有误，请重新输入。并再次提示用户继续输入想要选择的运算。
六、算法分析
1. 简单选择排序：
核心思想是在未排序的序列中找到最小的元素，然后将其放到序列的起始位置。
接着，再从剩余未排序的序列中找到最小的元素，放到已排序序列的末尾。
重复这个过程，直到整个序列都被排序。
2. 直接插入排序：
核心思想是将一个待排序的元素插入到已经排好序的部分序列中，使得插入之后的序列仍然保持有序。
即从第二个元素开始，依次将后面的元素插入到已排好序的序列中，直到所有元素都被插入。
3. 冒泡排序：
核心思想是利用外层和内层两个for循环，外层for循环代表总共比较的趟数，内层for循环代表每趟比较的次数。
从第一个元素开始，依次比较相邻的两个元素，如果顺序不对就交换它们的位置，这样一轮下来，最大的元素就放在了最后。
然后，对剩下的n-1个元素重复上述过程，直到所有元素都排好序。
3. 希尔排序：
首先确定一个增量序列，通常选择增量刚开始为d = n/2，其中n为待排序序列的长度。
然后根据增量序列，将待排序的序列分割成若干个子序列，对每个子序列进行插入排序
。每次缩小增量为上次的d/2，重复上述步骤，直到增量为1，完成最后一次插入排序。
4. 快速排序：
选择一个序列中的第一个元素为基准元素，然后将序列分割成两个子序列，一个子序列中的元素都小于基准元素，另一个子序列中的元素都大于基准元素。
递归地对两个子序列进行排序，当子序列的长度为1或0时，递归结束。
5. 堆排序：
将待排序的序列看作是一个完全二叉树的顺序存储结构，从最后一个非叶子节点开始，依次向前调整，使得每个节点都满足双亲节点的值大于孩子节点的值，以此构建大根堆。
将大根堆的根节点（即序列中的最大元素）与堆的最后一个节点交换位置，然后将剩余的n-1个元素重新调整为最大堆。
重复这个过程，直到整个序列都排好序。
6. 折半插入排序：
核心思想是从第二个元素开始，将当前元素插入到已排序的子序列中。
使用二分查找法在已排序的子序列中找到插入位置。
将插入位置之后的元素后移一位，然后将当前元素插入到找到的位置。
七、操作说明
编译后首先出现一个菜单，1-8有文字信息描述不同的排序的相关算法，提示用户输入1-8之间的数字。输入数字1，代表对刚刚输入的排序序列进行简单选择排序；输入数字2，代表对刚刚输入的排序序列进行直接插入排序；输入数字3，代表对刚刚输入的排序序列进行冒泡排序；输入数字4，代表对刚刚输入的排序序列进行希尔排序；输入数字5，代表对刚刚输入的排序序列进行快速排序；输入数字6，代表对刚刚输入的排序序列进行堆排序；输入数字7，代表对刚刚输入的排序序列进行折半插入排序；输入数字8，系统退出，提示用户“退出成功！”；输入其他数字，提示用户"输入有误！请重新输入！"。
