链表实现排序算法

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

第9页

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

4. 总结

本次实验进行了使用链表存储结构实现插入排序、冒泡排序、快速排序、简单选择排序的编程。这使我对不同的排序方法有了更加深刻的理解和认识。从中也体会到不同的排序方式所耗费的时间复杂度实在是大相径庭，这警示我们，编写一个时间复杂度小的排序函数在进行排序操作时，起着至关重要的作用。

完整代码如下： #include #include using namespace std; struct Node {

int data;

struct Node*next; struct Node*previor; };

class LinkList {

private:

Node* partion(Node*first,Node*end); //快速排序一趟

第10页

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

public:

Node*front; int comparision; //比较次数 int movement; //移动次数 LinkList() //无参构造 { front = new Node; front->next = NULL; front->previor = NULL; comparision = movement = 0;

}

LinkList(int a[],int n); void insertsort(); void bubblesort(); void Qsort(Node*x,Node*y); void selectsort(); void show(); ~LinkList(); };

LinkList::LinkList(int a[],int n) {

front = new Node; front->next = NULL; front->previor = NULL;

comparision = movement = 0; Node*x = new Node; Node*s = new Node; s->data = a[n - 1]; s->next = front; s->previor = front; front->next = s; front->previor = s; x = s;

for (int i = n - 2; i >= 0; i--) { Node*s = new Node; s->data = a[i]; s->next = front->next; s->previor = front;

第11页

//构造函数:建立双向链表 //插入排序 //冒泡排序 //快速排序 //简单选择排序 //显示排序结果 //析构函数 北京邮电大学信息与通信工程学院

front->next = s; x->previor = s; x = s; } }

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; movement++; }

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

void LinkList::insertsort() {

Node*p = front->next; Node*s = p->next; while (s!=front) { if (s->data < p->data) {

第12页