自己用快排写的list的sort比stl的合并排序sort快

直接贴代码

// test1.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include"list"
#include"time.h"
#include"windows.h"
#include"iostream"
using namespace std;

static void swap(list<int>::iterator a, list<int>::iterator b)

{
    if(*a==*b)
        return;
    int temp = *a;

    *a=*b;

    *b=temp;

}

 static list<int>::iterator partion(list<int>& _ilist,list<int>::iterator start,list<int>::iterator end)
 {
     int compare_value=*end;
     list<int>::iterator i=start;
     list<int>::iterator j=start;
     for(;j!=end;j++)
     {
         if((*j)<=compare_value)
         {
             //转换i---j//
            // i++;
             swap(i,j);
             i++;

         }
     }

     // i++;
     swap(i,end);
     return i;
 }


static void qurtsort(list<int>& _ilist,list<int>::iterator start,list<int>::iterator end)
{
    if(start==end)
        return;
    list<int>::iterator mid1=partion(_ilist,start,end);
    list<int>::iterator mid2=mid1;
    if(!(mid1==start))
     qurtsort(_ilist,start,--mid1);
    if(!(mid2==end))
        if(!(mid2==start))
        qurtsort(_ilist,mid2,end);

}




int main(int argc, char* argv[])
{
    list<int> _ilist;
    list<int> _ilist1;
    for(int k=0;k<1000;k++)
    {
        int jj=rand();
        _ilist.push_back(jj);
        _ilist1.push_back(jj);

    }

//    _ilist.push_back(1);
//    _ilist.push_back(2);
//    _ilist.push_back(1);
    list<int>::iterator _iter;
//    for(_iter=_ilist.begin();_iter!=_ilist.end();_iter++)
//        printf("%d\t",*_iter);
    int betime=GetTickCount();
    qurtsort(_ilist,_ilist.begin(),--(_ilist.end()));
    int eetime=GetTickCount();
//    for(_iter=_ilist.begin();_iter!=_ilist.end();_iter++)
//        printf("%d\t",*_iter);
     printf("\n");
    cout<<eetime-betime;


    int betime1=GetTickCount();
    _ilist1.sort();
    int eetime1=GetTickCount();
         printf("\n");
    cout<<eetime1-betime1;

    return 0;
}

另外：还可以参考