北京邮电大学信息与通信工程学院

{ if (s->data < p->data) { comparision++; front->data = s->data; movement++; Node*x = p; Node*y = s; while (front->data < x->data) { comparision++; y->data = x->data; movement++; x = x->previor; y = y->previor; } y->data = front->data; movement++; } comparision++; p = p->next; s = s->next; } }

冒泡排序函数：每一次内循环边比较边交换，将无序区中最大的数放入有序区中，

并记录无序元素的范围。当无序元素指向front时即整体排序完成。

void LinkList::bubblesort() {

Node*s = front->previor; //初始化无序元素位置 while (s != front) { Node*p = s; //本次无序元素位置 s = front; Node*x = front->next; Node*y = x->next; while (x != p) { if (x->data > y->data) { comparision++; front->data = x->data; x->data = y->data; y->data = front->data;

第5页

北京邮电大学信息与通信工程学院

movement = movement + 3; s = x; //更新无序元素位置 } comparision++; x = x->next; y = y->next; } } }

快速排序函数：快速排序函数是个递归调用函数，关键在一次快速排序函数的

编写。选择第一个元素作为分区的轴值，将待排序元素分成左右两个区域，左区的元素都比轴值小，右边的都更大。

然后反复进行此操作，即可完成排序。而结束递归的关键便是 左右分界节点有了直接前后继关系的时候。 void LinkList::Qsort(Node*x,Node*y) { if (x->previor != y) { Node*pivot = partion(x, y); Qsort(x, pivot->previor); Qsort(pivot->next, y); } }

Node* LinkList::partion(Node*first, Node*end) {

int basic = first->data; while (first != end) { while ((first != end) && (end->data >= basic)) { end = end->previor; comparision++; } comparision++; first->data = end->data; movement++; while ((first != end) && (first->data <= basic)) { first = first->next; comparision++; } comparision++; end->data = first->data;

第6页

北京邮电大学信息与通信工程学院

}

movement++; }

first->data = basic; movement++; return first;

简单选择排序函数：是将待排序中最小的元素放置序列最前面，其关键是先

通过循环比较确定最小元素的位置，再进行数据交换，从而大大减少了元素交换的次数。void LinkList::selectsort() {

Node*s = front->next; while (s != front->previor) { Node*p = s->next; Node*record = s; while (p != front) { Node*x = record; if (p->data < x->data) { comparision++; record = p; } comparision++; p = p->next; } if (record != s) { int a = record->data; record->data = s->data; s->data = a; movement = movement + 3; } s = s->next; } }

第7页

北京邮电大学信息与通信工程学院

3. 程序运行结果分析

第8页