10种常见排序算法实现

#include <unistd.h>
#include <stdlib.h>
#include <stdio.h>
#include <fcntl.h>
#include <sched.h>
#include <wait.h>
#include <assert.h>
#include <errno.h>
#include <signal.h>
#include <string.h>
#include <pthread.h>

#include <sys/mman.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <sys/time.h>
#include <sys/resource.h>
#include <sys/socket.h>

#include <iostream>

using namespace std;

#define TIMER(val) do{
        struct timeval tm;
        gettimeofday(&tm, NULL);
        val = tm.tv_sec * 1000 + tm.tv_usec/1000;
}
while(0)

unsigned int seed = 0;

int is_sorted(int *array, int size)
{
        int sorted = 1;
        for(int i=0; i<size-1; i++)
        {
                if(array[i]<=array[i+1])
                        continue;
                else
                {
                        sorted = 0;
                        break;
                }
        }
        return sorted;
}

//insert sort
int insert_sort(int array[], int size)
{
        for(int i=1; i<size; i++)
        {
                int sentinel = array[i];
                int j;
                for(j=i-1; j>=0; j--)
                {
                        if(sentinel < array[j])
                        {
                                array[j+1] = array[j];
                        }
                        else
                        {
                                break;
                        }
                }
                if(j+1 != i)
                        array[j+1] = sentinel;
        }
        assert(is_sorted(array, size)==1);
        return 0;
}

//shell basic
int shell_basic_sort(int array[], int size, int step)
{
        for(int i=1; i<=step; i++)
        {
                //jump insert sort
                for(int j=i; j<=size; j+=step)
                {
                        int sentinel = array[j-1];
                        int k;
                        for(k=j-step; k>=i; k-=step)
                        {
                                if(sentinel < array[k-1])
                                {
                                        array[k+step-1] = array[k-1];
                                }
                                else
                                {
                                        break;
                                }
                        }
                        array[k+step-1] = sentinel;
                }
        }
        return 0;
}

int shell_sort(int array[], int size)
{
        int step = size;
        while(step>=1)
        {
                shell_basic_sort(array, size, step);
                step/=2;
        }

        assert(is_sorted(array, size)==1);
        return 0;
}

void swap(int *a, int *b)
{
        int t = *a;
        *a = *b;
        *b = t;
}


//bubble sort
int bubble_sort(int array[], int size)
{
        int sorted;

        for(int i=size-1; i>0; i--)
        {
                sorted = 1;
                for(int j=0; j<i; j++)
                {
                        if(array[j] > array[j+1])
                        {
                                swap(&array[j], &array[j+1]);
                                sorted = 0;
                        }
                }
                if(1==sorted)
                        break;
        }

        assert(is_sorted(array, size)==1);
        return 0;
}

int pivot(int array[], int first, int last)
{
        int f = array[first];
        while(first<last)
        {

                while(first < last && array[last]>=f)
                        last--;
                array[first] = array[last];
                while(first < last && array[first]<=f)
                        first++;
                array[last] = array[first];
        }
        array[first] = f;
        return;
}


int quick_sort(int array[], int first, int last)
{
        if(first>=last)
                return 0;

        int size = last - first + 1;
        int rand = (int)rand_r(&seed) % size;
        swap(&array[first], &array[first+rand]);

        int mid = pivot(array, first, last);
        quick_sort(array, first, mid-1);
        quick_sort(array, mid+1, last);
        return 0;
}

typedef struct stack
{
        int low;
        int high;
}stack;

int quick_sort2(int array[], int first, int last)
{
        int top = 0;
        stack *pstack = (stack *)malloc(sizeof(stack) * (last-first+1));
        if(pstack==NULL)
                return -1;
        memset(pstack, (last-first+1), 0);

        int size = last - first + 1;
        int rand = (int)rand_r(&seed) % size;
        swap(&array[first], &array[first+rand]);
        int mid = pivot(array, first, last);

        pstack[top].low = mid+1;
        pstack[top].high = last;
        top++;
        //1

        pstack[top].low = first;
        pstack[top].high = mid-1;
        top++;
        //2

        while(top>0)
        {
                top--;
                int low = pstack[top].low;
                int high = pstack[top].high;
                if(low<high)
                {
                        int size = high - low + 1;
                        int rand = (int)rand_r(&seed) % size;
                        swap(&array[low], &array[low+rand]);
                        int mid = pivot(array, low, high);

                        pstack[top].low = mid+1;
                        pstack[top].high = high;
                        top++;

                        pstack[top].low = low;
                        pstack[top].high = mid-1;
                        top++;
                }
        }

        free(pstack);
        return 0;
}

int find_max(int array[], int size)
{
        int max_index = 0;
        int sentinel = array[0];
        for(int j=1; j<size; j++)
        {
                if(array[j]>sentinel)
                {
                        sentinel = array[j];
                        max_index = j;
                }
        }
        return max_index;
}

int select_sort(int array[], int size)
{
        for(int i=size; i>=1; i--)
        {
                int max_index = find_max(array, i);
                if(max_index!=i-1)
                {
                        swap(&array[max_index], &array[i-1]);
                }
        }
        assert(is_sorted(array, size)==1);
        return 0;
}

int heapify(int array[], int index, int size)
{
        while(index<=size/2)
        {
                int left = 2*index;
                int right = left+1;
                int max_index = left;
                if( (right<=size) && array[left-1] < array[right-1])
                        max_index = right;
                if(array[index-1] < array[max_index-1])
                {
                        swap(&array[index-1], &array[max_index-1]);
                        index = max_index;
                }
                else
                        break;
        }
        return 0;
}

int heap_sort(int array[], int size)
{
        //build heap, heapify
        int mid = size/2;
        for(int i=mid; i>0; i--)
                heapify(array, i, size);
        for(int i=size; i>0; )
        {
                swap(&array[0], &array[i-1]);
                i--;
                if(i>0)
                        heapify(array, 1, i);
        }
        assert(is_sorted(array, size)==1);
        return 0;
}

//(start, mid-1)
//(mid, end)
int merge(int array[], int start, int mid, int end, int temparray[])
{
        int size1 = mid -start;
        int size2 = end - mid +1;
        int size = size1 > size2 ? size2 : size1;

        int i,j,k;
        i = j = k =0;
        while( i<size1 && j<size2 )
        {
                if(array[start+i] <array[mid+j])
                {
                        temparray[j++] = array[start+i];
                        i++;
                }
                else
                {
                        temparray[j++] = array[mid+j];
                        j++;
                }
        }
        if(i==size1)
        {
                memcpy(array+size, &array[mid+j], size1-j);
        }
        else
        {
                memcpy(array+size, &array[start+i], size1-i);
        }
        memcpy(array, temparray, sizeof(int)*size);
        return 0;
}


int merge_sort(int array[], int start, int end, int temparray[])
{
        if(start>=end)
                return 0;

        int size = end - start + 1;
        int mid = start + size/2;

        merge_sort(array, start, mid-1, temparray);
        merge_sort(array, mid, end, temparray);
        merge(array, start, mid, end, temparray);
        return 0;
}

int Merge_sort(int array[], int start, int end)
{
        int size = end-start+1;
        int *temparray = (int *)malloc(sizeof(int) *size);
        assert(array!=NULL);
        merge_sort(array, start, end, temparray);
        free(temparray);
        return 0;
}


///////////////////////////////////////////////////////////////////////////////////////////////////////////
typedef struct queue_elem
{
        int value;
        struct queue_elem *next;
}queue_elem;

typedef struct queue
{
        queue_elem *first;
        queue_elem *last;
        int queue_size;
}queue;

typedef struct radix_queue
{
        queue qvalue[10];
}radix_queue;

radix_queue radix;
queue_elem *g_alloc;
int begin_alloc;
int max_size;

void init_queue_elm(queue_elem *qe)
{
        qe->value = 0;
        qe->next = NULL;
}

int init_queue(queue *q)
{
        q->first = q->last = NULL;
        q->queue_size = 0;
}

queue_elem *get_queue_elem()
{
        if(begin_alloc>=max_size)
        {
                cout << "get queue elem error2" << endl;
                return NULL;
        }
        int curr = begin_alloc++;
        queue_elem * p = g_alloc + curr;
        init_queue_elm(p);
        return p;
}

int init_radix(radix_queue *radix)
{
        for(int i=0; i<10; i++)
                init_queue(&radix->qvalue[i]);
}

int insert_queue(queue *q, int value)
{
        queue_elem *elem = get_queue_elem();
        if(elem==NULL)
        {
                cout << "get queue elem error" << endl;
                return -1;
        }
        elem->value = value;
        elem->next = NULL;
        if(q->queue_size==0)
                q->first = q->last = elem;
        else
                q->last->next = elem;

        q->last = elem;
        q->queue_size++;
        return 0;
}
int collect(radix_queue radix, int array[])
{
        int i = 0;
        for(int j=0; j<10; j++)
        {
                queue q = radix.qvalue[j];
                queue_elem *first = q.first;
                while(first!=NULL)
                {
                        array[i++] = first->value;
                        first = first->next;
                }
        }
        return 0;
}

int power(int base, int m)
{
        int value = 1;
        for(int i=0; i<m; i++)
                value *= base;
        return value;
}

int radix_sort(int array[], int size)
{
        max_size = size;
        begin_alloc = 0;
        g_alloc = (queue_elem *)malloc(sizeof(queue_elem) * size);
        assert(g_alloc);

        int maxvalue = array[0];
        for(int i=1; i<size; i++)
                if(array[i]>maxvalue)
                        maxvalue = array[i];
        int max_step = 0;
        while(maxvalue>0)
        {
                max_step++;
                maxvalue = maxvalue/10;
        }

        for(int i=0; i<max_step; i++)
        {
                init_radix(&radix);

                int div = power(10, i);
                for(int j=0; j<size; j++)
                {
                        int temp = array[j]/div;
                        int index = temp - temp/10 *10;
                        insert_queue(&radix.qvalue[index], array[j]);
                }
                collect(radix, array);
                begin_alloc = 0;
        }

        free(g_alloc);
        assert(is_sorted(array, size)==1);
        return 0;
}


int counting_sort(int array[], int size)
{
        int max = array[0];
        for(int i=1; i<size; i++)
                if(array[i]>max)
                        max = array[i];
        int *temparray = (int *)malloc(sizeof(int) * (max+1));
        assert(temparray!=NULL);
        memset(temparray, 0, sizeof(int)*(max+1));

        int *array2 = (int *)malloc(sizeof(int) * (size));
        assert(array2!=NULL);
        memset(array2, 0, sizeof(int)*(size));

        for(int i=0; i<size; i++)
        {
                temparray[array[i]]++;
        }
        for(int i=1; i<=max; i++)
        {
                temparray[i] += temparray[i-1];
        }
        for(int i=0; i<size; i++)
        {
                array2[--temparray[array[i]]] = array[i];
        }
        memcpy(array, array2, sizeof(int) * size);
        free(temparray);
        free(array2);
        return 0;
}

int mypower(int base, int p)
{
        int ret = 1;
        while(p-->0)
                ret *= base;
        return ret;
}

int getindexvalue(int num, int index)
{
        if(index<1)
                return -1;

        int p = mypower(10, index);
        int q = p/10;
        return ( num - num /p * p ) / q;
}

int radix_sort2(int array[], int size)
{
        int *p = array;
        int maxvalue = array[0];
        for(int i=1; i<size; i++)
                if(array[i]>maxvalue)
                        maxvalue = array[i];
        int max_step = 0;
        while(maxvalue>0)
        {
                max_step++;
                maxvalue = maxvalue/10;
        }

        int *array2 = (int *)malloc(sizeof(int) * (size));
        assert(array2!=NULL);
        memset(array2, 0, sizeof(int)*(size));

        for(int i=1; i<=max_step; i++)
        {
                int tempbuf[10] = {0};
                for(int j=0; j<=size; j++)
                        tempbuf[getindexvalue(p[j], i)]++;
                for(int j=1; j<10; j++)
                        tempbuf[j] += tempbuf[j-1];
                for(int j=0; j<size; j++)
                        array2[--tempbuf[getindexvalue(p[j],i)]] = p[j];
                int *t = p;
                p = array2;
                array2 = t;
        }
        if(p!=array)
        {
                memcpy(array, p, sizeof(int)*size);
        }

        free(array2);
        return 0;
}


/*
   in this file, we test the sort funcion.
 */
int main(int argc, char **argv)
{
        int *array = NULL;
        int size = 100000;
        array = (int *)malloc(sizeof(int) *size);
        assert(array!=NULL);

        int *array_bak = (int *)malloc(sizeof(int) *size);
        assert(array_bak!=NULL);

        seed = time(NULL);
        int mod = 1000000;

        long starttime, endtime;

        //init
        for(int i=0; i<size; i++)
        {
                array[i] = rand_r(&seed) % mod;
        }
        memcpy(array_bak, array, sizeof(int)*size);

        //1. insert sort
        TIMER(starttime);
        insert_sort(array, size);
        TIMER(endtime);
        cout << "insert sort time: " << endtime-starttime << endl;
        memcpy(array, array_bak, sizeof(int)*size);

        //2. shell sort
        TIMER(starttime);
        shell_sort(array, size);
        TIMER(endtime);
        cout << "shell sort time: " << endtime-starttime << endl;
        memcpy(array, array_bak, sizeof(int)*size);

        //3. bubble sort
        TIMER(starttime);
        bubble_sort(array, size);
        TIMER(endtime);
        cout << "bubble sort time: " << endtime-starttime << endl;
        memcpy(array, array_bak, sizeof(int)*size);

        //4. quick sort
        TIMER(starttime);
        quick_sort(array, 0, size-1);
        assert(is_sorted(array, size)==1);
        TIMER(endtime);
        cout << "quick sort time: " << endtime-starttime << endl;
        memcpy(array, array_bak, sizeof(int)*size);

        //4.1 quick sort without recursion
        TIMER(starttime);
        quick_sort2(array, 0, size-1);
        assert(is_sorted(array, size)==1);
        TIMER(endtime);
        cout << "quick sort 2 time: " << endtime-starttime << endl;
        memcpy(array, array_bak, sizeof(int)*size);

        //5. select sort
        TIMER(starttime);
        select_sort(array, size);
        TIMER(endtime);
        cout << "select sort time: " << endtime-starttime << endl;
        memcpy(array, array_bak, sizeof(int)*size);

        //6. heap sort
        TIMER(starttime);
        heap_sort(array, size);
        TIMER(endtime);
        cout << "heap sort time: " << endtime-starttime << endl;
        memcpy(array, array_bak, sizeof(int)*size);

        //7. merge sort
        TIMER(starttime);
        Merge_sort(array, 0, size-1);
        TIMER(endtime);
        cout << "merge sort time: " << endtime-starttime << endl;
        memcpy(array, array_bak, sizeof(int)*size);

        //8. radix sort
        TIMER(starttime);
        radix_sort(array, size);
        TIMER(endtime);
        cout << "radix sort time: " << endtime-starttime << endl;
        memcpy(array, array_bak, sizeof(int)*size);

        //9. radix sort 2 using counting sort
        TIMER(starttime);
        radix_sort2(array, size);
        TIMER(endtime);
        cout << "radix sort 2 time: " << endtime-starttime << endl;
        memcpy(array, array_bak, sizeof(int)*size);


        //10. counting sort
        TIMER(starttime);
        counting_sort(array, size);
        TIMER(endtime);
        cout << "counting sort time: " << endtime-starttime << endl;
        memcpy(array, array_bak, sizeof(int)*size);

        //destroy the memory
        free(array);
        free(array_bak);
        return 0;
}