C++程序设计第七章排序.ppt

7.5.2 基数排序 基数排序依次根据各关键字分量进行“分配”、“收集”完成排序 在单关键字排序中，一个关键字可以看作由若干个关键字分量复合而成，如整数可视为若干数位的集合。 基数排序例 7.5.2 基数排序 用数组实现的基数排序算法 void RadixSort(int data[], int n) { const int radix = 10; const int digits = 10;? int i,j,k,factor;? queueint queues[radix]; ? for ( i = 0,factor = 1; i digits;i++,factor *= radix) { for ( j = 0;j n; j++) queues[(data[j]/factor)%radix].push(data[j]); // 分配 for ( k = j = 0; j radix; j++,k++) // 收集 while (!queues[j].empty()){ data[k] = queues[j].front(); queues[j].pop(); } } } 7.5.2 基数排序 用数组实现基数排序的缺点 虽然不需要进行“比较”操作，但仍需要大量的元素移动操作 还需要额外的空间来存放10个队列 链式基数排序 用链表作存储结构的基数排序 7.5.2 基数排序 链式基数排 设置10个队列，front[i]和rear[i]分别为第i个队列的头指针和尾指针 第一趟分配对最低位关键字（个位）进行，改变元素的指针值，将链表中的元素分配至10个链队列中，每个队列记录的关键字的个位相同 第一趟收集是改变所有非空队列的队尾记录的指针域，令其指向下一个非空队列的队头记录，重新将10个队列链成一个链表 重复上述两步，进行第二趟、第三趟分配和收集，分别对十位、百位进行，最后得到一个有序序列 链式基数排序（第一趟）例 静态链表 class SLList { struct Node { int key[DIGITS]; int info; int next; }; friend ostream operator(ostream os, SLList s); public: SLList():data(NULL),length(0){}; ~SLList(); void Arrange(); //重排 void Init(int arr[],int n); void RadixSort(); //链式基数排序 private: void Distribute(int[], int[], int); //分配 void Collection(int[], int[], int); //收集 Node *data; int length; }; 7.5.2 基数排序 void SLList::Distribute(int front[], int rear[], int digit) { int i, index; for (i = 0; i RADIX; i++) front[i] = 0; ? for (i = data[0].next; i 0; i = L.data[i].next){ index = data[i].key / (int)pow(10.0, digit) - data[i].key / (int)pow(10.0, digit + 1) * 10; if (front[index] == 0) front[index] = i; else data[rear[index]].next = i; ? rear[index] = i; } } 链式基数排序 ——“分配”算法 链式基数排序 ——“收集”算法 7.5.2 基数排序 void SLList::Collection(int front[], int rear[], int digit) { int i, c