深圳大学算法设计与杨煊实验一讲述.doc

深 圳 大 学 实 验 报 告 课程名称： 算法设计与分析 实验项目名称： 排序算法性能分析 学院： 专业、班级： 指导教师： 杨 烜 报 告 人： 学号： 实验报告提交时间： 2015.4.3 教务处制 一、实验目的与实验环境 实验目的： 1. 掌握选择排序、冒泡排序、合并排序、快速排序、插入排序算法原理 2. 掌握不同排序算法时间效率的经验分析方法，验证理论分析与经验分析的一致性。 实验环境：VC++ 6.0 二、实验原理与算法描述 算法（1）选择排序 SelectSort(A[0...n-1],n) //利用选择排序对给定的数组排序 //输入：一个可排序数组A[0...n-1] //输出：非降序排列的数组A[0...n-1] for i-0 to n-2 do min-i for j-i+1 to n-1 do if A[j]A[min] min-j swap A[i] and A[min] 理论效率：C(n) ∈θ(n^2),不稳定算法 算法（2）快速排序 QuickSort(A[0...n-1],n) //利用快速排序对给定的数组排序 //输入：一个可排序数组A[0...n-1] //输出：非降序排列的数组A[0...n-1] if lr s-Partition(A[l...r]) //s是分裂位置 Quicksort(A[l...s-1]) Quicksort(A[s+1...r]) Partition(A[l...r]) //以第一个数为中轴，对子数组进行分区 //输入：数组A[0...n-1]中的子数组A[l...r]，由左右下标l和r定义 //输出：数组A[l...r]的一个分区，分裂点的未知作为函数的返回值 p-A[l] i-l;j-r+1 repeat repeat i-i+1 until A[i]=P repeat j-j-1 until A[j]=P swap(A[i],A[j]) until i=j swap (A[i],A[j]) //当i=j撤销最后一次交换 swap (A[l],A[j]) return j 理论效率：C(n) ∈θ(nlnn)，不稳定算法 算法（3）合并排序 MergeSort(A[0...n-1]) //利用合并排序对给定的数组排序 //输入：一个可排序数组A[0...n-1] //输出：非降序排列的数组A[0...n-1] if n1 copy A[0...?n/2?-1] to B[0...?n/2?-1] copy A[?n/2?...n-1] to C[0...?n/2?-1] Mergesort(B[0...?n/2?-1]) Mergesort(C[0...?n/2?-1]) Merge(B,C,A) Merge(B[0...p-1],C[0...q-1],A[0...p+q-1]) //将两个有序数组合并为一个有序数组 //输入：两个有序数组B[0...p-1],C[0...q-1] //输出：A[0...p+q-1]中已经有序存放了B和C中的元素 i-0;j-0;k-0 while ip and jq do if B[i]=C[j] A[k]-B[i];i-i+1 else A[k]-C[j];j-j+1 k-k+1 if i=p copy C[j...q-1] to A[k...p+q-1] else copy B[i...p-1] to A[k...p+q-1] 理论效率：C(n)∈θ(nlogn)，稳定算法 算法（4）冒泡排序 BubbleSort(A[0...n