下载文档原格式
排序的实验报告排序的实验报告引言：排序是计算机科学中非常重要的一个概念，它涉及到对一组数据按照一定规则进行重新排列的操作。
在计算机算法中，排序算法的效率直接影响到程序的运行速度和资源利用率。
为了深入了解各种排序算法的原理和性能，我们进行了一系列的排序实验。
实验一：冒泡排序冒泡排序是最简单的排序算法之一。
它的原理是通过相邻元素的比较和交换来实现排序。
我们编写了一个冒泡排序的算法，并使用Python语言进行实现。
实验中，我们分别对10、100、1000个随机生成的整数进行排序，并记录了排序所需的时间。
实验结果显示，随着数据规模的增加，冒泡排序的时间复杂度呈现出明显的增长趋势。
当数据规模为10时，排序所需的时间约为0.001秒；而当数据规模增加到1000时，排序所需的时间则增加到了1.5秒左右。
这说明冒泡排序的效率较低，对大规模数据的排序并不适用。
实验二：快速排序快速排序是一种常用的排序算法，它的核心思想是通过分治的策略将数据分成较小的子集，然后递归地对子集进行排序。
我们同样使用Python语言实现了快速排序算法，并对相同规模的数据进行了排序实验。
实验结果显示，快速排序的时间复杂度相对较低。
当数据规模为10时，排序所需的时间约为0.0005秒；而当数据规模增加到1000时，排序所需的时间仅为0.02秒左右。
这说明快速排序适用于大规模数据的排序，其效率较高。
实验三：归并排序归并排序是一种稳定的排序算法，它的原理是将待排序的数据分成若干个子序列，然后将子序列两两合并，直到最终得到有序的结果。
我们同样使用Python 语言实现了归并排序算法，并进行了相同规模数据的排序实验。
实验结果显示，归并排序的时间复杂度相对较低。
当数据规模为10时，排序所需的时间约为0.0008秒；而当数据规模增加到1000时，排序所需的时间仅为0.03秒左右。
这说明归并排序同样适用于大规模数据的排序，其效率较高。
讨论与结论：通过以上实验，我们可以得出以下结论：1. 冒泡排序虽然简单易懂，但对于大规模数据的排序效率较低，不适用于实际应用。
排序的应用实验报告实验题目：排序的应用实验一、实验目的：1. 了解排序算法的基本原理和应用场景；2. 掌握常见的排序算法的实现方法；3. 熟悉排序算法的时间复杂度分析；4. 在实际应用中灵活运用排序算法。
二、实验原理：排序是将一组数据按照某个规则进行重新排列的过程，常见的排序算法有冒泡排序、选择排序、插入排序、归并排序、快速排序、堆排序等。
每种排序算法有其特点和适用场景，掌握不同排序算法的实现方法和时间复杂度对于实际应用非常重要。
三、实验内容及步骤：1. 冒泡排序实验：a) 随机生成一组整数数据；b) 利用冒泡排序算法对数据进行排序；c) 输出排序结果，并统计排序过程中的比较次数和交换次数。
2. 选择排序实验：a) 随机生成一组整数数据；b) 利用选择排序算法对数据进行排序；c) 输出排序结果，并统计排序过程中的比较次数和交换次数。
3. 插入排序实验：a) 随机生成一组整数数据；b) 利用插入排序算法对数据进行排序；c) 输出排序结果，并统计排序过程中的比较次数和移动次数。
4. 归并排序实验：a) 随机生成一组整数数据；b) 利用归并排序算法对数据进行排序；c) 输出排序结果。
5. 快速排序实验：a) 随机生成一组整数数据；b) 利用快速排序算法对数据进行排序；c) 输出排序结果。
四、实验结果及分析：1. 冒泡排序实验结果：随机生成的一组整数数据为：[5, 3, 8, 2, 6]排序过程中的比较次数为：10排序过程中的交换次数为：4排序结果为：[2, 3, 5, 6, 8]2. 选择排序实验结果：随机生成的一组整数数据为：[5, 3, 8, 2, 6] 排序过程中的比较次数为：10排序过程中的交换次数为：4排序结果为：[2, 3, 5, 6, 8]3. 插入排序实验结果：随机生成的一组整数数据为：[5, 3, 8, 2, 6] 排序过程中的比较次数为：10排序过程中的移动次数为：7排序结果为：[2, 3, 5, 6, 8]4. 归并排序实验结果：随机生成的一组整数数据为：[5, 3, 8, 2, 6] 排序结果为：[2, 3, 5, 6, 8]5. 快速排序实验结果：随机生成的一组整数数据为：[5, 3, 8, 2, 6]排序结果为：[2, 3, 5, 6, 8]五、实验总结：通过本次实验，我对常见的排序算法有了更深入的了解。
查找和排序实验报告查找和排序实验报告一、引言查找和排序是计算机科学中非常重要的基础算法之一。
查找（Search）是指在一组数据中寻找目标元素的过程，而排序（Sort）则是将一组数据按照特定的规则进行排列的过程。
本实验旨在通过实际操作和实验验证，深入理解查找和排序算法的原理和应用。
二、查找算法实验1. 顺序查找顺序查找是最简单的查找算法之一，它的基本思想是逐个比较待查找元素与数据集合中的元素，直到找到目标元素或遍历完整个数据集合。
在本实验中，我们设计了一个包含1000个随机整数的数据集合，并使用顺序查找算法查找指定的目标元素。
实验结果显示，顺序查找的时间复杂度为O(n)。
2. 二分查找二分查找是一种高效的查找算法，它要求待查找的数据集合必须是有序的。
二分查找的基本思想是通过不断缩小查找范围，将待查找元素与中间元素进行比较，从而确定目标元素的位置。
在本实验中，我们首先对数据集合进行排序，然后使用二分查找算法查找指定的目标元素。
实验结果显示，二分查找的时间复杂度为O(log n)。
三、排序算法实验1. 冒泡排序冒泡排序是一种简单但低效的排序算法，它的基本思想是通过相邻元素的比较和交换，将较大（或较小）的元素逐渐“冒泡”到数列的一端。
在本实验中，我们设计了一个包含1000个随机整数的数据集合，并使用冒泡排序算法对其进行排序。
实验结果显示，冒泡排序的时间复杂度为O(n^2)。
2. 插入排序插入排序是一种简单且高效的排序算法，它的基本思想是将数据集合分为已排序和未排序两部分，每次从未排序部分选择一个元素插入到已排序部分的适当位置。
在本实验中，我们使用插入排序算法对包含1000个随机整数的数据集合进行排序。
实验结果显示，插入排序的时间复杂度为O(n^2)。
3. 快速排序快速排序是一种高效的排序算法，它的基本思想是通过递归地将数据集合划分为较小和较大的两个子集合，然后对子集合进行排序，最后将排序好的子集合合并起来。
第1篇一、实验目的1. 熟悉常见的查找和排序算法。
2. 分析不同查找和排序算法的时间复杂度和空间复杂度。
3. 比较不同算法在处理大数据量时的性能差异。
二、实验环境1. 操作系统：Windows 102. 编程语言：Python3.73. 开发工具：PyCharm三、实验内容1. 实现以下查找和排序算法：（1）查找算法：顺序查找、二分查找（2）排序算法：冒泡排序、选择排序、插入排序、快速排序、归并排序2. 分析算法的时间复杂度和空间复杂度。
3. 对不同算法进行性能测试，比较其处理大数据量时的性能差异。
四、实验步骤1. 实现查找和排序算法。
2. 分析算法的时间复杂度和空间复杂度。
3. 创建测试数据，包括小数据量和大数据量。
4. 对每种算法进行测试，记录运行时间。
5. 分析测试结果，比较不同算法的性能。
五、实验结果与分析1. 算法实现（1）顺序查找def sequential_search(arr, target): for i in range(len(arr)):if arr[i] == target:return ireturn -1（2）二分查找def binary_search(arr, target):low, high = 0, len(arr) - 1while low <= high:mid = (low + high) // 2if arr[mid] == target:return midelif arr[mid] < target:low = mid + 1else:high = mid - 1return -1（3）冒泡排序def bubble_sort(arr):n = len(arr)for i in range(n):for j in range(0, n-i-1):if arr[j] > arr[j+1]:arr[j], arr[j+1] = arr[j+1], arr[j]（4）选择排序def selection_sort(arr):n = len(arr)for i in range(n):min_idx = ifor j in range(i+1, n):if arr[min_idx] > arr[j]:min_idx = jarr[i], arr[min_idx] = arr[min_idx], arr[i]（5）插入排序def insertion_sort(arr):for i in range(1, len(arr)):key = arr[i]j = i-1while j >=0 and key < arr[j]:arr[j+1] = arr[j]j -= 1arr[j+1] = key（6）快速排序def quick_sort(arr):if len(arr) <= 1:pivot = arr[len(arr) // 2]left = [x for x in arr if x < pivot]middle = [x for x in arr if x == pivot]right = [x for x in arr if x > pivot]return quick_sort(left) + middle + quick_sort(right)（7）归并排序def merge_sort(arr):if len(arr) <= 1:return arrmid = len(arr) // 2left = merge_sort(arr[:mid])right = merge_sort(arr[mid:])return merge(left, right)def merge(left, right):result = []i = j = 0while i < len(left) and j < len(right):if left[i] < right[j]:result.append(left[i])i += 1else:result.append(right[j])result.extend(left[i:])result.extend(right[j:])return result2. 算法时间复杂度和空间复杂度分析（1）顺序查找：时间复杂度为O(n)，空间复杂度为O(1)。
第1篇一、实验背景随着计算机科学的发展，算法在各个领域都扮演着至关重要的角色。
排序算法作为算法领域中的一项基本技能，其重要性不言而喻。
快速排序作为一种高效的排序算法，因其简洁的原理和良好的性能，被广泛应用于各种场景。
本次实验旨在通过实践，深入了解快速排序算法的原理、实现及其性能特点。
二、实验目的1. 掌握快速排序算法的基本原理和实现方法；2. 分析快速排序算法的时间复杂度和空间复杂度；3. 比较快速排序与其他排序算法的性能差异；4. 熟练运用快速排序算法解决实际问题。
三、实验内容1. 快速排序算法原理及实现快速排序是一种分而治之的排序算法，其基本思想是：选取一个基准元素，将待排序序列划分为两个子序列，一个子序列中的所有元素均小于等于基准元素，另一个子序列中的所有元素均大于等于基准元素。
然后递归地对这两个子序列进行快速排序。
具体实现步骤如下：（1）选择基准元素：从待排序序列中选取一个元素作为基准元素，通常选择序列的第一个或最后一个元素。
（2）划分：将待排序序列划分为两个子序列，左子序列包含小于等于基准元素的元素，右子序列包含大于等于基准元素的元素。
（3）递归排序：递归地对左子序列和右子序列进行快速排序。
2. 快速排序算法性能分析快速排序算法的平均时间复杂度为O(nlogn)，最坏情况下的时间复杂度为O(n^2)。
空间复杂度为O(logn)，因为快速排序采用递归实现，需要一定的栈空间。
3. 快速排序与其他排序算法的比较与冒泡排序、插入排序等简单排序算法相比，快速排序具有以下优点：（1）时间复杂度较低，适用于大规模数据的排序；（2）空间复杂度较低，节省内存资源；（3）对数据结构无特殊要求，适用于各种数据类型。
然而，快速排序也存在以下缺点：（1）最坏情况下的时间复杂度较高，当数据量较大且分布不均匀时，性能可能不如其他排序算法；（2）递归实现可能导致栈溢出，对数据量较大的排序任务不适用。
四、实验总结通过本次实验，我对快速排序算法有了更深入的了解。
排序实验报告排序实验报告引言排序是计算机科学中的一个重要概念，它指的是将一组元素按照特定的规则进行重新排列的过程。
排序算法的选择和性能对于提高计算机程序的效率至关重要。
为了深入了解不同排序算法的优劣，我们进行了一系列的排序实验。
实验设计本次实验选择了五种常见的排序算法进行比较，包括冒泡排序、插入排序、选择排序、快速排序和归并排序。
在实验中，我们使用了Python编程语言来实现这些排序算法，并通过随机生成的整数数组作为排序的输入。
实验过程在实验过程中，我们首先使用了冒泡排序算法。
冒泡排序算法的基本思想是从数组的第一个元素开始，依次比较相邻的两个元素，如果前一个元素大于后一个元素，则交换它们的位置。
通过多次遍历数组，将最大的元素逐渐“冒泡”到数组的末尾。
冒泡排序算法的时间复杂度为O(n^2)。
接下来，我们实现了插入排序算法。
插入排序算法的核心思想是将数组分为已排序和未排序两部分，每次从未排序部分中取出一个元素，并将其插入到已排序部分的适当位置。
插入排序算法的时间复杂度也是O(n^2)。
然后，我们使用了选择排序算法。
选择排序算法的基本思想是每次从未排序的部分中选择最小的元素，然后将其与未排序部分的第一个元素交换位置。
通过多次遍历数组，将最小的元素逐渐选择到数组的开头。
选择排序算法的时间复杂度同样为O(n^2)。
接下来，我们实现了快速排序算法。
快速排序算法是一种分治法的排序算法，其基本思想是选择一个基准元素，将数组分为两个子数组，一个子数组中的元素都小于基准元素，另一个子数组中的元素都大于基准元素。
然后，对这两个子数组分别进行快速排序。
快速排序算法的时间复杂度为O(nlogn)。
最后，我们使用了归并排序算法。
归并排序算法也是一种分治法的排序算法，其基本思想是将数组递归地分成两个子数组，然后将这两个子数组合并成一个有序数组。
归并排序算法的时间复杂度同样为O(nlogn)。
实验结果通过对不同大小的随机数组进行排序实验，我们得到了如下的实验结果：冒泡排序算法的性能最差，其运行时间随着数组大小的增加呈平方级增长；插入排序和选择排序算法的性能相对较好，但仍然随着数组大小的增加呈平方级增长；快速排序和归并排序算法的性能最佳，其运行时间随着数组大小的增加呈线性对数级增长。
快速排序实验报告《快速排序实验报告》快速排序是一种经典的排序算法，它的时间复杂度为O(nlogn)，在实际应用中具有较高的效率和性能。
本实验旨在通过对快速排序算法的实验验证，探讨其在不同数据规模下的排序效率和性能表现。
实验一：随机数据排序首先，我们对随机生成的数据进行排序实验。
通过对不同规模的随机数据进行排序，我们可以观察到快速排序算法在处理大规模数据时的高效性。
实验结果表明，快速排序在处理随机数据时，排序速度较快且表现稳定，验证了其O(nlogn)的时间复杂度。
实验二：有序数据排序接着，我们对有序数据进行排序实验。
有序数据在排序过程中可能会导致快速排序算法的性能下降，因为快速排序算法的分治策略可能会导致不均匀的分割，从而影响排序效率。
实验结果表明，快速排序在处理有序数据时，排序速度较慢且性能不稳定，这与我们的预期相符。
实验三：重复数据排序最后，我们对重复数据进行排序实验。
重复数据可能会导致快速排序算法的性能下降，因为在分割阶段可能会产生大量的重复数据，导致分割不均匀。
实验结果表明，快速排序在处理重复数据时，排序速度较慢且性能不稳定，这与我们的预期相符。
综上所述，通过对快速排序算法的实验验证，我们可以得出结论：快速排序算法在处理随机数据时具有较高的排序效率和性能表现，但在处理有序数据和重复数据时性能会下降。
因此，在实际应用中，需要根据数据的特点选择合适的排序算法，以达到最佳的排序效果。
总之，快速排序算法作为一种经典的排序算法，在实际应用中具有较高的效率和性能。
通过本实验，我们对快速排序算法的排序效率和性能表现有了更深入的了解，为我们在实际应用中选择合适的排序算法提供了重要的参考依据。
课程设计排序实验报告一、教学目标本课程的教学目标是使学生掌握XX学科的基本知识，提高学生的XX技能，培养学生的科学素养和探究精神。
具体来说，知识目标包括：1.掌握XX学科的基本概念、原理和规律。
2.了解XX学科的发展历程和现状。
3.学会运用XX学科的知识解决实际问题。
技能目标包括：1.能够运用实验方法进行科学探究。
2.能够运用数学方法对实验数据进行分析和处理。
3.能够撰写实验报告，表达自己的观点和结论。
情感态度价值观目标包括：1.培养学生对科学的热爱和好奇心，激发学生探索未知的欲望。
2.培养学生尊重事实、严谨治学的科学态度。
3.培养学生团队合作、沟通交流的能力。
二、教学内容根据课程目标，教学内容主要包括XX学科的基本概念、原理和规律，以及实验方法和技能。
具体安排如下：1.第一部分：XX学科的基本概念、原理和规律。
包括章节1-5，主要介绍XX学科的基础知识，如XX现象的产生、XX规律的应用等。
2.第二部分：实验方法和学习技能。
包括章节6-8，主要介绍实验设计、实验操作、实验数据分析等方法，以及如何撰写实验报告。
3.第三部分：综合应用。
包括章节9-10，主要结合实际问题，让学生运用所学知识和技能进行分析和解决。
三、教学方法为了实现课程目标，我们将采用多种教学方法，如讲授法、讨论法、案例分析法、实验法等。
具体安排如下：1.讲授法：用于传授基本概念、原理和规律，引导学生理解并掌握知识点。
2.讨论法：用于探讨实验现象、分析实验数据，培养学生的思考和表达能力。
3.案例分析法：通过分析实际案例，让学生学会运用所学知识解决实际问题。
4.实验法：让学生亲自动手进行实验，培养学生的实验操作能力和科学探究精神。
四、教学资源为了支持教学内容和教学方法的实施，我们将准备以下教学资源：1.教材：选用权威、实用的教材，为学生提供系统、全面的学习材料。
2.参考书：提供相关领域的参考书籍，拓展学生的知识视野。
3.多媒体资料：制作课件、视频等多媒体资料，提高课堂教学的趣味性和效果。
一、实验目的1. 理解并掌握常见的数组排序算法；2. 分析不同排序算法的优缺点，提高算法选择能力；3. 提高编程能力，熟练运用编程语言实现排序算法。
二、实验环境1. 操作系统：Windows 102. 编程语言：Java3. 开发工具：Eclipse三、实验内容1. 选择合适的排序算法进行实验；2. 编写排序算法的代码，实现数组的排序；3. 对排序结果进行分析，验证排序算法的正确性；4. 比较不同排序算法的执行效率。
四、实验过程1. 选择排序算法本次实验选择了以下四种排序算法进行实验：（1）冒泡排序（Bubble Sort）（2）选择排序（Selection Sort）（3）插入排序（Insertion Sort）（4）快速排序（Quick Sort）2. 编写排序算法代码以下为四种排序算法的Java代码实现：（1）冒泡排序```javapublic class BubbleSort {public static void bubbleSort(int[] arr) {int n = arr.length;for (int i = 0; i < n - 1; i++) {for (int j = 0; j < n - 1 - i; j++) { if (arr[j] > arr[j + 1]) {int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}}}```（2）选择排序```javapublic class SelectionSort {public static void selectionSort(int[] arr) { int n = arr.length;for (int i = 0; i < n - 1; i++) {int minIndex = i;for (int j = i + 1; j < n; j++) {if (arr[j] < arr[minIndex]) {minIndex = j;}}int temp = arr[minIndex];arr[minIndex] = arr[i];arr[i] = temp;}}}```（3）插入排序```javapublic class InsertionSort {public static void insertionSort(int[] arr) { int n = arr.length;for (int i = 1; i < n; i++) {int key = arr[i];int j = i - 1;while (j >= 0 && arr[j] > key) {arr[j + 1] = arr[j];j--;}arr[j + 1] = key;}}}```（4）快速排序```javapublic class QuickSort {public static void quickSort(int[] arr, int low, int high) { if (low < high) {int pivot = partition(arr, low, high);quickSort(arr, low, pivot - 1);quickSort(arr, pivot + 1, high);}}public static int partition(int[] arr, int low, int high) { int pivot = arr[high];int i = (low - 1);for (int j = low; j < high; j++) {if (arr[j] < pivot) {i++;int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}int temp = arr[i + 1];arr[i + 1] = arr[high];arr[high] = temp;return i + 1;}}```3. 对排序结果进行分析为了验证排序算法的正确性，我们分别对四个排序算法进行了测试。
一、实验目的1. 理解数据排序的基本概念和原理。
2. 掌握常见的数据排序算法，如冒泡排序、选择排序、插入排序、快速排序等。
3. 比较不同排序算法的效率，分析其适用场景。
4. 通过实验验证排序算法的正确性和性能。
二、实验环境1. 操作系统：Windows 102. 编程语言：Python3.73. 数据集：随机生成10000个整数，范围在1到100000之间。
三、实验内容1. 设计数据排序实验，包括冒泡排序、选择排序、插入排序、快速排序四种算法。
2. 实现四种排序算法的Python代码。
3. 比较四种排序算法的时间复杂度和空间复杂度。
4. 对随机生成的数据集进行排序，并记录每种算法的执行时间。
四、实验步骤1. 导入Python中的random模块，用于生成随机数据集。
2. 定义冒泡排序、选择排序、插入排序、快速排序四种算法的函数。
3. 生成随机数据集，并记录数据集的大小。
4. 分别调用四种排序算法对数据集进行排序，并记录每种算法的执行时间。
5. 分析四种排序算法的时间复杂度和空间复杂度，比较其效率。
五、实验结果与分析1. 数据集大小：10000个整数，范围在1到100000之间。
2. 冒泡排序：- 时间复杂度：O(n^2)- 空间复杂度：O(1)- 执行时间：约3.2秒3. 选择排序：- 时间复杂度：O(n^2)- 空间复杂度：O(1)- 执行时间：约3.5秒4. 插入排序：- 时间复杂度：O(n^2)- 空间复杂度：O(1)- 执行时间：约3.0秒5. 快速排序：- 时间复杂度：O(nlogn)- 空间复杂度：O(logn)- 执行时间：约0.8秒分析：从实验结果可以看出，快速排序在处理大量数据时具有更高的效率，其执行时间最短。
冒泡排序、选择排序和插入排序的时间复杂度均为O(n^2)，在数据量较大时效率较低。
快速排序的时间复杂度为O(nlogn)，在处理大量数据时具有较好的性能。
六、实验结论1. 掌握了数据排序的基本概念和原理。
数据结构排序算法综合实验报告姓名： xx x x班级： 10电信1 学号： xxx 指导老师：胡圣荣日期： 2012.12.15～2013.1.5 华南农业大学工程学院算法基本思想：1、插入排序：每次将一个待排序的记录，按其关键字大小插入到前面已经排序好的序列中的适当位置，直到全部记录插入完毕为止。
（1）直接插入排序：在排序过程中，每次都讲无序区中第一条记录插入到有序区中适当位置，使其仍保持有序。
初始时，取第一条记录为有序区，其他记录为无序区。
显然，随着排序过程的进行，有序区不断扩大，无序区不断缩小。
最终无序区变为空，有序区中包含了所有的记录，排序结束。
（2）希尔排序：将排序表分成若干组，所有相隔为某个“增量”的记录为一组，在各组进行直接插入排序；初始时增量d1较大，分组较多（每组的记录数少），以后增量逐渐减少，分组减少（每组的记录数增多），直到最后增量为1（d1>d2>...>dt=1）,所有记录放为一组，再整体进行一次直接插入排序。
2、交换排序：每次比较两个待排序的记录，如果发现他们关键字的次序与排序要求相反时就交换两者的位置，直到没有反序的记录为止。
（1）冒泡排序：设想排序表R[1]到R[n]垂直放置，将每个记录R[i]看作是重量为R[i].key 的气泡；根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R，凡违反本原则的轻气泡，就使其向上“漂浮”，如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。
（2）快速排序：在待排序的n个记录中任取一个作为“基准”，将其与记录分为两组，第一组中个记录的键值均小于或等于基准的键值，第二组中个记录的键值均大于或等于基准的键值，而基准就排在这两组中间（这也是该记录的最终位置），这称为一趟快速排序（或一次划分）。
对所分成的两组重复上述方法，直到所有记录都排在适当位置为止。
3、选择排序：每次从待排序的记录中选出关键字最小（或最大）的记录，顺序放在已排好序的子序列的后面（或最前），直到全部记录排序完毕。
（1）直接选择排序：首先，所有记录组成初始无序区R[1]到R[n]，从中选出键值最小的记录，与无序区第一个记录R[1]交换；新的无序区为R[2]到R[n]，从中再选出键值最小的记录，与无序区第一个记录R[2]交换；类似，第i趟排序时R[1]到R[i-1]是有序区，无序区为R[i]到R[n]，从中选出键值最小的记录，将它与无序区第一个记录R[i]交换，R[1]到R[i]变为新的有序区。
因为每趟排序都使有序区中增加一个记录，所以，进行n-1趟排序后，整个排序表就全部有序了。
（2）堆排序：利用小根堆（或大根堆）来选取当前无序区中关键字最小（或最大）的记录来实现排序的。
下面介绍利用大根堆来排序。
首先，将初始无序区调整为一个大根堆，输出关键字最大的堆顶记录后，将剩下的n-1个记录在重建为堆，于是便得到次小值。
如此反复执行，知道全部元素输出完，从而得到一个有序序列。
4、并归排序：指将若干个已排序的子表合成一个有序表。
（1）二路并归排序：开始时，将排序表R[1]到R[n]看成n个长度为1的有序子表，把这些子表两两并归，便得到n/2个有序的子表（当n为奇数时，并归后仍是有一个长度为1的子表）；然后，再把这n/2个有序的子表两两并归，如此反复，直到最后得到一个程度为n的有序表为止。
各种排序实验结果：实验结果原因分析和结论：1.插入、冒泡排序的速度较慢，但参加排序的序列局部或整体有序时，这种排序能达到较快的速度。
反而在这种情况下，快速排序反而慢了。
当n较小时，对稳定性不作要求时宜用选择排序，对稳定性有要求时宜用插入或冒泡排序。
若待排序的记录的关键字在一个明显有限围时,且空间允许是用桶排序。
当n较大时，关键字元素比较随机，对稳定性没要求宜用快速排序。
当n较大时，关键字元素可能出现本身是有序的，对稳定性有要求时，空间允许的情况下。
宜用归并排序。
当n较大时，关键字元素可能出现本身是有序的，对稳定性没有要求时宜用堆排序。
2.插入排序、冒泡排序、选择排序的时间复杂性为O(n2)其它非线形排序的时间复杂性为O(nlog2n)线形排序的时间复杂性为O(n);3.在算法运行期间，运行QQ软件、360安全卫士、360杀毒、word文档、ppt、酷狗等软件会影响绝对时间和逻辑时间，使时间增大4.随着n的取值增大，算法的实际时间增长速度逐渐增大。
5.直接插入排序（有、无监视哨）、冒泡排序（上升、下沉）、堆排序（递归、非递归）的关键字比较次数相同，但绝对时间相差比较大；直接选择排序与冒泡排序的关键字比较次数相近。
6.相比较其他同学的数据，直接插入（有、无监视哨），直接选择，冒泡（上升、下沉）的结果相差较小，希尔选择结果相差很大，另快速（递归），堆（递归，非递归），二路归并（非递归）结果并不会受计算机环境而不同。
附录：源程序极其代码#define CPP C++#define MPP M++#define MP2 M+=2#define MP3 M+=3#include <fstream.h>#include <iomanip.h>#include <stdlib.h>#include <time.h>#include <math.h>const int maxsize=20000; //排序表容量typedef int datatype;typedef struct {datatype key; //关键字域// othertype other; //其它域} rectype; //记录类型typedef rectype list[maxsize+2]; //排序表类型，0号单元不用__int64 C,M; //比较和移动次数void check(list R,int n) { //检验排序结果int i;for(i=2;i<=n;i++)if(R[i].key<R[i-1].key) {cout<<"Error!\n";return;}cout<<"Correct! ";}void disp(list R,int n) { //显示排序后的结果int i;for(i=1;i<=n;i++) {cout<<setw(4)<<R[i].key<<" ";// if(i%20==0) cout<<endl;}cout<<endl;}void InsertSort1(list R,int n) {//直接插入排序，带监视哨(并不改变关键字次数)int i,j;for(i=2;i<=n;i++) { //依次插入R[2],R[3],…,R[n]if(CPP,R[i].key>=R[i-1].key) continue;//R[i]大于有序区最后一个记录，则本趟不需插入MPP,R[0]=R[i]; //R[0]是监视哨j=i-1;do { //查找R[i]的插入位置MPP,R[j+1]=R[j];j--; //记录后移，继续向前搜索} while(CPP,R[0].key<R[j].key);MPP,R[j+1]=R[0]; //插入R[i]}}void InsertSort2(list R,int n) {//直接插入排序，无监视哨int i,j;rectype x; //x为辅助量(用R[0]代替时间变长)for(i=2;i<=n;i++) { //进行n-1次插入if(CPP,R[i].key>=R[i-1].key) continue;MPP,x=R[i]; //待排记录暂存到xj=i-1;do { //顺序比较和移动MPP,R[j+1]=R[j];j--;} while(j>=1 && (CPP,x.key<R[j].key));MPP,R[j+1]=x; //插入R[i]}}void ShellSort1(list R,int n){//一趟插入排序，h为本趟增量int h,i,j,k;for(h=n/2;h>=1;h=h/2){for(i=1;i<=h;i++){ //i为组号for(j=i+h;j<=n;j+=h){ //每组从第2个记录开始插入if(CPP,R[j].key>=R[j-h].key) continue;//R[j]大于有序区最后一个记录，//则不需要插入MPP,R[0]=R[j]; //R[0]保存待插入记录，但不是监视哨k=j-h; //待插记录的前一个记录do{ //查找正确的插入位置MPP,R[k+h]=R[k];k=k-h;//后移记录，继续向前搜索}while(k>0&&(CPP,R[0].key<R[k].key));MPP,R[k+h]=R[0]; //插入R[j]}}if(h==1) break;}}void SelectSort1(list R,int n){int i,j,k;for(i=1;i<=n-1;i++){//n-1趟排序k=i;for(j=i+1;j<=n;j++)//在当前无序区从前向后找键值最小的记录R[k] if(R[j].key<R[k].key) k=j;if(k!=i){R[0]=R[i];R[i]=R[k];R[k]=R[0];}//交换R[i]和R[0]，R[0]作辅助量 }}void BubbleSort1(list R,int n) {//上升法冒泡排序int i,j,flag;rectype x; //x为辅助量(可用R[0]代替)for(i=1;i<=n-1;i++) { //做n-1趟扫描flag=0; //置未交换标志for(j=n;j>=i+1;j--) //从下向上扫描if(CPP,R[j].key<R[j-1].key) { //交换记录flag=1;MP3,x=R[j];R[j]=R[j-1];R[j-1]=x;//交换}if(!flag) break; //本趟未交换过记录，排序结束}}void BubbleSort2(list R,int n) {//下沉法，冒泡排序int i,j,flag;rectype x; //x为辅助量(可用R[0]代替)for(i=1;i<=n-1;i++) { //做n-1趟扫描flag=0; //置未交换标志for(j=1;j<=n-i;j++) //从上向下扫描if(CPP,R[j].key>R[j+1].key) {//交换记录flag=1;MP3,x=R[j];R[j]=R[j+1];R[j+1]=x;//交换}if(!flag) break; //本趟未交换过记录，排序结束}}int Partition(list R,int p,int q) {//对R[p]到R[q]划分，返回基准位置int i,j;rectype x; //辅助量(可用R[0]代替)i=p;j=q;MPP,x=R[p]; //x存基准(无序区第一个记录)do {while((CPP,R[j].key>=x.key) && i<j) j--;//从右向左扫描(取消=变快)if(i<j) {MPP,R[i]=R[j];i++;} //交换R[i]和R[j]while((CPP,R[i].key<=x.key) && i<j) i++;//从左向右扫描if(i<j) {MPP,R[j]=R[i];j--;} //交换R[i]和R[j]} while(i<j);MPP,R[i]=x; //基准移到最终位置return i; //最后i=j}void QuickSort1(list R,int s,int t) {//对R[s]到R[t]快速排序，递归算法mint i;if(s>=t) return; //只有一个记录或无记录时无需排序i=Partition(R,s,t); //对R[s]到R[t]做划分QuickSort1(R,s,i-1); //递归处理左区间QuickSort1(R,i+1,t); //递归处理右区间}void Sift1(list R,int p,int q){ //堆围为R[p]~R[q],调整R[p]为堆，非递归算法int j;MPP,R[0]=R[p]; //R[0]作辅助量j=2*p; //j指向R[p]的左孩子while(j<=q){if(j<q && (CPP,R[j].key<R[j+1].key)) j++; //j指向R[p]的右孩子if(CPP,R[0].key>=R[j].key) break; //根结点键值大于孩子结点，已经是堆，调整结束MPP,R[p]=R[j]; //将R[j]换到双亲位置上p=j; //修改当前被调整结点j=2*p; //j指向R[p]的左孩子}MPP,R[p]=R[0]; //原根结点放入正确位置}void Sift2(list R,int p,int q){ //堆围为R[p]~R[q],调整R[p]为堆，递归算法int j;if(p>=q) return; //只有一个元素或无元素j=2*p;if(j>q) return;if(j<q && (CPP,R[j].key<R[j+1].key)) j++; //j指向R[p]的右孩子if(CPP,R[p].key>=R[j].key) return; //根结点关键字已最大MPP,R[0]=R[j]; //交换R[j]和R[p]，R[0]作辅助量MPP,R[j]=R[p];MPP,R[p]=R[0];Sift2(R,j,q); //递归}void HeadSort1(list R,int n){ //堆R[1]到R[n]进行堆排序int i;for(i=n/2;i>=1;i--) Sift1(R,i,n); //建初始堆for(i=n;i>=2;i--){ //进行n-1趟堆排序MPP,R[0]=R[1]; //堆顶和当前堆底交换，R[0]作辅助量MPP,R[1]=R[i];MPP,R[i]=R[0];Sift1(R,1,i-1); //R[1]到R[i-1]重建成新堆}}void HeadSort2(list R,int n){ //堆R[1]到R[n]进行堆排序int i;for(i=n/2;i>=1;i--) Sift2(R,i,n); //建初始堆for(i=n;i>=2;i--){ //进行n-1趟堆排序MPP,R[0]=R[1]; //堆顶和当前堆底交换，R[0]作辅助量MPP,R[1]=R[i];MPP,R[i]=R[0];Sift2(R,1,i-1); //R[1]到R[i-1]重建成新堆}}void Merge(list R,list R1,int low,int mid,int high) {//合并R的两个子表：R[low]~R[mid]、R[mid+1]~R[high]，结果在R1中int i,j,k;i=low;j=mid+1;k=low;while(i<=mid && j<=high)if(CPP,R[i].key<=R[j].key) MPP,R1[k++]=R[i++]; //取小者复制else MPP,R1[k++]=R[j++];while(i<=mid) MPP,R1[k++]=R[i++]; //复制左子表的剩余记录while(j<=high) MPP,R1[k++]=R[j++]; //复制右子表的剩余记录}void MergePass(list R,list R1,int n,int len) {//对R做一趟归并，结果在R1中 int i,j;i=1; //i指向第一对子表的起始点while(i+2*len-1<=n) { //归并长度为len的两个子表Merge(R,R1,i,i+len-1,i+2*len-1);i=i+2*len; //i指向下一对子表起始点}if(i+len-1<n) //剩下两个子表，其中一个长度小于lenMerge(R,R1,i,i+len-1,n);else //子表个数为奇数,剩一段for(j=i;j<=n;j++) //将最后一个子表复制到R1中MPP,R1[j]=R[j];}void MergeSort(list R,list R1,int n) {//对R二路归并排序，结果在R中(非递归算法) int len;len=1;while(len<n) {MergePass(R,R1,n,len);len=len*2; //一趟归并，结果在R1中MergePass(R1,R,n,len);len=len*2; //再次归并，结果在R中}}int random1(int num) {return rand();} //0~RAND_MAX=32767int random3(int num) {//素数模乘同余法,0~Mint A=16807; // 16807,39722040,764261123,630360016 48271?int M=2147483647; //有符号4字节最大素数,2^31-1int Q=M/A;int R=M%A;static int x=1,n=0,g=0; //seed(set to 1)static double r,r1=0,r2=0;int x1;x1=A*(x%Q)-R*(x/Q);if(x1>=0) x=x1;else x=x1+M;r=1.*x/M;if(r>0.5) g++;n++;r1+=r;r2+=r*r;if(n%maxsize==0) {cout<<"x="<<r<<" "<<g<<" "<<"n="<<n<<" "<<r1/n<<" "<<r2/n<<" "<<(r2-r1)/n+.25<<endl;}return x;}void main() {rectype *R,*R1,*S; //R1用于归并排序的辅助存储，S用于保存初始排序数据 R=new list;if(R==NULL) {cout<<"数组太大!\n";exit(-1);}R1=new list;if(R1==NULL) {cout<<"数组太大!\n";exit(-1);}S=new list;if(S==NULL) {cout<<"数组太大!\n";exit(-1);}int i,n=maxsize;int choice;clock_t t1,t2;// float s,t;// 正序序列// for(i=1;i<=n;i++)// S[i].key=i;//反序序列// for(i=1;i<=n;i++)// S[i].key=n-i+1;// srand( (unsigned)time( NULL ) );for(i=1;i<=n;i++)S[i].key=random3(n); //生成0-n之间的随机数do {C=M=0;for(i=1;i<=n;i++)R[i].key=S[i].key; //取出初始数据用于排序cout<<"选择排序方法(0: 退出): \n\ 11：直接插入(带监视哨) 12：直接插入(无监视哨) \n\ 21：希尔排序(无监视哨) \n\ 31：直接选择 \n\ 41：冒泡(上升) 42：冒泡(下沉） \n\ 51：快速(递归) \n\ 61：堆排序(非递归) 62:堆排序(递归) \n\ 71：二路归并(非递归) \n"; cin>>choice;switch(choice) {case 11:t1=clock();InsertSort1(R,n);t2=clock();break;case 12:t1=clock();InsertSort2(R,n);t2=clock();break;case 21:t1=clock();ShellSort1(R,n);t2=clock();break;case 31:t1=clock();SelectSort1(R,n);t2=clock();break;case 41:t1=clock();BubbleSort1(R,n);t2=clock();break;case 42:t1=clock();BubbleSort2(R,n);t2=clock();break;case 51:t1=clock();QuickSort1(R,1,n);t2=clock();break;case 61:t1=clock();HeadSort1(R,n);t2=clock();break;case 62:t1=clock();HeadSort2(R,n);t2=clock();break;case 71:t1=clock();MergeSort(R,R1,n);t2=clock();break;default:;}check(R,n);//disp(R,n);cout<<" C="<<C/1e6<<" M="<<M/1e6<<" C+M="<<(C+M)/1e6; cout<<" 时间："<<float(t2-t1)/CLK_TCK<<endl;} while(choice!=0);delete R;delete S;// delete R1; }。
