p*****e
发帖数: 537 | 1 bubble sort应该是可以的，merge sort也是可行的只是比较麻烦。还有别的更好的方
法吗？ | z*********8
发帖数: 2070 | | a**d
发帖数: 85 | | u*****o
发帖数: 1224 | 4 只知道bubble sort怎么做，请问愿意分享merge sort怎么写吗？
【在 z*********8 的大作中提到】
: 没了， 就写个merge sort吧
| p*****3
发帖数: 488 | 5 给个我以前写的吧，快速排序版本的
struct NODE
{
int nVal;
NODE* pNext;
NODE(int n) : nVal(n), pNext(NULL) {}
};
void sort(NODE* pNode, int nLen)
{
if (NULL == pNode || nLen <= 0)
return;
int nCount = 0;
int nPivot = pNode->nVal;
NODE* pPrev = pNode;
NODE* pIterBeg = pPrev->pNext;
NODE* pIterEnd = pIterBeg;
while (NULL != pIterEnd)
{
if (pIterEnd->nVal < nPivot)
{
swap
(pIterBeg->nVal, pIterEnd->nVal);
pPrev = pPrev->pNext;
pIterBeg = pIterBeg->pNext;
nCount++;
}
pIterEnd = pIterEnd->pNext;
}
swap(pNode->nVal, pPrev->nVal);
sort(pNode, nCount);
sort(pIterBeg, nLen - 1 - nCount);
}
NODE* sortLinkedList(NODE* pHead)
{
if (NULL == pHead)
return NULL;
int nLen = 0;
NODE* pIter = pHead;
while (pIter != NULL)
{
pIter = pIter->pNext;
nLen++;
}
sort(pHead, nLen);
return pHead;
} | d******e
发帖数: 164 | 6 void quick_sort(node *&head, node *&tail) {
if (!head) return;
node *lh, *lt, *rh, *rt;
lh = lt = rh = rt = NULL;
for (node *p = head->next; p; p = p->next) {
if (p->val < head->val) {
if (!lh) lh = lt = p;
else lt->next = p, lt = p;
} else {
if (!rh) rh = rt = p;
else rt->next = p, rt = p;
}
}
if (lh) lt->next = NULL;
if (rh) rt->next = NULL;
quick_sort(lh, lt);
quick_sort(rh, rt);
node *p = head;
p->next = NULL, tail = p;
if (lh) head = lh, lt->next = p;
if (rh) p->next = rh, tail = rt;
}
【在 p*****3 的大作中提到】
: 给个我以前写的吧，快速排序版本的
: struct NODE
: {
: int nVal;
: NODE* pNext;
:
: NODE(int n) : nVal(n), pNext(NULL) {}
: };
:
: void sort(NODE* pNode, int nLen)
| w**t
发帖数: 893 | 7 看看STL C++,有一个不错的实现
【在 u*****o 的大作中提到】
: 只知道bubble sort怎么做，请问愿意分享merge sort怎么写吗？
| l********7
发帖数: 40 | 8 merge sort不复杂吧，都不用额外分配空间 | x********u
发帖数: 1150 | 9 1. merge sort
no extra space needed. It is decided by the nature of linked list.
when merging two sorted sub lists, you can represent ordering by reassigning
node's next pointers. array elements don't have next pointers. so extra
array is needed to hold merged result. ordering in array is reflected by
array's indexes.
2. quick sort
copy linked list's node values into an array.
quick sort this array.
reassign linked list by copying values from the sorted array.
why this is a good approach? it can be faster than merge sort.
because it leverages cache's performance. CPU cache performs better on
adjacent numbers. array's numbers are adjacent in memory.
Numbers in linked list are rarely adjacent, they are scattered.
Also, quick sort has efficient inner loop. In most cases, it is faster than
merge sort.
performance gain from better cache hits + gain from using quick sort are set
back by the two copy operations. | z*********8
发帖数: 2070 | | m*****k
发帖数: 731 | | c********p
发帖数: 1969 | |
|
