<分区>
我已经写了链表快速排序的代码，这里是代码
#include<stdio.h>
#include<iostream>
using namespace std;
typedef struct _tagIntegerList
{
int nInteger;
struct _tagIntegerList *prev;
struct _tagIntegerList *next;
}IntegerList;
IntegerList *firstitem=NULL;
IntegerList *lastitem=NULL;
void addlist(int n)
{
IntegerList *pitem=new IntegerList;
pitem->nInteger=n;
if ( firstitem==NULL){
firstitem=lastitem=pitem;
pitem->next=pitem->prev=NULL;
}
else{
lastitem->next=pitem;
pitem->prev=lastitem;
lastitem=pitem;
pitem->next=NULL;
}
}
void removeall(){
IntegerList *delitem,*pitem=firstitem;
while(pitem!=NULL){
delitem=pitem;
pitem=pitem->next;
delete delitem;
}
firstitem=lastitem=NULL;
}
void print(){
IntegerList * pitem=firstitem;
while(pitem!=NULL){
cout<<pitem->nInteger<<" ";
pitem=pitem->next;
}
}
// Quick Sort List
void quicksort(IntegerList *left, IntegerList *right)
{
IntegerList *start;
IntegerList *current;
int copyinteger;
if (left==right) return ;
start=left;
current=start->next;
while(1){
if (start->nInteger<current->nInteger){
copyinteger=current->nInteger;
current->nInteger=start->nInteger;
start->nInteger=copyinteger;
}
// Check if we have reached the right end
if (current=right) break;
current=current->next;
}
//swap first and current items
copyinteger=left->nInteger;
left->nInteger=current->nInteger;
current->nInteger=copyinteger;
IntegerList *oldcurrent=current;
// Check if we need to sort the left hand size of the Current point
current=current->prev;
if (current!=NULL){
if ((left->prev!=current)&& (current->next!=left))
quicksort(left,current);
}
current=oldcurrent;
current=current->next;
if (current!=NULL){
if ((current->prev!=right)&& (right->next!=current))
quicksort(current,right);
}
}
int main(){
addlist(100);
addlist(12);
addlist(56);
addlist(67);
addlist(4);
addlist(91);
addlist(34);
addlist(59);
addlist(42);
addlist(20);
addlist(83);
addlist(74);
addlist(33);
addlist(79);
addlist(49);
addlist(51);
quicksort(firstitem,lastitem);
print();
removeall();
return 0;
}
但输出不是我所期待的，这是结果
4 56 67 12 91 34 59 42 20 83 74 33 79 49 51 100
请帮我看看这段代码有什么问题吗？我也对算法的复杂度感兴趣，它是否与 O(nlogn) 相同？