# 8种排序算法的比较案例
# 一、使用说明
## 1.1 操作手册
- 运行程序后，进入欢迎界面
- 输入排序的规模
- 选择排序方法
### 1.1.1 冒泡排序
输入1冒泡排序，例如：
程序将给出排序的时间和交换的次数。
### 1.1.2 选择排序
输入2进行选择排序，例如：
程序将给出排序的时间和交换的次数。
### 1.1.3 直接插入排序
输入3进行直接插入排序，例如：
程序将给出排序的时间和交换的次数。
### 1.1.4 希尔排序
输入4进行希尔排序，例如：
程序将给出排序的时间和交换的次数。
### 1.1.5 快速排序
输入5进行快速排序，例如：
程序将给出排序的时间和交换的次数。
### 1.1.6 堆排序
输入6进行堆排序，例如：
程序将给出排序的时间和交换的次数。
### 1.1.7 归并排序
输入7进行归并排序，例如：
程序将给出排序时间和比较次数。
### 1.1.8 基数排序
输入8进行基数排序，例如：
# 二、概述
## 2.1 程序设计目的
本程序实现了冒泡、选择、直接插入、快排、希尔、堆、归并、基数八种基本排序方法，比较了它们的排序时间和比较次数。
## 2.2 算法思路
- **冒泡排序**：重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成
- **选择排序**：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完
- **直接插入排序**：第一趟比较前两个数，然后把第二个数按大小插入到有序表中； 第二趟把第三个数据与前两个数从后向前扫描，把第三个数按大小插入到有序表中；依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程
- **快速排序**：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列
- **希尔排序**：把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止
- **堆排序**：利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值，即A[PARENT[i]] >= A[i]。在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶
- **归并排序**：比较a[i]和a[j]的大小，若a[i]≤a[j]，则将第一个有序表中的元素a[i]复制到r[k]中，并令i和k分别加上1；否则将第二个有序表中 的元素a[j]复制到r[k]中，并令j和k分别加上1，如此循环下去，直到其中一个有序表取完，然后再将另一个有序表中剩余的元素复制到r中从下标k到 下标t的单元。归并排序的算法我们通常用递归实现，先把待排序区间[s,t]以中点二分，接着把左边子区间排序，再把右边子区间排序，最后把左区间和右区 间用一次归并操作合并成有序的区间[s,t]
- **基数排序**：透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用
## 2.3 数据结构
除了堆排序的数据结构为堆外，其他用的基本都是数组。
# 三、函数接口
## 3.1 冒泡排序
| 成员函数名 | 功能 | 参数 |
| --------------------------- | ------ | ------- |
| void bubble_sort(int arr[]) | 进行冒泡排序 | 需要排序的序列 |
## 3.2 选择排序
| 成员函数名 | 功能 | 参数 |
| ------------------------------ | ------ | ------- |
| void selection_sort(int arr[]) | 进行选择排序 | 需要排序的序列 |
## 3.3 直接插入排序
| 成员函数名 | 功能 | 参数 |
| ------------------------------ | -------- | ------- |
| void insertion_sort(int arr[]) | 进行直接插入排序 | 需要排序的序列 |
## 3.4 希尔排序
| 成员函数名 | 功能 | 参数 |
| -------------------------- | -------- | ------- |
| void shell_sort(int arr[]) | 进行希尔插入排序 | 需要排序的序列 |
## 3.5 快速排序
| 成员函数名 | 功能 | 参数 |
| ---------------------------------------- | ---------- | ------------- |
| void quick_sort(int arr[]) | 进行快速排序 | 需要排序的序列 |
| void quick_sort_help(int arr[], cons tint left, cons tint right) | 辅助快速排序递归函数 | 需要排序的序列；左值；右值 |
## 3.6 堆排序
| 成员函数名 | 功能 | 参数 |
| ---------------------------------------- | ------- | ------------- |
| void heap_sort(int arr[]) | 进行堆插入排序 | 需要排序的序列 |
| void HeapAdjust(int arr[], int I, int nLength) | 堆维护函数 | 需要排序的序列；节点；深度 |
## 3.7 归并排序
| 成员函数名 | 功能 | 参数 |
| ---------------------------------------- | ------- | --------------------- |
| void merge_sort(int arr[]) | 进行堆归并排序 | 需要排序的序列 |
| void merge_help1(int arr[], int temp[], int start, int end) | 归并辅助函数 | 需要排序的序列；临时数组； 开始；结束 |
| void merge_help2(int arr[], int temp[], int start, int mid, int end) | 归并辅助函数 | 需要排序的序列；临时数组；开始；中值；结束 |
## 3.8 基数排序
| 成员函数名 | 功能 | 参数 |
| ---------------------------------------- | -------- | ------------ |
| void radix_sort(int arr[]) | 进行基数排序 | 需要排序的序列 |
| int getPlaces(int num) | 获取“桶子” | 存放的数 |
| int getMax(int arr[], int n) | 获取最大值 | 需要排序的序列；个数 |
| void radix_help(int arr[], int n, int place) | 基数排序辅助函数 | 需要排序的序列；个数；桶 |
# 四、体会
排序算法对于一个程序员来说是什么重要的，如何高效地进行排序，是一门学问。这八种基本的排序算法由简到难都凝聚着一代代人
