精选_毕业设计_8种排序算法的比较案例_完整源码

# 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) | 基数排序辅助函数 | 需要排序的序列；个数；桶 | # 四、体会 排序算法对于一个程序员来说是什么重要的，如何高效地进行排序，是一门学问。这八种基本的排序算法由简到难都凝聚着一代代人