八大排序及其c代码实现

 

#include
#include
#include
#include

#define N 10
#define Swap(a, b){ int tmp;tmp=a;a=b;b=tmp;}
#define M 100
void Bubbling_sort(int* arr);//冒泡排序
void Select_sort(int* arr);//选择排序
void Insert_sort(int* arr);//插入排序
void Shell_sort(int* arr);//希尔排序
void Quick_sort(int* arr, int left, int right);// 快速排序
void Heap_sort(int* arr);//堆排序
void Merge_sort(int* arr, int low,int high);//归并排序
void Count_sort(int* arr);//计数排序
 

void Bubbling_sort(int *arr)
{
    int i, j,tmp;
    for( i=1;i         for (j = 0; j < N - i; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
            }
        }
}

void print(int* arr)
{
    int i;
    for (i = 0; i < N; i++)
    {
        printf("%3d", arr[i]);
    }
    putchar('n');
}

void Select_sort(int *arr)
{
    int i, j, min_pos,tmp;
    for (j = 0; j < N - 1; j++)
    {
        min_pos = j;
        for (i = j + 1; i < N; i++)
        {
            if (arr[min_pos] > arr[i])
            {
                min_pos = i;
            }
        }
        tmp = arr[j];
        arr[j] =arr[min_pos] ;
        arr[min_pos] = tmp;
    }
}

void Insert_sort(int *arr)
{
    int i, j,insert;
    for (j = 1; j < N; j++)
    {
        insert = arr[j];
        for (i = j - 1; i > -1; i--)
        {
            if (insert             {
                arr[i + 1] = arr[i];
            }
            else
            {
                break;
            }
        }
        arr[i+1] = insert;
    }

}

void Shell_sort(int* arr)
{
    int i, j, insert,gap;
    
    for (gap=N >> 1; gap > 0; gap >>= 1)
    {
        for (j = gap; j < N; j++)
        {
            insert = arr[j];
            for (i = j - gap; i > -1; i-=gap)
            {
                if (insert < arr[i])
                {
                    arr[i + gap] = arr[i];
                }
                else
                {
                    break;
                }
            }
            arr[i + gap] = insert;
        }
    }
}

int position(int *arr, int left,int right)
{
    int i, k;
    for (i = 0, k = 0; i < right; i++)
    {
        if (arr[i] < arr[right])
        {
            Swap(arr[k] , arr[i]);
            k++;
        }
    }
    Swap(arr[k], arr[right]);
    return k;
}

void Quick_sort(int* arr, int left, int right)
{    
    int pos;
    if (left < right)
    {
        pos = position(arr,left,right);
        Quick_sort(arr, left, pos - 1);
        Quick_sort(arr, pos+1, right);
    }
}

void adjust_max_heap(int* arr, int adjust_pos, int len)
{
    int dad, son;
    dad = adjust_pos;
    son = 2 * dad + 1;
    while (son     {
        if (son + 1 < len && arr[son] < arr[son + 1])
        {
            son++;
        }
        if (arr[son] > arr[dad])
        {
            Swap(arr[son], arr[dad]);
            dad = son;
            son = 2 * dad + 1;
        }
        else {
            break;
        }
    }
}

void Heap_sort(int* arr)
{
    int i;
    for (i = N / 2 - 1; i >= 0; i--)
    {
        adjust_max_heap(arr, i, N);
    }
    Swap(arr[0], arr[N - 1]);
    for (i = N-1 ; i >= 1; i--)
    {
        adjust_max_heap(arr, 0, i);
        Swap(arr[0],arr[i-1])
    }
}

void merge(int* arr, int low, int mid, int high)//递归思想
{
    int b[N],i,j,k;
    memcpy(b, arr, sizeof(int) * N);
    for (i = low, k = low, j = mid + 1; i <= mid && j <= high;)
    {
        if (b[i] < b[j])
        {
            arr[k] = b[i];
            i++;
            k++;
        }
        else  {
            arr[k] = b[j];
            j++;
            k++;
        }
    }
    while (i <= mid)
    {
        arr[k] = b[i];
        i++;
        k++;
    }
    while (j <= high)
    {
        arr[k] = b[j];//改变arr值
        j++;
        k++;
    }
}

void Merge_sort(int* arr, int low, int high)
{
    int mid;
    if (low < high)
    {
        mid = (low + high) / 2;
        Merge_sort(arr, low, mid);
        Merge_sort(arr, mid+1, high);
        merge(arr, low, mid, high);
    }
}

void Count_sort(int* arr)
{
    int i, j, k=0;
    int count[M] = {0};
    for (i = 0; i < N; i++)
    {
        count[arr[i]]++;
    }
    for(j=0;j         for (i = 0; i < count[j]; i++)
        {
            arr[k++] = j;
        }

}