排序算法
经典排序算法包括： 冒泡、 选择、 和 插入。
下面按照升序排序给出一句话解释：
冒泡 -- 进行N-1次循环， 每次循环从第一个元素开始，将此元素和其后元素比较， 如果前者大，则互换位置， 直到最后一个位置元素被比较， 执行完毕则最大的一个元素在最后一个位置， 类似水中气泡向上冒的过程， 越是向上，气泡越大。
选择 -- 进行N-1次循环， 每次循环， 遍历所有未排序元素，定位最大的一个元素，将其放到尾部， 则最后一个位置保证为最大元素。 定位的过程就是选择。
插入 -- 进行N-1次循环， 每次循环， 取出未排序的第一个元素， 将此元素插入到一个新的有序列表中， 插入过程为从有序列表中第一个元素开始， 找到第一个大于待插入元素的元素， 将 待插入元素插入到此元素前。
数组形式的排序算法例子， 见下面博文：
http://www.cnblogs.com/peggy89321/p/3246466.html
本文给出单链表形式的排序代码：
https://github.com/fanqingsong/code-snippet/blob/master/C/listOrder/listOrder.c
选择排序
/*********************************************************************** selecting sort method ************************************************************************/ // find specific node by strcmpfunc and detach it from list PT_NODE FindAndDetachNode(PT_NODE ptHeadNode, STRCMPFUNC strcmpfunc ) { PT_NODE ptTargetNode = NULL; PT_NODE ptPreMax = NULL; PT_NODE ptCurNode = NULL; PT_NODE ptPreNode = NULL; ptTargetNode = ptHeadNode->next; ptPreMax = ptHeadNode; ptCurNode = ptHeadNode->next; ptPreNode = ptHeadNode; while( ptCurNode ) { // current node string is larger than specific node string, record it if ( strcmpfunc(ptCurNode->str, ptTargetNode->str) ) { ptTargetNode = ptCurNode; ptPreMax = ptPreNode; } ptPreNode = ptCurNode; ptCurNode = ptCurNode->next; } // specific node found, detach it from list if ( ptTargetNode ) { ptPreMax->next = ptTargetNode->next; ptTargetNode->next = NULL; } // return specific node return ptTargetNode; } // sort list by specific order by strcmpfunc void SortListWithSelectMethod(PT_NODE ptHeadNode, STRCMPFUNC strcmpfunc) { T_NODE tNewHead = {NULL, NULL}; PT_NODE ptNode = NULL; // selection sort method while( TRUE ) { // find target node and detach it from list ptNode = FindAndDetachNode(ptHeadNode, strcmpfunc); if ( !ptNode ) { break; } // insert target node into new list from head InsertNode2ListHead(&tNewHead, ptNode); } // reset head node to new list ptHeadNode->next = tNewHead.next; tNewHead.next = NULL; }
冒泡排序
/*********************************************************************** bubble sort method ************************************************************************/ // bubble list by strcmpfunc and detach last from list PT_NODE BubbleAndDetachLast(PT_NODE ptHeadNode, STRCMPFUNC strcmpfunc) { PT_NODE ptCurNode = NULL; PT_NODE ptPreNode = NULL; PT_NODE ptNextNode = NULL; ptCurNode = ptHeadNode->next; ptPreNode = ptHeadNode; while( ptCurNode ) { ptNextNode = ptCurNode->next; // reach list tail if ( !ptNextNode ) { break; } // current node string is larger than next node string, swap it if ( strcmpfunc(ptCurNode->str, ptNextNode->str) ) { ptPreNode->next = ptNextNode; ptCurNode->next = ptNextNode->next; ptNextNode->next = ptCurNode; // reset current node's previous node ptPreNode = ptNextNode; } else { ptPreNode = ptCurNode; ptCurNode = ptCurNode->next; } } //detach current node from list ptPreNode->next = NULL; // current node is the last node, return it return ptCurNode; } // sort list by specific order by strcmpfunc void SortListWithBubbleMethod(PT_NODE ptHeadNode, STRCMPFUNC strcmpfunc) { T_NODE tNewHead = {NULL, NULL}; PT_NODE ptNode = NULL; // selection sort method while( TRUE ) { // bubble list and detach last from list ptNode = BubbleAndDetachLast(ptHeadNode, strcmpfunc); if ( !ptNode ) { break; } // insert max node into new list from head InsertNode2ListHead(&tNewHead, ptNode); } // reset head node to new list ptHeadNode->next = tNewHead.next; tNewHead.next = NULL; }
插入排序
/*********************************************************************** inserting sort method ************************************************************************/ PT_NODE DetachFirstNode(PT_NODE ptHeadNode) { PT_NODE ptFirstNode = NULL; ptFirstNode = ptHeadNode->next; // detach first node from list if ( ptFirstNode ) { ptHeadNode->next = ptFirstNode->next; } return ptFirstNode; } // insert node into list by inserting sort method void InsertNode2ListByInsertMethod(PT_NODE ptHeadNode, PT_NODE ptNode, STRCMPFUNC strcmpfunc) { PT_NODE ptPrevNode = NULL; PT_NODE ptCurNode = NULL; ptPrevNode = ptHeadNode; ptCurNode = ptPrevNode->next; while( ptCurNode ) { if ( strcmpfunc(ptCurNode->str, ptNode->str) ) { ptPrevNode->next = ptNode; ptNode->next = ptCurNode; // insert ok, let's leave break; } else { ptPrevNode = ptCurNode; ptCurNode = ptCurNode->next; } } // current node is NULL, previous node is last node of list, // ie, insert not ok, the node shall be added to tail if ( !ptCurNode ) { ptPrevNode->next = ptNode; ptNode->next = NULL; } } // sort list by specific order by strcmpfunc void SortListWithInsertMethod(PT_NODE ptHeadNode, STRCMPFUNC strcmpfunc) { T_NODE tNewHead = {NULL, NULL}; PT_NODE ptNode = NULL; // selection sort method while( TRUE ) { // get first node from list ptNode = DetachFirstNode(ptHeadNode); if ( !ptNode ) { break; } // insert the node into new list by inserting method InsertNode2ListByInsertMethod(&tNewHead, ptNode, strcmpfunc); } // reset head node to new list ptHeadNode->next = tNewHead.next; tNewHead.next = NULL; }