小米 南京 代工:一步一步写算法（之链表排序）

来源：百度文库 编辑：偶看新闻 时间：2024/05/02 18:10:36

【 声明：版权所有，欢迎转载，请勿用于商业用途。 联系信箱：feixiaoxing @163.com】


相比较线性表的排序而言，链表排序的内容稍微麻烦一点。一方面，你要考虑数据插入的步骤；另外一方面你也要对指针有所顾虑。要是有一步的内容错了，那么操作系统会马上给你弹出一个exception。就链表的特殊性而言，适合于链表的排序有哪些呢？

（1）插入排序 （适合）

（2）冒泡排序 （适合）

（3）希尔排序 （适合）

（4）选择排序 （适合）

（5）快速排序 （不适合）

（6）合并排序 （不适合）

（7）基数排序 （不适合）

（8）堆排序 （不适合）

其实，一般来说。如果涉及到数据之间的相对关系调配，那么只适合线性排序；如果只是数据内容之间的相互交换，那么这种排序方法也比较适合链表的排序。快速排序、合并排序、堆排序都涉及到了中间值的选取问题，所以不大适合链表排序。

为了说明链表排序是怎么进行的，我们可以利用插入排序作为示例，描述链表是怎么进行插入排序的。

a）首先遍历节点，一边是排序好的节点，一边是待排序的节点

view plaincopy to clipboardprint?

  1. void sort_for_link_node(NODE** ppNode)
  2. {
  3. NODE* prev;
  4. NODE* curr;
  6. if(NULL == ppNode || NULL == *ppNode)
  7. return;
  9. curr = (*ppNode) ->next;
  10. (*ppNode) ->next = NULL;
  12. while(curr){
  13. prev = curr;
  14. curr = curr->next;
  15. insert_for_sort_operation(ppNode, prev);
  16. }
  18. return;
  19. }

b）对于待插入的节点，选择合适的位置插入即可

view plaincopy to clipboardprint?

  1. void insert_for_sort_operation(NODE** ppNode, NODE* pNode)
  2. {
  3. NODE* prev;
  4. NODE* cur;
  6. /* 在第一个数据之前插入pNode */
  7. if(pNode->data < (*ppNode)->data){
  8. pNode->next = *ppNode;
  9. *ppNode = pNode;
  10. return;
  11. }
  13. cur = *ppNode;
  14. while(cur){
  15. if(pNode->data < cur->data)
  16. break;
  18. prev = cur;
  19. cur = cur->next;
  20. }
  22. pNode->next = prev->next;
  23. prev->next = pNode;
  24. return;
  25. }
链表的冒泡排序算法 用C语言写一个排序算法。 设计一个用链表表示的简单选择排序的算法，并实现之（试验报告） 结构体排序算法 asp排序算法 什么是起泡排序算法?? 急求一排序算法 合并排序算法 vb选择排序算法 内部排序算法比较 内部排序算法比较 整数排序算法的问题？ 堆排序的具体算法 快速排序的循环算法 求几种排序法的算法 全排序的算法(PASCAL) 一、题目：三种典型排序算法及其比较（直接法、插入法、shell排序比较） 请问有哪位高人知道AOV网的拓扑排序算法(用邻接链表和栈作为存储空间,最好有数据域) 请教算法高手：还是关于排序！ pascal 排序算法的一道选择题。Help！ 给出一种拓扑排序的改进算法 关于数据库排序输出的算法? C语言中排序的算法是什么 用JAVA写出冒泡排序的算法