基于姓名排序算法动态演示系统的设计与实现毕业设计说明书(编辑修改稿)

基于姓名排序算法动态演示系统的设计与实现毕业设计说明书(编辑修改稿)内容摘要：

效率最高，其最好情况时间复杂度为 O(nlog2n)；反之，如果每次分划操作所产生的两个子序列，其中之一为空序列，此时，快速排序效率最低，其最坏情况时间复杂度为 O(n2)。 如果选择左边第一个元素为主元，则快速排序的最坏情况发生在原始序列正向有序或反向有序时。 快速排序的平均情况时间复杂度为O(nlog2n)。 选择排序 (1) 基本原理 待排序的一组数据元素中，选出最小的 一个数据元素与第一个位置的数据元素交换；然后在剩下的数据元素当中再找最小的与第二个位置的数据元素交换，循环到只剩下最后一个数据元素为止，依次类推直到所有记录 [12]。 排序示例见图。 图 选择排序示例 (2)算法描述 对字符串顺序链表 src作选择排序，返回值为空。 public void selectSort(String[] src){ for (int i = 0。 i。 i++) { int j = selectMinKey(src, i)。 if (j != i) { String temp = src[i]。 src[i] = src[j]。 src[j] = temp。 }} } (3)时间复杂度分析 该算法运行时间与元素的初始排列无关。 不论初始排列如何，该算法都必须执行 n1 趟，每趟执行 ni1 次关键字的比较，这样总的比较次数为：所以，简单选择排序的最好、最坏和平均情况的时间复杂度都为 O(n2)。 陕西理工学院毕业设计 第 9 页 共 80 页 归并排序 (1) 基本原理 是将两个或两个以上的有序表组合成一个有序的表。 利用归并思想实现排序，假 设初始序列含有 n/2 个长度为 2 或 1 的有序子列表；再两两归并， ......，如此重复直到得到长度为 n的有序列表为止；排序示例见图。 图 归并排序示例 (2) 算法描述 将有序顺序链表 sr[i...m]和 sr[m+1...n]归并为有序的 sr[i...n] private void merge(String[] sr,int s,int m,int t){ String[] tmp = new String[t s +1]。 //临时数据存储 int i=s, k = 0,j = m+1。 for(。 i=m amp。 amp。 j = t。 k++) { if(sr[i].pareTo(sr[j])0){ tmp[k] = sr[i]。 i++。 }else { tmp[k] = sr[j]。 j++。 } }//for end if(i = m){ //将剩余的 sr[i...m]复制到 tmp中 for(。 i = m。 i++){ tmp[k] = sr[i]。 k++。 }//for end }//if end if(j = t){ //将剩余的 sr[j...t]复制到 tmp中 for(。 j = t。 j++){ tmp[k] = sr[j]。 k++。 }//for end }//if end (tmp, 0, sr, s, )。 } (3) 时间复杂度分析 陕西理工学院毕业设计 第 10 页 共 80 页 一趟归并排序的操作是，调用 n/2h 次算法 merge 将 sr[1...n]中前后相邻且长度为 h 的有序段进行两两 归并得到前后相邻，长度为 2h 的有序段并存放在 Tr[1 ... n]中整个归并排序需进行 log2n趟，可见需要和待排序等数量的辅助空间，其时间复杂度为 O(nlogn) 链表插入排序 (1) 基本原理 设数组中下标为 0 的分量为表头结点，并令表头结点记录的关键字取最大整数 MAX，则表的插入过程描述如下：首先将静态链表中的数组下标为 1 的分量和表头结点构成一个循环链表，然后依次将下标为 2 至 n 的分量按记录关键字非递减有序插入到循环链表中 [1]。 排序示例见图。 图 链表插入排序示例 (2) 算法描述 对有序 静态链表 nodes作链表插入排序，返回值为空。 private void updateNext(Node[] nodes) { for (int i = 2。 i。 i++) { int q = 0。 int p = nodes[0].getNext()。 while (nodes[i].getValue().pareTo(nodes[p].getValue()) 0) { q = p。 p = nodes[p].getNext()。 } nodes[q].setNext(i)。 nodes[i].setNext(p)。 } } (3) 时间复杂度分析 陕西理工学院毕业设计 第 11 页 共 80 页 和直接插入排序相比，不同之处仅是以修改 2n 次指针值代替移动记录，排序过程中所需进行的关键字间的比较次数相同，因此，表插入排序的时间复杂度仍是 O(n2)； 堆排序 (1) 基本原理 堆含义表明，所有非终点结点的值均不大于（或不小于）其左右孩子结点；若输出堆顶的最小值之后，使得剩余 n1个元素的序列重又建成一个堆，则得到 n个元素中 的次小值，如此反复执行，便得到一个有序序列；堆排序解决 2个问题： ； 顶之后，调整剩余元素成为一个新的堆； 堆调整示例见图。 图 堆调整示例 (2) 算法描述 已知字符串顺序链表 num[s...m]中记录的关键字除 num[s]之外均满足堆的定义，本函数调整num[s]的关键字，使 num[s...m]成为一个大顶堆。 public void adjustHeap(String[] num, int s, int t) { int i = s。 for (int j = 2 * i。 j = t。 j = 2 * j) { if (j t amp。 amp。 num[j].pareTo(num[j + 1])0) j = j + 1。 // 找出较大者把较大者给 num[i] if (num[i].pareTo(num[j])0) break。 String x = num[i]。 num[i] = num[j]。 num[j] = x。 i = j。 } } 陕西理工学院毕业设计 第 12 页 共 80 页 (3) 时间复杂 度分析 堆排序的时间，主要由建立初始堆和反复重建堆这两部分的时间开销构成，它们均是通过调用Heapify 实现的。 堆排序的最坏时间复杂度为 O(nlogn)。 堆排序的平均性能较接近于最坏性能。 由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。 堆排序是不稳定的，算法时间复杂度 O(nlogn)。 基数排序（ MSD） (1) 基本原理 是一种借助多关键字排序的思想对单逻辑关键字进行排序的方法； MSD：先对最主要位关键字K0 进行排序，将序列分成若干子序列，每个子序列中的记录都具有相同的 K0 值，然后分别就 每个子序列对关键字 K1 进行排序，按 K1 值得不同再分成若干更小的子序列，依次重复直至每个子序列中都有相同的关键字 [1]。 排序示例见图。 图 MSD 排序示例 (2) 算法描述 对字符串顺序链表 data每个关键字第 power的字符比较排序，返回值为空。 public void msd(String[] data, int power) { String[][] temp = new String[26][]。 int[] order = new int[26]。 int pos = 0。 int k = 0。 if (power 0) return。 for (int i = 0。 i。 i++) { if (data[i] == null || .equals(data[i])) break。 if (power data[i].length()) { pos = (int) data[i].charAt(power) 97。 } else { pos = 0。 } 陕西理工学院毕业设计 第 13 页 共 80 页 temp[pos][order[pos]] = data[i]。 order[pos]++。 } ++power。 for (int i = 0。 i 26。 i++) { if (order[i] 1 amp。 amp。 power getStringMaxLength(temp[i])) { (1)。 msd(temp[i], power)。 // msd in every sibling bucks } } for (int i = 0。 i 26。 i++) { for (int j = 0。 j。 j++) { if (temp[i][j] != null) { data[k++] = temp[i][j]。 // regain the sorted numbers } } } } (3) 时间复杂度分析 对于 n 个记录（假设每个记录含 d 个关键字，每个关键字的取值范围为 rd 个值），时间复杂度为 O(d(n+rd)),其中每一 趟分配的时间复杂度为 O(n),辅助存储 O(rd)。 陕西理工学院毕业设计 第 14 页 共 80 页 3 系统设计 系统模块结构 根据需求分析，按功能划分 8 个模块，分别是：链表插入排序模块、直接插入排序模块、折半插入排序模块、选择排序模块、归并排序模块、堆排序模块、基数排序模块。 排序算法动态演示系统功能模块结构图如图 所示。 图 系统模块结构图 模块算法流程图 (1) 直接插入排序 直接插入排序算法流程图如图 所示。 开 始i s r c . l e n g t hi = 2s r c [ 0 ] = s r c [ i ]。 s r c [ i ] = s r c [ i 1 ]。 i n t j = i 2。 s r c [ 0 ] s r c [ j ]s r c [ j + 1 ] = s r c [ j ]s r c [ j + 1 ] = s r c [ 0 ]。 结 束YNNs r c [ i ] s r c [ i 1 ]YNYY 图 直接插入排序算法流程图 排序算法动态演示系统 链 表 插 入 排 序 直 接 插 入 排 序 折 半 插 入 排 序 交 换 排 序 选 择 排 序 归 并 排 序 堆 排 序 基 数 排 序 陕西理工学院毕业设计 第 15 页 共 80 页 (2) 折半插入排序 折半插入排序算法流程图如图 所示。 开 始i s r c .l e n g t h初 始 化s r c [ 0 ] = s r c [ i ]。 l o w = 1 , h i g h = i 1。 l o w = h i g hm = ( l o w + h i g h ) / 2。 s r c [ 0 ] s r c [ m ]j 从 i 1 到 h i g h + 1s r c [ j + 1 ] = s r c [ j ]。 s r c [ h i g h + 1 ] = s r c [ 0 ]。 h i g h = m 1。 l o w = m + 1。 结 束YYYNNN 图 折半插入排序算法流程图 (3) 选择排序 选择排序算法流程图如图 所示。 陕西理工学院毕业设计 第 16 页 共 80 页 开 始i s r c .l e n g t h初 始 化j = s e l e c t M i n K e y ( s r c , i )。 j ! = it e m p = s r c [ i ]。 s r c [ i ] =。