基本排序(C语言实现)

#include <stdio.h>
#include <stdlib.h>

void bubble_sort(int a[], int len);// 冒泡 

void insertion_sort(int a[], int len);// 插入

void shell_sort(int a[], int len);// 希尔

void selection_sort(int a[], int len);// 选择

void quick_sort(int a[], int sIndex, int eIndex);// 快速排序(单边)

void merge_sort_top_down(int a[], int sIndex, int eIndex);// 归并 从上往下

void merge_sort_bottom_up(int a[], int len);// 归并 从下往上

void bucket_sort(int a[], int len, int max);// 桶排序

void radix_sort_LSD(int a[], int len);// 基数排序LSD

int main(int argc, char const *argv[])
{
    int a[] = {6, 5, 3, 1, 2, 4};
    int len = sizeof(a) / sizeof(a[0]);


    // bubble_sort(a, len);
    // insertion_sort(a, len);
    // shell_sort(a, len);
    // selection_sort(a, len);
    // quick_sort(a, 0, len - 1);
    // merge_sort_top_down(a, 0, len - 1);
    // merge_sort_bottom_up(a, len);
    // bucket_sort(a, len, 7);// Max Win(数组长度 pk 元素最大值) + 1
    // radix_sort_LSD(a, len);

    for (int i = 0; i < len; ++i)
    {
        printf("%d\n", a[i]);
    }

    return 0;
}


void bubble_sort(int a[], int len)
{
    int i, j, temp, jCount, iCount = len - 1;
    for (i = 0; i < iCount; ++i)
    {
        for (j = 0, jCount = iCount - i; j < jCount; ++j)
        {
            if (a[j] > a[j + 1])
            {
                temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
            }            
        }
    }
}


void insertion_sort(int a[], int len)
{
    int i, j, temp;
    for (i = 1; i < len; ++i)
    {
        temp = a[i];
        j = i - 1;
        while (j >= 0 && temp < a[j])
        {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = temp;
    }
}


void shell_sort(int a[], int len)
{
    int i, j, temp, gap;
    for (gap = len >> 1; gap > 0; gap = gap >> 1)
    {
        for (i = gap; i < len; ++i)
        {
            temp = a[i];
            for (j = i - gap; j >= 0 && temp < a[j]; j = j - gap)
            {
                a[j + gap] = a[j];
            }
            a[j + gap] = temp;
        }
    }
}


void selection_sort(int a[], int len)
{
    int i, j, temp, minIndex, iCount = len  - 1;

    for (i = 0; i < iCount; ++i)
    {
        minIndex = i;
        for (j = i + 1; j < len; ++j)
        {
            if (a[j] < a[minIndex])
            {
                minIndex = j;
            }
        }

        if (minIndex != i)
        {
            temp = a[i];
            a[i] = a[minIndex];
            a[minIndex] = temp;
        }
    }
}


void quick_sort(int a[], int sIndex, int eIndex)
{
    if (sIndex >= eIndex)
    {
        return;
    }

    int i = sIndex - 1, j = sIndex, baseValue = a[eIndex];
    while (j < eIndex)
    {
        if (baseValue >= a[j])
        {
            int temp = a[j];
            a[j] = a[i + 1];
            a[i + 1] = temp;

            i++;
            j++;
        } 
        else
        {
            j++;
        }
    }

    a[eIndex] = a[i + 1];
    a[i + 1] = baseValue;

    quick_sort(a, sIndex, i);
    quick_sort(a, i + 2, eIndex);
}


void merge(int a[], int sIndex, int eIndex, int mid)
{
    int arrayTemp[eIndex - sIndex + 1];

    int i = sIndex, j = mid + 1, k = 0;
    while (1) 
    {
        if (i <= mid && j <= eIndex) 
        {
            if (a[i] <= a[j])
            {
                arrayTemp[k] = a[i];
                i++;
            } 
            else 
            {
                arrayTemp[k] = a[j];
                j++;
            }
            k++;
        } 
        else if (i > mid && j <= eIndex) 
        {
            arrayTemp[k] = a[j];
            j++;
            k++;
        } 
        else if (i <= mid && j > eIndex) 
        {
            arrayTemp[k] = a[i];
            i++;
            k++;
        } 
        else 
        {
            break;
        }
    }

    for (int m = 0; m < k; ++m)
    {
        a[sIndex + m] = arrayTemp[m];
    }
}


void merge_sort_top_down(int a[], int sIndex, int eIndex)
{
    if (sIndex >= eIndex)
    {
        return;
    }
    
    int mid = (sIndex + eIndex) / 2;
    merge_sort_top_down(a, sIndex, mid);
    merge_sort_top_down(a, mid + 1, eIndex);

    merge(a, sIndex, eIndex, mid);
}

void merge_sort_buttom_up(int a[], int len)
{
    int gap, i;
    for (gap = 1; gap < len; gap *= 2)
    {
        for(i = 0; i + 2 * gap - 1 < len; i += 2 * gap)
        {
            merge(a, i, i + 2 * gap - 1, i + gap - 1);
        }
    }
    merge(a, 0, len - 1, len >> 1);
}

void bucket_sort(int a[], int len, int max)
{
    int i, j;
    int *buckets;

    if (a == NULL || len < 1 || max < 1)
    {
        return ;
    }

    // 辅助空间
    buckets = (int *) calloc(max, sizeof(int));

    // 1. 计数 
    for(i = 0; i < len; i++) 
    {
        buckets[a[i]]++; 
    }

    // 2. 排序     i:辅助空间数组下标也是待排序数组值    j:待排序数组下标
    for (i = 0, j = 0; i < max; i++) 
    {
        while((buckets[i]--) > 0)
        {
            a[j++] = i;
        }
    }

    free(buckets);// 释放辅助空间内存
}

int get_max(int a[], int n)
{
    int i, max;

    max = a[0];
    for (i = 1; i < n; i++)
    {
        if (a[i] > max)
        {
            max = a[i];
        }
    }    
    return max;
}

void radix_sort_LSD_core(int a[], int len, int exp)
{
    int i, j, aIndex = 0, buckets[10][len];
    int tag[10] = {0};

    for (i = 0; i < len; ++i)
    {
        int tempValue = a[i] / exp % 10;
        buckets[tempValue][tag[tempValue]++] = a[i];
    }

    for (i = 0; i < 10; ++i)
    {
        for (j = 0; j < tag[i]; ++j)
        {
            a[aIndex++] = buckets[i][j];
        }
    }
}

void radix_sort_LSD(int a[], int len)
{
    int max = get_max(a, len);
    int exp;
    for (exp = 1; max / exp > 0; exp *= 10)
    {
        radix_sort_LSD_core(a, len, exp);
    }
}