题目来自网络
题目(1):基于数组的快速排序
题目(2):基于链表的快速排序
----
题目(1):基于数组的快速排序
思路:使用分治的思想,先选择枢轴,之后执行一次划分,并把原序列划分两个子序列,之后递归处理。
代码:
int partition(int nArr[],int nStart,int nEnd) { int nKey = nArr[nStart]; while(nStart < nEnd) { while(nStart < nEnd && nArr[nEnd] >= nKey) { nEnd--; } nArr[nStart] = nArr[nEnd]; while(nStart < nEnd && nArr[nStart] <= nKey) { nStart++; } nArr[nEnd] = nArr[nStart]; } nArr[nStart] = nKey; return nStart; } void QSort(int nArr[],int nStart,int nEnd) { if (nStart >= nEnd) { return; } int nLoc = partition(nArr,nStart,nEnd); QSort(nArr,nStart,nLoc - 1); QSort(nArr,nLoc + 1,nEnd); } void QSort(int nArr[],int nLen) { assert(nArr != NULL && nLen > 0); QSort(nArr,0,nLen - 1); }
题目(2)基于链表的快速排序
思路(1)改变结点的值,不破坏链表指向。
代码:
struct ListNode { int m_nData; ListNode* m_pNext; }; /*对区间[pStartNode,pEndNode - 1]之间的结点进行排序*/ ListNode* Partition(ListNode* pStartNode,ListNode* pEndNode) { assert(pStartNode != NULL); int nKey = pStartNode->m_nData; ListNode* pSlow = pStartNode;//链表中结点个数大于等于2 ListNode* pFast = pStartNode->m_pNext; while(pFast != pEndNode) { if (pFast->m_nData < nKey) { pSlow->m_nData = pFast->m_nData; if (pSlow->m_pNext == pFast) { pSlow = pSlow->m_pNext; } else { pSlow = pSlow->m_pNext; pFast->m_nData = pSlow->m_nData; } } pFast = pFast->m_pNext; } //返回分割点位置 pSlow->m_nData = nKey; return pSlow; } void QSort(ListNode* pStartNode,ListNode* pEndNode) { //没有待排序结点或只有一个结点,则可直接返回 if (pStartNode == pEndNode || pStartNode->m_pNext == pEndNode) { return; } ListNode* pKeyPos = Partition(pStartNode,pEndNode); QSort(pStartNode,pKeyPos); QSort(pKeyPos->m_pNext,pEndNode); }
思路(2)不改变结点的值,但改变链表指向。
代码:
struct ListNode { int m_nData; ListNode* m_pNext; }; //*对区间[pStartNode,pEndNode - 1]之间的结点进行排序*/ ListNode* Partition(ListNode* pStartNode,ListNode* pEndNode) { assert(pStartNode != NULL); ListNode* pKeyNode = pStartNode; ListNode* pLessHead = NULL; ListNode* pLastLessList = NULL; ListNode* pLastGreatList = pStartNode; ListNode* pCur = pStartNode->m_pNext; while(pCur != pEndNode) { if (pCur->m_nData > pKeyNode->m_nData) { //插入大于枢轴的链表中 pLastGreatList->m_pNext = pCur; pLastGreatList = pCur; } else { //插入小于枢轴的链表中 if (pLastLessList == NULL) { pLessHead = pCur; pLastLessList = pCur; } else { pLastLessList->m_pNext = pCur; pLastLessList = pCur; } } pCur = pCur->m_pNext; } //两个链表拼接在一起 if (pLessHead != NULL) { pLastLessList->m_pNext = pKeyNode; } else { pLessHead = pKeyNode; } pLastGreatList->m_pNext = pEndNode; //返回第一个结点的地址 return pLessHead; } ListNode* QSort(ListNode* pStartNode,ListNode* pEndNode) { ListNode* pHead = NULL; //没有待排序结点或只有一个结点,则可直接返回 if (pStartNode == pEndNode || pStartNode->m_pNext == pEndNode) { return pStartNode; } ListNode* pNewHead = Partition(pStartNode,pEndNode); pHead = QSort(pNewHead,pStartNode); //此链表第一个结点的地址是链表的首地址,需要返回 pStartNode->m_pNext = QSort(pStartNode->m_pNext,pEndNode);//此链表第一个结点的地址应该放入枢轴的next中 return pHead; }