数据结构之编写冒泡排序算法

错误！未找到引用源。

void BubbleSortDec ( DataType a[], int n ) {

for ( i=0; i

for( j=0; j

if ( not change ) break; // 没有交换则完成排序 } }

错误！未找到引用源。

分析：计算语句频度是计算时间复杂度的基础。可以用观察和归纳进行简单的计算。 1) 问题规模n 执行次数 1 1 2 2+1 3 3+2+1 ... ... n n+...+2+1=n(n+1)/2 结论：语句频度为n(n+1)/2。 2) 问题规模n 执行次数 1 1 2 2 3 2 4 3 ... ...

k

2 k+1 结论：语句频度为?logn??1。

错误！未找到引用源。 void Reverse ( SqList& L ) {

for ( i=0; i

错误！未找到引用源。

思路1：先查找适合插入的位置i

向后移动元素（从后向前处理） 插入元素，表长加1

思路2：从后向前查找插入位置，同时向后移动大于x的元素 插入元素，表长加1 注意：表满时不能插入。 // 顺序表结构

①

用边界值验证法说明对于偶数个元素的表会有何种情况。

const int MAXSIZE = 1024; typedef struct {

DataType elem[MAXSIZE]; int length; } SqList;

// 向非递减有序的顺序表L中插入元素x，仍保持非递减有序 // 插入成功返回true，否则返回false

bool OrderListInsert ( SqList &L, DataType x ) {

if ( L.length==MAXSIZE ) return false; // 表满，插入失败 // 将大于x的元素后移

for ( i=L.length-1; i>=0 && L.elem[i]>x; i--) L.elem[i+1] = L.elem[i];

// 插入x (因为最后执行i--，故应在i+1处) L.elem[i+1] = x; L.length++; return true; }

错误！未找到引用源。

void Remove ( SqList &L, DataType x ) {

i = 0; // 剩余元素个数，同时是下一个元素的插入位置 for ( j=0; j

L.length = i; // 剩余元素个数 }

本算法的时间复杂度为O(n)；若改用反复调用查找和删除算法，时间复杂度会达到O(n2)。

错误！未找到引用源。

思路：设已经唯一化的序列是(a0, … , ai-1)，剩余序列是(aj,…, an)。所要做的就是在已经唯一化的序列L.elem[0..i-1]中查找L.elem[j]，如果未找到则复制到L.elem[i]处。如此重复直到剩余序列为空。 void Unique ( SqList &L ) {

if ( L.length<=1 ) return; // 空表或只有一个元素的表已经唯一化了 i = 1; // 开始L.elem[0..0]是唯一化序列 for ( j=1; j

// 在L.elem[0..i-1]中查找L.elem[j] for ( k=0; k

if ( L.elem[k]==L.elem[j] ) break; if ( k==i ) { // L.elem[j]未出现过，复制到L.elem[i]处 if ( j!=i ) L.elem[i] = L.elem[j]; i++; } }

L.length = i; // 表长为i }

以上算法的时间复杂度为O(n2)。当然，可以反复将重复元素删除达到唯一化，时间复杂度仍是O(n2)，但是与以上算法相比要移动更多元素。

错误！未找到引用源。

分析：由于该表是有序的，相等的元素必然靠在一起，不必从头开始查找，所以算法的时间复杂度可以降低。

思路：类似习题错误！未找到引用源。，但是查找部分只要与L.elem[i-1]比较就可以了。 void Unique ( SqList &L ) {

i = 0; // 开始的唯一化序列为空(○?对比习题错误！未找到引用源。思考为什么不用i=1开始①) for ( j=1; j

if ( L.elem[j]!=L.elem[i-1] ) { // Note：写成L.elem[j]!=L.elem[j-1]亦可 if ( j!=i ) L.elem[i] = L.elem[j]; i++; }

L.length = i; // 表长 }

错误！未找到引用源。

思路：从链上依次取下结点，按照逆序建表的方法(参见2.错误！未找到引用源。错误！未找到引用源。错误！未找到引用源。节)重新建表。 void Reverse ( LinkList &L ) {

p = L->next; // 原链表 L->next = NULL; // 新表(空表) while ( p ) {

// 从原链表中取下结点s s = p;

p = p->next;

// 插入L新表表头 s->next = L->next; L->next = s; } }

错误！未找到引用源。

void InsertionSort ( LinkList &L ) {

h = L->next; // 原链表 L->next = NULL; // 新空表 while ( h ) {

// 从原链表中取下结点s s = h; h = h->next;

①

原因是这里不能确定表是否为空，而习题2.4则用开始的if语句排除了空表的情况。事实上，习题2.4也可以仿照此

处修改，请读者自己完成。

// 在新表中查找插入位置 p = L;

while ( p->next && p->next->data<=s->data ) p = p->next; // 在p之后插入s s->next = p->next; p->next = s; } }

错误！未找到引用源。

void SelectionSort ( LinkList &L ) {

p = L;

while ( p->next ) {

// 选择最小(从p->next至表尾) q = p; // 最小元素的前驱q s = p;

while ( s->next ) {

if ( s->next->data < q->next->data ) q = s; s = s->next; }

m = q->next; // 找到最小m // 最小元素m插入有序序列末尾(p之后) if ( q!=p ) {

q->next = m->next; // 解下最小m m->next = p->next; // 插入p之后 p->next = m; }

p = p->next; // L->next至p为有序序列 } }

错误！未找到引用源。

// 将非递减有序的单链表lb合并入la，保持非递减有序 // 结果la中含有两个链表中所有元素，lb为空表 void Merge ( LinkList &la, LinkList &lb ) {

p = la, q = lb;

while ( p->next and q->next ) { // 跳过la中较小的元素

while ( p->next and (p->next->data <= q->next->data) ) p = p->next;

// 把lb中较小的元素插入la中

while ( p->next and q->next and (q->next->data < p->next->data) ) { s = q->next;

q->next = s->next; s->next = p->next; p->next = s;