z*8
2 楼
没了， 就写个merge sort吧
a*d
3 楼
heap sort
u*o
4 楼
只知道bubble sort怎么做，请问愿意分享merge sort怎么写吗？
【在 z*********8 的大作中提到】
: 没了， 就写个merge sort吧
【在 z*********8 的大作中提到】
: 没了， 就写个merge sort吧
p*3
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;
}
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
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)
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
7 楼
看看STL C++,有一个不错的实现
【在 u*****o 的大作中提到】
: 只知道bubble sort怎么做，请问愿意分享merge sort怎么写吗？
【在 u*****o 的大作中提到】
: 只知道bubble sort怎么做，请问愿意分享merge sort怎么写吗？
l*7
8 楼
merge sort不复杂吧，都不用额外分配空间
x*u
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.
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
10 楼
m*k
11 楼
selection sort
c*p
12 楼
mark
相关阅读
请教哈佛博士后薪资水平请教: part-time 是否可以拿H1B请过来人给分析分析这种情况为什么H1B会有人被拒？一道behavior question有时间在6 周以内的Internship吗？"中美工作签证的对等待遇"项目正式归入NIU (转载)SQL面试题以及请教经典书籍Interview Questions for an investment bank免费拿最高350刀chase bonus+Discover 12000mile+10刀礼品卡若干（自取）啥是W2, 1099, corp-to-corp contract?OPT电话加急问个h1b transfer的问题啊 有人知道不【新奥集团上海分院招聘启事】关于out of status and opt 的一些问题 (转载)等了一天都没有消息，好着急刚刚搞匝了一个电面，很难过VA Job opening, citizen能不能递简历？CPT 月中到期, paycheck 月底拿有问题吗?