排序,
我使用了三种排序:
手写快排: 48ms
C++模板快排: 48ms
堆排序:52ms
c++:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
int a[100005];
int pos = 0;
void inserts(int x)
{
a[++pos]=x;
int j=pos;
while(j>1)
{
if(a[j]<a[j/2])
{
swap(a[j],a[j/2]);
j=j/2;
}
else
break;
}
}
void removes()
{
swap(a[pos],a[1]);
int j=1;
pos--;
while(j<pos)
{
if(j*2>pos) break;
if(j*2+1>pos)
{
if(a[j]>a[j*2])
{
swap(a[j],a[j*2]);
j=j*2;
continue;
}
else
break;
}
if(j*2+1<=pos)
{
if(a[j*2]<a[j*2+1]&&a[j]>a[j*2])
{
swap(a[j],a[j*2]);
j=j*2;
continue;
}
if(a[j*2]>=a[j*2+1]&&a[j]>a[j*2+1])
{
swap(a[j],a[j*2+1]);
j=j*2+1;
continue;
}
else
break;
}
}
}
void quickSort(int l,int r)
{
if(r<=l)return;
int start = l+1;
int end = r;
int pos=l;
while(true)
{
while(a[pos]>a[end]&&end>l)
{
end--;
}
while(a[pos]<a[start]&&start<=r)
{
start++;
}
if(end<start) break;
swap(a[start],a[end]);
start++;
end--;
}
swap(a[pos],a[end]);
quickSort(l,end-1);
quickSort(end+1,r);
}
ListNode* sortList(ListNode* head) {
ListNode* list = new ListNode(0);
if(head==NULL) return NULL;
ListNode* temp = head;
int tag=0;
while(temp!=NULL)
{
a[tag++]=temp->val;
temp = temp->next;
}
quickSort(0,tag-1);
ListNode* term = list;
int tag2=tag-1;
while(tag2>=0)
{
term->val = a[tag2--];
if(tag2==-1)
break;
term->next = new ListNode(0);
term = term->next;
}
return list;
}
};