排序：从数组中选出最大的32个

今天还得洗衣服洗澡洗袜子。。。 就单纯的列出了这两种算法，但是没有具体解释第二种为什么会比第一种快。改天再给大家讲解原因。。。。代码写完之后也没有review，要是有什么问题麻烦大牛指正。

#include <stdio.h>
#include <time.h>
#include<string.h>
#include<assert.h>


//the total number need to be sort
#define MAXNUMBER            10000

// the max numbers
#define SORTNUMBER            32


typedef struct sortnode_t{
    int data;
    //_sortnode *pre;
    struct sortnode_t *next;
}sortnode;

//the array need to be sort
static int randomData[MAXNUMBER];

//sorted array
static int sortRandomData[SORTNUMBER];


//init the array which is need to be sort
void initRandomData(void)
{
    unsigned int i =0;
    srand((unsigned)time(NULL));
    memset(randomData,0,sizeof(randomData));
    for(i = 0; i < MAXNUMBER; i ++)
    {
        randomData[i] = rand();
    }

}

//sort the inited array,and find the SORTNUMBER max numbers
//if MAXNUMBER is large,this way will spend lots of time
void sortData_theWorst(void)
{
    //should not change the org array(randomData)
    int *tmpptr;
    int i,j;
    tmpptr = malloc(sizeof(randomData));
    memcpy(tmpptr, randomData, MAXNUMBER * sizeof(int));

    //init sortRandomData
    memset(sortRandomData, 0, sizeof(sortRandomData));
    for(i = 0; i < SORTNUMBER; i++)
    {
        sortRandomData[i] = tmpptr[i];
        for(j = i; j < MAXNUMBER; j ++)
        {
            if(sortRandomData[i] < tmpptr[j])
            {
                sortRandomData[i] = tmpptr[j];
                tmpptr[j] =tmpptr[i];
                tmpptr[i] =sortRandomData[i];
            }
        }
    }
    //print the result
    for(i = 0; i < SORTNUMBER; i++)
    {
        if((i & 0xF0 == 0) && (i !=0))
        {
            printf("\n");
        }

        printf("%d\t", sortRandomData[i]);
    }
    printf("\n");


}

//insert the value to the right list, return the min value of the list
int insertNodeToList(sortnode **list, int value)
{
    int i,nodenumber,mindata;
    sortnode *p;
    sortnode *tmplist;
    tmplist= malloc(sizeof(sortnode));
    assert(tmplist != NULL);
    tmplist->data = value;
    tmplist ->next = NULL;
    p = *list;
    for(i = 0; i < SORTNUMBER; i ++)
    {
        if(value > p->data)
        {
            nodenumber = i;
            break;
        }
        else
        {
            p = p->next;
        }
    }
    //if i = 32,should check the source
    assert(i != 32);

    p = *list;
    if(nodenumber == 0)
    {
        tmplist->next = p;
        *list = tmplist;
        p = *list;
        nodenumber = 1;
    }
    else
    {
        for(i = 0; i < nodenumber - 1; i ++)
        {
            p = p->next;
        }
        tmplist->next = p->next;
        p->next = tmplist;
    }
    for(i = nodenumber; i < SORTNUMBER; i ++)
    {
        p = p->next;
    }
    // p does not point to the last node
    mindata = p->data;

    assert(p->next != NULL);
    free(p->next);
    p->next = NULL;
    return mindata;

}

void sortData_worse(void)
{
    int i,j,minof32;
    sortnode *sortlist;
    sortnode *tmplist;
    sortnode *p;

    //consider the first 32 number of randomData are the max numbers
    memset(sortRandomData,0,sizeof(sortRandomData));
    memcpy(sortRandomData,randomData,sizeof(int) * SORTNUMBER);

    //sort the 32 numbers
    for(i = 0; i < SORTNUMBER - 1; i++)
    {
        int t;
        for(j = i + 1; j < SORTNUMBER; j ++)
        {
            if(sortRandomData[i] < sortRandomData[j])
            {
                t = sortRandomData[j];
                sortRandomData[j] = sortRandomData[i];
                sortRandomData[i] = t;
            }
        }
    }

    //init the sortlist,and fill it with the max 32 numbers
    sortlist = malloc(sizeof(sortnode));
    assert(sortlist != NULL);
    sortlist->data = sortRandomData[0];
    sortlist->next = NULL;
    p = sortlist;

    for(i = 1; i < SORTNUMBER; i ++)
    {
        tmplist= malloc(sizeof(sortnode));
        assert(tmplist != NULL);
        tmplist->data = sortRandomData[i];
        tmplist ->next = NULL;
        p->next = tmplist;
        p = p ->next;
    }
    minof32 = randomData[SORTNUMBER - 1];
    for(i = 32; i < MAXNUMBER; i++)
    {
        if(randomData[i] > minof32)
        {
            minof32 = insertNodeToList(&sortlist, randomData[i]);
        }
    }

    p = sortlist;
    for(i = 0; i < SORTNUMBER; i++)
    {
        if((i & 0xF0 == 0) && (i != 0))
        {
            printf("\n");
        }

        printf("%d\t", p->data);
        p = p->next;
    }
    printf("\n");




}

void main(void)
{
    int i;
    initRandomData();


    sortData_theWorst();


    printf("the second way\n");
    sortData_worse();


}