c*******r
发帖数: 309 | 1 电面改了好几次最后才给了个Linked List 版本的bubble sort..... |
d**********x
发帖数: 4083 | 2 merge sort更不容易错。。
【在 c*******r 的大作中提到】
: 电面改了好几次最后才给了个Linked List 版本的bubble sort.....
|
n****r
发帖数: 120 | |
x*********w
发帖数: 533 | 4 quick sort版本
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;
} |
l*****a
发帖数: 14598 | 5 你又来贴c++ code了?
【在 x*********w 的大作中提到】
: quick sort版本
: struct NODE
: {
: int nVal;
: NODE* pNext;
: NODE(int n) : nVal(n), pNext(NULL) {}
: };
: void sort(NODE* pNode, int nLen)
: {
: if (NULL == pNode || nLen <= 0)
|
c*****a
发帖数: 808 | |
s***0
发帖数: 117 | 7 define FastBogoSort(list):
// An optimized BogoSort
// Runs in O(n log n)
for n from 1 to log(length(list)):
shuffle(list):
if isSorted(list):
return list
return "Kernel Page Fault (Error code: 2)" |
G****A
发帖数: 4160 | 8 我觉得最佳方案是拷贝成array，然后quick sort. 但你要能解释出为什么。
【在 c*******r 的大作中提到】
: 电面改了好几次最后才给了个Linked List 版本的bubble sort.....
|
x*********w
发帖数: 533 | 9
java是用来做project的，
c++是用来面试的
【在 l*****a 的大作中提到】
: 你又来贴c++ code了?
|
p*****2
发帖数: 21240 | 10
什么project呀？
【在 x*********w 的大作中提到】
:
: java是用来做project的，
: c++是用来面试的
|
w*****t
发帖数: 485 | 11 G家的第一次电面就是对linked list 做快排
【在 c*******r 的大作中提到】
: 电面改了好几次最后才给了个Linked List 版本的bubble sort.....
|
