排序算法

#ifndef SORT_H_
#define SORT_H_

#include <malloc.h>
#include <string.h>

#ifndef D_TYPY_
#define D_TYPY_
typedef int DType;
#endif

/*****排序(非递减)***************************/

/* 值交换 */
static void swap(DType* a, DType* b)
{
    DType tmp;
    tmp = *a;
    *a = *b;
    *b = tmp;
}

/* 插入排序：从前往后，将后续索引元素插入到前面已经排好序的记录的适当位置
   left为较低下标，right为较高下标，eg: arr[10..20]
*/
void insert_sort(DType* arr, int left, int right)
{
    if (left >= right)
        return;

    int i, j, tmp;
    for (i = left+1; i <= right; ++i)
    {
        j = i-1;
        tmp = arr[i];
        while ( j>=0 && arr[j]>tmp )
        {
            arr[j+1] = arr[j];
            --j;
        }
        arr[j+1] = tmp;
    }
}

/* 选择排序：从前往后，将后续索引元素与当前记录比较，小则交换 */
void select_sort(DType* arr, int left, int right)
{
    if (left >= right)
        return;

    int i, j;
    for (i = left; i < right; ++i)
        for (j = i+1; j <= right; ++j)
        {
            if (arr[i] > arr[j])
                swap(&arr[i], &arr[j]);
        }
}

/* 冒泡交换排序：从后往前，毗邻元素比较，较小的置前 */
void bubble_sort(DType* arr, int left, int right)
{
    if (left >= right)
        return;

    int i, j;
    int exchanged; /* 提前结束标志 */

    for (i = left; i < right; ++i)
    {
        exchanged = 0;
        for (j = right-1; j >= i; --j)
        {
            if (arr[j] > arr[j+1])
            {
                swap(&arr[j], &arr[j+1]);
                exchanged = 1;
            }
        }
        if (exchanged == 0)
            break;
    }
}

/* 归并有序子串ptr_from[0..n_from-1]到ptr_to[0..n_to-1]
*/
static void merge(DType* ptr_to, size_t n_to, const DType* ptr_from, size_t n_from)
{
    while (n_from > 0)
    {
        if (n_to <= 0 || *(ptr_from + n_from - 1) > *(ptr_to + n_to - 1) )
        {
            --n_from;
            *(ptr_to + n_to + n_from) = *(ptr_from + n_from);
        }
        else
        {
            --n_to;
            *(ptr_to + n_to + n_from) = *(ptr_to + n_to);
        }
    }
}

/* 归并排序:分治法的应用，将数组在中间分为子数组，分别排序，然后归并。
   它在最坏情况下具有良好特性 T(n)=O(nlogn)
*/
void merge_sort(DType* arr, int left, int right)
{
    if (left >= right)
        return;

    int mid = (left+right)/2;
    merge_sort(arr, left, mid);
    merge_sort(arr, mid+1, right);

    const size_t bytes = (right-mid)*sizeof(DType);

    /* 临时分配内存作归并，有待改善！！！ */
    DType* tmp_arr = (DType*)malloc(bytes);
    if (NULL == tmp_arr)
        exit(1);
    memcpy(tmp_arr, &arr[mid+1], bytes);
    merge(&arr[left], mid-left+1, tmp_arr, right-mid);
    free(tmp_arr);
}

/* 快速排序：将数组根据临街值分为子数组，对子数组递归分割，无需归并即为有序数组
   T(n)=O(nlogn)
*/
void quick_sort(DType* arr, int left, int right)
{
    if (left >= right)
        return;

    DType pivot = arr[left];
    int i = left, j = right+1;
    while (1)
    {
        while (i<=right && arr[++i]<pivot)
            ;
        while (arr[--j]>pivot)
            ;
        if (i >= j)
            break;
        else
            swap(&arr[i], &arr[j]);
    }
    swap(&arr[left], &arr[j]);

    quick_sort(arr, left, j-1);
    quick_sort(arr, j+1, right);
}

/* 快排版本2 */
void quick_sort2(DType* arr, int left, int right)
{
    if (left >= right)
        return;

    int m = left;
    int i;
    for (i = left+1; i <= right; ++i)
    {
        if (arr[i] < arr[left])
            swap(&arr[++m], &arr[i]);
    }
    swap(&arr[left], &arr[m]);

    quick_sort2(arr, left, m-1);
    quick_sort2(arr, m+1, right);
}

#endif