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