堆排序、快速排序、基数排序(静态链表)输出一组数组16页.docx

数据结构程序报告（5） 1. 需求分析：（1）堆排序、快速排序、基数排序（静态链表）输出一组数组【1】堆排序：对所有纪录建立最大堆 取出堆顶的最大纪录与数组末端的纪录交换，最大记录在下边n-1的位置，原数组末端元素临时处于根结点；将根元素向下调整到合适的位置，即剩下的n-1个记录重新调整为堆，再取新堆顶最大的记录，与数组n-2为交换；不断重复这一操作，直到堆为空。这时数组正好是从小到大排序。【2】快速排序：从待排序序列S中任意选择一个记录k作为轴值。将剩余的记录分割成左子序列L和右子序列R。L中所有记录都小于或等于k，R中记录都大于等于k，因此k正好位于正确的位置。对子序列L和R递归进行快速排序，直到子序列中只含有0或1个元素，推出递归。 【3】基数排序：高位优先法（MSD）分配排序。