数据结构与算法 -- 普通链表的插入、冒泡排序、选择排序方法(c++实现)

王朝c/c++·作者佚名  2006-01-09
窄屏简体版  字體: |||超大  

template<class T>

class ChainNode{

friend Chain<T>;

template <class T> friend ostream& operator<<(ostream& os, const Chain<T>& c);

private:

T data;

ChainNode<T>* link;

};

template<class T>

class Chain{

friend ChainIterator<T>;

private:

ChainNode<T>* first;

bool Bubble(ChainNode<T>* current); // 递归函数,从链表的最后一对数开始冒泡至current

pubilc:

void InsertionSort(); //插入算法对链表进行升序排序,不得创建新结点和删除老结点

void BubbleSort(); // 冒泡排序

void SelectionSort(); // 选择排序

void RankSort(); // 计数排序

};

template <class T>

void Chain<T>::InsertionSort() //插入算法对链表进行升序排序,不创建新结点和删除老结点

{

if (first)

for (ChainNode<T>* current = first; current->link;){ // current->link为当前要插入的数据

for (ChainNode<T>* p = first; p->data < current->link->data; p = p->link); // p指向表中第一个大于或等于当前要插入数据的数据

if (p == current->link){ // 表中没有比current->link大的数据

current = current->link;

continue; // 继续下一个数据插入

}

if (p!= current){ // 将要插入的数据挪到第一个比它大的数后面

ChainNode<T>* n = current->link->link;

current->link->link = p->link;

p->link = current->link;

current->link = n;

}

else

current = current->link; // 如果已经在第一个比他大的数后面了,更新current->link

T x = p->link->data; //交换要插入元素和他前面那个比它大的元素

p->link->data = p->data;

p->data = x;

}

}

// 问题1:插入排序对于已排好序的链表仍需检验n(n - 1)次,能否及时终止插入排序?

template <class T>

bool Chain<T>::Bubble(ChainNode<T>* current) // 递归函数,从链表的最后一对数开始冒泡至current

{

bool sorted = true; // 如果链表已排好序(未发生交换),返回true

if (current && current->link && current->link->link)

sorted = Bubble(current->link);

if (current->data > current->link->data){

T temp = current->data;

current->data = current->link->data;

current->link->data = temp;

sorted = false;

}

return sorted;

}

template <class T>

void Chain<T>::BubbleSort() // 冒泡排序

{

bool sorted = false;

for (ChainNode<T>* start = first; start && start->link && !sorted; start = start->link)

sorted = Bubble(start);

}

问题2:不使用递归函数能否以同样的检索次数排序?

template <class T>

void Chain<T>::SelectionSort() // 选择排序

{

bool sorted = false;

for (ChainNode<T>* start = first; start && start->link && !sorted; start = start->link){

sorted = true;

for (ChainNode<T>* current = start->link; current; current = current->link){

if (current->data < start->data){ // 交换

T temp = current->data;

current->data = start->data;

start->data = temp;

}

if (sorted && current->link &&current->data > current->link->data) // 如果在链表中存在比后一项大的项,则表示未排序

sorted = false;

}

}

}

问题三:现在每次我遇到比start大的节点都要交换,能否在每一趟检索过程中最多交换一次?

原创,欢迎指出不妥之处。

我的三个问题麻烦高手解答。

如果您有更好的排序方法,请发给我一分Leaf_jo@msn.com 谢谢!

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
 
 
© 2005- 王朝網路 版權所有 導航