常用排序算法

1. 插入排序：

?

#include "main.h"void insertSort(int *data, int length){    int pos, i , temp;    for (pos = 1; pos < length; pos++)    {        temp = data[pos];        for (i = pos - 1; i >= 0; i--)        {            if (temp < data[i])            {                data[i + 1] = data[i];                if (0 == i)                {                    data[0] = temp;                    break;                }            }            else            {                data[i + 1] = temp;                break;            }        }    }}

?２.　选择排序：

?

#include "main.h"void selectSort(int *data, int length){    int max, pos, i;    for (pos = length - 1; pos > 0; pos--)    {        max = 0;        for (i = 1; i <= pos; i++)        {            if (data[max] < data[i])            {                max = i;            }        }        if (max != pos)        {            swap(data, max, pos);        }    }}

３.　冒泡排序：

?

#include "main.h"void popSort(int *data, int length){    int pos, i;    for (pos = length - 1; pos >= 1; pos--)    {        for (i = 0; i < pos; i++)        {            if (data[i] > data[i + 1])            {                swap (data, i, i + 1);            }        }    }}

４.　快速排序：

?

?

#include "main.h"/**  *  Partition of the quickSort  */int partition(int *data, int start, int end){    int i = start + 1, j = end;    if (start >= end)    {        return start;    }    while (1)    {        while (i <= j && data[start] >= data[i])        {            i++;        }        while (i <= j && data[start] < data[j])        {            j--;        }        if (i < j)        {            swap(data, i, j);        }        else        {            swap(data, start, j);            return j;        }    }}void quickSort(int *data, int start, int end){    int pos;        if (start >= end)    {        return;    }    pos = partition(data, start, end);    quickSort(data, start, pos - 1);    quickSort(data, pos + 1, end);}

?

５.　归并排序：

?

#include "main.h"void merge(int *data, int start, int middle, int end){    int i = start, j = middle + 1;    int pos = 0;    int *temp = NULL;        if (start >= end)    {        return;    }    temp = (int *)malloc((end - start + 1) * sizeof(int));    while (i <= middle && j <= end)    {        temp[pos++] = data[i] <= data[j] ? data[i++] : data[j++];    }    while (i <= middle)    {        temp[pos++] = data[i++];    }    while (j <= end)    {        temp[pos++] = data[j++];    }    pos = 0;    while (pos < end - start + 1)    {        data[start + pos] = temp[pos++];    }    free(temp);}void mergeSort(int *data, int length){    int i, step;    for (step = 1; step < length; step *= 2)    {        for (i = 0; i + step < length; i += 2 * step)        {            (i + 2 * step - 1 < length) ?                 merge(data, i, i + step - 1, i + 2 * step - 1) : merge(data, i, i + step - 1, length - 1);        }    }}

６.　堆排序：

?

#include "main.h"void adjust(int *data, int pos, int length){    int parent = pos, child = 2 * parent + 1;    while (child < length)    {        if (child + 1 < length && data[child + 1] > data[child])        {            child++;        }        if (data[parent] < data[child])        {            swap(data, parent, child);            parent = child;            child = 2 * parent + 1;        }        else        {            break;        }    }}void createHeap(int *data, int length){    int pos;    for (pos = (length - 2) / 2; pos >= 0; pos--)    {        adjust(data, pos, length);    }}void heapSort(int *data, int length){    int pos;    createHeap(data, length);    for (pos = length - 1; pos >= 0; pos--)    {        swap(data, pos, 0);        adjust(data, 0, pos);    }}void heapSortNoWrap(int *data, int length){    int start, end, child, parent, temp;    end = length - 1;    start = (end - 1) / 2;    while (1)    {        if (0 <= start)        {            temp = data[start--];        }        else        {            if (0 == end)            {                return;            }            else            {                temp = data[end];                data[end--] = data[0];            }        }        parent = start + 1;        child = 2 * parent + 1;        while (child <= end)        {            if (child + 1 <= end && data[child + 1] > data[child])            {                child++;            }            if (temp < data[child])            {                data[parent] = data[child];                parent = child;                child = 2 * parent + 1;            }            else            {                break;            }        }         data[parent] = temp;    }}

?