基本排序算法

作为一个自动化专业毕业的年轻小伙，自己的编程水平有限，需要广泛学习训练。特此记录下自己编程学习代码。非科班毕业，没有严格考量时间和空间的复杂度。

学习当然是学习了别人的思想然后内化的呀。

sort.h

//排序
//1.插入排序
//2.选择排序
//3.希尔排序
//4.冒泡排序
//5.快速排序(改进冒泡排序)
//6.堆排序(二叉树里的特例：堆)

#ifndef SORT_H

    #define SORT_H

    #include 

    //插入排序
    void InsertSortUp(int *pInt,int num);

    //选择排序
    void SelectSortUp(int *pInt,int num);

    //希尔排序
    void ShellSortUp(int *pInt,int num);
    //冒泡排序
    void BubbleSortUp(int *pInt,int num);

    //快速排序
    void QuickSortUp(int *pInt,int begin,int end);
    
#endif 

sort.c

#include "Sort.h"

//插入排序
//取出一个比较数,此时比较数对应的位置为空
//对于不满足条件的数移动，直到满足条件，此时插入
void InsertSortUp(int *pInt,int num)
{
    //检查传入参数的有效性
    if (pInt == NULL)
    {
        return;
    }
    if (num <= 1)
    {
        return;
    }

    //开始排序
    for (int i = 1; i < num; i ++)
    {
        int temp = *(pInt + i);
        int j = i - 1;
        while (1)
        {
            if (*(pInt + j) > temp)
            {
                *(pInt + j + 1) = *(pInt + j);
            }
            else if (*(pInt + j) <= temp)
            {
                break;
            }
            j --;
            if (j < 0)
            {
                break;
            }
        }
       *(pInt + j + 1) = temp;
    }
}

//选择排序
//每轮选出一个最小值，放置在数组前面
void SelectSortUp(int *pInt,int num)
{
    //检查输入参数有效性
    if (pInt == NULL)
    {
        return;
    }
    if (num <= 1)
    {
        return;
    }

    //开始排序
    int sortedNum = 0;
    int curMinIndex;
    
    while (1)
    {
        if (sortedNum < num)
        {
            //假设当前最小值索引为起始索引
            curMinIndex = sortedNum;

            for (int i = sortedNum; i < num; i ++)
            {
                if (*(pInt + curMinIndex) >= *(pInt + i))
                {
                    //更新当前最小值索引
                    curMinIndex = i;
                }
            }

            printf("min in this turn is : %dn",*(pInt + curMinIndex));

            if (curMinIndex != sortedNum)
            {
                //随sortedNum更新最小值
                int temp = *(pInt + sortedNum);
                *(pInt + sortedNum) = *(pInt + curMinIndex);
                *(pInt + curMinIndex) = temp;
            }
                
            //更新sortenNum
            sortedNum ++;
        }
        else 
        {
            break;
        }
    }
}

//希尔排序
//间隔递减排序
void ShellSortUp(int *pInt,int num)
{
    //检查输入参数的有效性
    if (pInt == NULL)
    {
        return;
    }
    if (num < 1)
    {
        return;
    }
    int deta = num - 1;
    for (;;)
    {
        if (deta == 0)
        {
            break;
        }
        for (int i = 0; i < num; i ++)
        { 
            if ((i + deta) >= num)
            {
                deta --;
                break;
            }
            if (pInt[i] > pInt[i + deta])
            {
                int tmp = pInt[i];
                pInt[i] = pInt[i + deta];
                pInt[i + deta] = tmp;
            }
        }
    }
}

//冒泡排序
void BubbleSortUp(int *pInt,int num)
{
    if (pInt == NULL)
    {
        return;
    }
    if (num < 2)
    {
        return;
    }
    for (int i = 0; i < num; i ++)
    {
        for (int j = i + 1; j < num; j ++)
        {
            if (pInt[i] > pInt[j])
            {
                int tmp = pInt[i];
                pInt[i] = pInt[j];
                pInt[j] = tmp;
            }
        }
    }
}

//快速排序
void QuickSortUp(int *pInt,int begin,int end)
{
    if (pInt == NULL)
    {
        return;
    }
    if (begin > end)
    {
        return;
    }

    int tem = pInt[begin];
    int i = begin;
    int j = end;
    while (i != j)
    {
        while ((pInt[j] >= tem) && (j > i))
        {
            j --;
        }
        while ((pInt[i] <= tem) && (j > i))
        {
            i ++;
        }
        if (j > i)
        {
            int t = pInt[i];
            pInt[i] = pInt[j];
            pInt[j] = t;
        }
       
    }
    pInt[begin] = pInt[i];
    pInt[i] = tem;
    QuickSortUp(pInt,begin,i-1);
    QuickSortUp(pInt,i+1,end);
}