堆排序、快速排序、基数排序（静态链表）输出一组数组

数据结构程序报告（5）

1. 需求分析：

（1）堆排序、快速排序、基数排序（静态链表）输出一组数组 【1】堆排序：○1对所有纪录建立最大堆

2取出堆顶的最大纪录与数组末端的纪录交换，最大记录在下边n-1的位置，○

原数组末端元素临时处于根结点；将根元素向下调整到合适的位置，即剩下的n-1个记录重新调整为堆，再取新堆顶最大的记录，与数组n-2为交换；…；不断重复这一操作，直到堆为空。这时数组正好是从小到大排序。

【2】快速排序：○1从待排序序列S中任意选择一个记录k作为轴值。

2将剩余的记录分割成左子序列L和右子序列R。 ○

3L中所有记录都小于或等于k，R中记录都大于等于k，因此k正好○

位于正确的位置。

4对子序列L和R递归进行快速排序，直到子序列中只含有0或1个○

元素，推出递归。

【3】基数排序：○1高位优先法（MSD）分配排序。

2低位优先法（LSD）分配排序。 ○

从最低位k0开始排序，对于排好的序列再用次低位k1排序，依次重复，直至对最

高位kd-1排好序后，整个序列成为有序的。这是一个分、收；分、收 ….的过程。 （2）输入输出要求： 输入数组个数：

输入数组： 快速排序： 输入数组个数： 输入数组：

堆排序： 输入数组个数： 输入数组： 基数排序：

2. 算法设计：

（1） QuickSort（）快速排序函数，Array[]为待排序数组，left、right分别为数组两端，

选择轴值p，分割前先将轴值放到数组末端，分割后轴值到达正确位置，对轴值左边和右边的子序列进行递归快速排序。

（2） swap（）交换2个数。

（3） Partition（）分割函数，定义l为左指针，r为右指针，开始分割l、r不断向中间移

动，直到相遇。

（4） MaxHeap（）最大堆类定义，包括BuildHeap（）建堆，LeftChild（）返回左孩

子位置，Shiftdown（）从left开始向下筛选，RemoveMax（） 堆顶删除最大值

（5） sort（）堆排序，依次找出最大记录，即堆顶。

（6） radixsort（）静态链实现基数排序，n为数组长度，d为排序码个数，r为基数。 （7） distribute（）分配过程，A中存放待排序记录，first为静态链中的第一个记录，i

为第i个排序码，r为基数。

（8） collect（）收集过程，Arra中存放待排序记录，first为静态链中的第一个记录，r

为基数。

（9） addrsort（）限行时间整理静态链表，使得数组按下标有序。 附程序：

#include

#include #include using namespace std; #define MAX 100

template

void QuickSort(Record Array[],intleft,int right) //快速排序 { }

template

void swap(Record Array[],intp,int right) {

Record temp; temp=p; p=right;

//交换两个数

if (right<=left) return; int p=(left+right)/2; swap(Array,p,right); p=Partition(Array,left,right); QuickSort(Array,left,p-1); QuickSort(Array,p+1,right);

}

right=temp;

template

int Partition(Record Array[],intleft,int right) //分割函数 { int l=left;

int r=right;

Record TempRecord=Array[r]; while(l!= r){ while(Array[l]<=TempRecord&& l

l++;

if (l

Array[r]=Array[l]; r--;

}

while(Array[r]>=TempRecord&&l

r--;

if (l

l++;