经典排序算法实现

1.希尔算法：

#include <stdio.h>
/* 希尔排序算法实现--但有时不稳定 */
void println(int array[], int len)
{
    int i = 0;

    for(i=0; i<len; i++)
    {
        printf("%d ", array[i]);
    }

    printf(" ");
}

void swap(int array[], int i, int j)
{
    int temp = array[i];

    array[i] = array[j];

    array[j] = temp;
}
//算法如下
void ShellSort(int array[], int len) // O(n*n)
{
    int i = 0;
    int j = 0;
    int k = -1;
    int temp = -1;
    int gap = len;

    do
    {
       //隔三个取一个数
        gap = gap / 3 + 1;
       //进行分组
        for(i=gap; i<len; i+=gap)
        {
            k = i;
            temp = array[k];
            //进行插入排序
            for(j=i-gap; (j>=0) && (array[j]>temp); j-=gap)
            {
               //每隔一个gap取一个数
                array[j+gap] = array[j];
                k = j;
            }

            array[k] = temp;
        }

    }while( gap > 1 );

}

int main()
{
   //初始化测试数据
    int array[] = {21, 25, 49, 25, 16, 8};
   //开辟空间
    int len = sizeof(array) / sizeof(*array);

    println(array, len);

    ShellSort(array, len);

    println(array, len);

    return 0;
}

2.快速算法：

#include <stdio.h>
/* 快速排序算法实现--也是不稳定 */
void println(int array[], int len)
{
    int i = 0;

    for(i=0; i<len; i++)
    {
        printf("%d ", array[i]);
    }

    printf(" ");
}
//对数据进行交换
void swap(int array[], int i, int j)
{
    int temp = array[i];

    array[i] = array[j];

    array[j] = temp;
}
//实现划分两个子序列(默认第一个用来做边界)
int partition(int array[], int low, int high)
{
    int pv = array[low];

    while( low < high )
    {
        while( (low < high) && (array[high] >= pv) )
        {
            high--;
        }
        //交换数据进行划分--pv 表示用来比较的基准
        swap(array, low, high);

        while( (low < high) && (array[low] <= pv) )
        {
            low++;
        }

        swap(array, low, high);
    }

    return low;
}
//快速算法如下
void QSort(int array[], int low, int high)
{
    if( low < high )
    {
        int pivot = partition(array, low, high);

        QSort(array, low, pivot-1);
        QSort(array, pivot+1, high);
    }
}
//之后在进行递归调用排序
void QuickSort(int array[], int len) // O(n*logn)
{
    QSort(array, 0, len-1);
}

int main()
{
    int array[] = {21, 25, 49, 25, 16, 8};
    int len = sizeof(array) / sizeof(*array);

    println(array, len);

    QuickSort(array, len);

    println(array, len);

    return 0;
}

2.归并算法：

#include <stdio.h>
#include <malloc.h>
/* 归并排序算法如下--此算法稳定 */
void println(int array[], int len)
{
    int i = 0;

    for(i=0; i<len; i++)
    {
        printf("%d ", array[i]);
    }

    printf(" ");
}
//交换数据
void swap(int array[], int i, int j)
{
    int temp = array[i];

    array[i] = array[j];

    array[j] = temp;
}
//两列归并划分代码如下
void Merge(int src[], int des[], int low, int mid, int high)
{
    int i = low;
    int j = mid + 1;
    int k = low;

    while( (i <= mid) && (j <= high) )
    {
        if( src[i] < src[j] )
        {
            des[k++] = src[i++];
        }
        else
        {
            des[k++] = src[j++];
        }
    }
    //若不对称执行以下代码
    while( i <= mid )
    {
        des[k++] = src[i++];
    }

    while( j <= high )
    {
        des[k++] = src[j++];
    }
}
//算法如下 --思想就是首先进行划分两列-在对两列进行排序-之后对两列进行归并
//（归并就是说--对已经排好序的两列进行归并）归排序直接可以用来做外排序
void MSort(int src[], int des[], int low, int high, int max)
{
    if( low == high )
    {
        des[low] = src[low];//递归的结束点；
    }
    else
    {
        int mid = (low + high) / 2;
        int* space = (int*)malloc(sizeof(int) * max);

        if( space != NULL )//空间有了--不停的划分递归
        {
            //src(low---mid)--->space
           MSort(src, space, low, mid, max);
           //src(mid+1---high)--->space
            MSort(src, space, mid+1, high, max);
            //src(low---mid)--->space
           Merge(space, des, low, mid, high);
        }
        //释放空间
        free(space);
    }
}
//进行排序之后复制到原数组来
void MergeSort(int array[], int len) // O(n*logn)
{
    MSort(array, array, 0, len-1, len);
}

int main()
{
    int array[] = {21, 25, 49, 25, 16, 8};
    int len = sizeof(array) / sizeof(*array);

    println(array, len);

    MergeSort(array, len);

    println(array, len);

    return 0;
}

经典排序算法实现

相关推荐