温建峰的技术栈

排序算法

排序算法

算法时间复杂度空间复杂度稳定性说明
冒泡排序O(n^2)O(1)稳定通过不断比较相邻元素的大小，将较大的元素“冒泡”到数组的末尾
插入排序O(n^2)O(1)稳定通过构建有序序列，对于未排序数据，在已排序序列中，从后向前扫描，找到相应位置并插入
快速排序O(nlogn)O(logn)不稳定通过选取一个“基准”元素，将待排序的数组划分为两个子数组，分别对这两个子数组进行排序，然后将两个有序子数组合并成一个有序数组
归并排序O(nlogn)O(n)稳定将待排序的数组划分为两个子数组，分别对这两个子数组进行排序，然后将两个有序子数组合并成一个有序数组
堆排序O(nlogn)O(1)不稳定将待排序的数组构建成一个大顶堆，每次从堆中取出最大（或最小）的元素，将其与最后一个元素交换位置，然后对前n-1个元素重新调整为大顶堆
希尔排序O(n^1.3)O(1)不稳定将待排序的数组按照步长进行分组，对每一组进行插入排序，然后逐步缩小步长
计数排序O(n+k)O(n+k)稳定将待排序的数组中的元素作为下标，统计每个元素出现的次数，然后按照出现次数从大到小输出

算法复杂度

权衡：以时间换空间、以空间换时间。

复杂度分析能够体现算法运行所需的时间和空间资源与输入数据大小之间的关系。它描述了随着输入数据大小的增加，算法执行所需时间和空间的增长趋势。

  • 时间和空间资源 对应时间复杂度和空间复杂度
  • 随着输入数据大小的增加 算法运行效率和输入数据体量之间的关系
  • 时间和空间的增长趋势 表示复杂度分析关注的不是运行时间或占用空间的具体值，而是时间或空间增长的快慢。

时间复杂度

时间复杂度符号表示
常数阶
对数阶
线性阶
线性对数阶
平方阶
立方阶
K次方阶
指数阶
阶乘阶
从上至下依次的时间复杂度越来越大，执行的效率越来越低。

比如冒泡排序，外层循环执行次，内层循环执行、、...、、次，平均为次所以时间复杂度为： 

// 时间复杂度 O(1)
// 与n无关，也即无论数据量多大，操作数量和数据量都保持不变

// 时间复杂度 O(n)
// 操作数量和数据数据n成正比（线性关系）
for(i = 0;i < n; i++)		// O(n)
{
    // 操作
    // ......
}

// 时间复杂度 O(n^2)
// 操作数量和数据数据n^2成正比，或者说操作数量和数据数据n成平方关系。
for(i = 0; i < n; i++)		// O(n)
{
    for(j = 0; j < n; j++)	// O(n)
    {

    }
}

// 时间复杂度 O(logn)
while(n > 1)
{
    n = n/2;
    // ...
}

// 时间复杂度 O(nlogn)
for(i = 0; i < n; i++)	// O(n)
{
    while(m < n)		// O(logn)
    {
        m *= 2;
        // ...
    }
}

// 时间复杂度 O(2^n)
// 例如：1, 2, 4, 8，16，32...
int size = 1;
for(i = 0; i < n; i++)
{
    for(j = 0; j < size; j++)	// 2^n
    {
        // ...
    }
    size *= 2;
}

// 时间复杂度 O(n!)

空间复杂度

常见空间复杂度类型，从上到下依次递增。

空间复杂度符号表示
常数阶
对数阶
线性阶
平方阶
指数阶
// 空间复杂度 O(1)

// 空间复杂度 O(n)
// 线性阶常见于元素数量与成正比的数组、链表、栈、队列等：
void func(int n)
{
    int *p = (int *)malloc(sizeof(int) * n);
    // ...
}

// 空间复杂度 O(n^2)
// 平方阶常见于元素数量与成正方比的二维数组、矩阵、图等：
void func(int n)
{
    int **matrix = malloc(sizeof(int *) * n);
    for (int i = 0; i < n; i++)
    {
        int *tmp = malloc(sizeof(int) * n);
        for (int j = 0; j < n; j++)
        {
            tmp[j] = 0;
        }
        matrix[i] = tmp;
    }

    // 内存释放
    for (int i = 0; i < n; i++) {
        free(matrix[i]);
    }
    free(matrix);
}

// 空间复杂度 O(2^n)
// 指数阶常见于二叉树

// 空间复杂度 O(logn)
// 对数阶常见于分治算法。例如归并排序等

稳定性

排序算法的稳定性是指当待排序的数据中有两个相等的元素时，经过排序后这两个元素在数组中的相对位置是否会改变。若不变，那么该排序算法是稳定的，否则为不稳定的。

递归

递归是一种算法策略，它通过重复调用自身的方式实现。

  • 递 程序不断深入地调用自身，通常传入更小或更简化的参数，直到达到“终止条件”。
  • 归 触发“终止条件”后，程序从最深层的递归函数开始逐层返回，汇聚每一层的结果。

递归树

当处理与分治相关的算法问题时，递归往往比迭代的思路更加直观。例如，斐波那契数列的生成。

/**
 * @brief 斐波那契数列
 * 
 */
int fib(int n)
{
    if (n == 1 || n == 2)
        return n - 1;
    int res = fib(n - 1) + fib(n - 2);
    return res;
}

int fib_test(void)
{
    const uint32_t len = 20;
    for(uint32_t i = 1; i <= len; i++)
    {
        printf("%d ", fib(i));
    }
    printf("\n");
}

当递归转化为迭代后，可读性变差，但节约栈空间。 对数列 的函数实现如下：

int get_sum(int n)
{
    if(n == 0)
    {
        return 0;
    }
    return get_sum(n - 1) + n;
}

int get_sum2(int n)
{
    int stack[100];
    int top = -1;    // 栈顶，-1表示栈空
    int res = 0;
    int i = 0;

    for(i = n; i > 0; i--)
    {
        // 压栈
        top++;
        stack[top] = i;
    }

    while(top >= 0)
    {
        // 出栈
        res += stack[top];
        top--;
    }
    return res;
}

void get_sum_test(void)
{
    int n = 10;
    printf("1+2+...+%d = %d\n", n, get_sum(n));
    printf("1+2+...+%d = %d\n", n, get_sum2(n));
}

排序算法是计算机科学中用于将数据元素按照某种顺序进行排列的一类算法。排序算法在数据处理、数据库管理、搜索引擎等领域都有广泛的应用。下面介绍几种常见的排序算法：

  1. 冒泡排序（Bubble Sort）： 冒泡排序是一种简单的排序算法，它通过不断比较相邻元素的大小，并交换位置，使得较大的元素逐渐“冒泡”到数组的末尾。冒泡排序的时间复杂度为O(n^2)，因此在大规模数据排序时效率较低。
  2. 选择排序（Selection Sort）： 选择排序算法每次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。选择排序的时间复杂度也是O(n^2)，但在某些情况下可能比冒泡排序略快一些。
  3. 插入排序（Insertion Sort）： 插入排序算法通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序的时间复杂度为O(n^2)，但在小规模数据排序时效率较高，且对于部分有序的数据，其效率也很高。
  4. 快速排序（Quick Sort）： 快速排序算法采用分治策略，通过选取一个“基准”元素，将待排序的数组划分为两个子数组，一个包含小于基准的元素，另一个包含大于基准的元素。然后递归地对这两个子数组进行排序。快速排序的平均时间复杂度为O(nlogn)，是一种高效的排序算法。
  5. 归并排序（Merge Sort）： 归并排序算法也是采用分治策略，将待排序的数组划分为两个子数组，分别对这两个子数组进行排序，然后将两个有序子数组合并成一个有序数组。归并排序的时间复杂度为O(nlogn)，是一种稳定的排序算法。

除了以上几种常见的排序算法外，还有堆排序、希尔排序、计数排序、桶排序等多种排序算法，每种算法都有其特点和适用场景。在实际应用中，需要根据具体的数据特性和需求选择合适的排序算法。

冒泡排序

/**
 * @brief 冒泡排序
 * 
 * @param flag 0. 升序，1. 降序
 * 
 * @note 冒泡排序是稳定的排序算法
 * 算法复杂度：O(n^2)
 */
void sort_bubble(uint8_t* data, uint32_t len, uint8_t flag)
{
    int i = 0, j = 0;
    uint8_t temp = 0;

    if(flag == 0)
    {
        for (i = 0; i < len; i++)       // 轮次
        {
            for(j = 1; j < len - i; j++)
            {
                if(data[j - 1] > data[j])
                {
                    // 交换
                    temp = data[j - 1];
                    data[j - 1] = data[j];
                    data[j] = temp;
                }
            }
        }
    }
    else
    {
        for (i = 0; i < len; i++)       // 轮次
        {
            for(j = 1; j < len - i; j++)
            {
                if(data[j - 1] < data[j])
                {
                    // 交换
                    temp = data[j - 1];
                    data[j - 1] = data[j];
                    data[j] = temp;
                }
            }
        }
    }
}

插入排序

/**
 * @brief 插入排序
 * 
 * @param flag 0:升序，1：降序
 * 
 * @note 插入排序是稳定的排序算法
 *  算法复杂度：O(n^2)
 */
void sort_insert(uint8_t* data, uint32_t len, uint8_t flag)
{
    int i = 0, j = 0;
    uint8_t key = 0;

    if(flag == 0)
    {
        for (i = 1; i < len; i++)
        {
            key = data[i];
            #if 0
            for(j = i - 1; j >= 0; j--)
            {
                if(key < data[j])
                {
                    data[j + 1] = data[j];  // 向后移动元素
                }
                else
                {
                    break;
                }
            }
            #else
            for(j = i - 1; j >= 0 && (key < data[j]); j--)
            {
                data[j + 1] = data[j];  // 向后移动元素
            }
            #endif
            data[j + 1] = key;     // 插入元素
        }
    }
    else
    {
        for (i = 1; i < len; i++)
        {
            key = data[i];
            for(j = i - 1; j >= 0 && (key > data[j]); j--)
            {
                data[j + 1] = data[j];  // 向后移动元素
            }
            data[j + 1] = key;     // 插入元素
        }
    }
}

快速排序

堆排序

示例2

#include "algo.h"
#include <time.h>

#define NDEBUG

// ==================================== 测试 ====================================
static void Algo_Display(const int *data,int dataLen)
{
    int  i = 0;
    printf("-------------------- INT --------------------\n");
    for(i = 0;i < dataLen; i++)
    {
        if(i % 16 == 0 && i != 0)
        {
            printf("\n");
        }
        printf("%4d ",*(data + i));
    }
    printf("\n");
}

unsigned char Algo_Judge(int * pArray,int iLen,unsigned char mode)
{
    int i = 0;
    for(i = 1; i < iLen; i++)
    {
        if(mode == 0)
        {
            //按照从小到大的顺序排序
            if(pArray[i - 1] > pArray[i])
            {
                return 0;
            }
        }
        else
        {
            //按照从大到小的顺序排序
            if(pArray[i - 1] < pArray[i])
            {
                return 0;
            }
        }
    }
    return 1;
}

// ==================================== 排序算法实现 ====================================
//-----------------------(^_^)-------------------------
// 函数: Algo_SortInsert
// 时间: 2017/5/3__Original__15:46:53
// 功能：插入排序
// 参数: 
// 		int * pArray			数据
// 		int iLen				数据长度
// 		unsigned char mode		0.从小到大 !0.从大到小
// 返回: 
// 		void	
//-----------------------------------------------------
void Algo_SortInsert(int * pArray,int iLen,unsigned char mode)
{
    int i = 0,j = 0;
    int key = 0;
    for(i = 1; i < iLen;i ++)
    {
        key = pArray[i];
        j = i - 1;
        if(mode == 0)
        {
            while(j >= 0 && key < pArray[j])
            {
                pArray[j + 1] = pArray[j]; 
                j --;
            }
        }
        else
        {
            while(j >= 0 && key > pArray[j])
            {
                pArray[j + 1] = pArray[j]; 
                j --;
            }
        }
        pArray[j + 1] = key; 
    }
}


static void Algo_GetMemory(int ** p,int size)
{
    (*p) = (int *)malloc(sizeof(int) * size);
}

//-----------------------(^_^)-------------------------
// 函数: Algo_SoutMerge_0
// 时间: 2017/5/10__Original__11:53:24
// 功能：将两段有序数列重组为一组有序数列
// 参数: 
// 		int * pArray		
// 		int IndexLeftStart		左数列起始下标
// 		int IndexLeftEnd		左数列终止下标
// 		int IndexRightEnd		右数列终止下标（右数列起始下标为 IndexLeftEnd+1 ）
// 返回: 
// 		void	
//-----------------------------------------------------
static void Algo_SoutMerge_0(int * pArray,int IndexLeftStart,int IndexLeftEnd,int IndexRightEnd)
{
    int i = 0;
    int j = 0,k = 0;
    int LenLeft = IndexLeftEnd - IndexLeftStart + 1;		//左 数据个数
    int LenRight = IndexRightEnd - IndexLeftEnd;			//右 数据个数
    int * pArrayLeft = (int *)malloc(LenLeft * sizeof(int));
    int * pArrayRight = (int *)malloc(LenRight * sizeof(int));

#ifndef NDEBUG
    printf("Left = %d,Right = %d\n",LenLeft,LenRight);
#endif
    for(i = 0;i < LenLeft; i++)
    {
        pArrayLeft[i] = pArray[IndexLeftStart + i];
    }
    for(i = 0;i < LenRight; i++)
    {
        pArrayRight[i] = pArray[IndexLeftEnd + 1 + i];
    }

    // ------------------------------------------ 
    //	方法1.利用各自的长度作为检测判断
    // ------------------------------------------
    for(i = IndexLeftStart; i <= IndexRightEnd; i++)
    {
        if(j == LenLeft)
        {
            pArray[i] = pArrayRight[k];
            k ++;
        }
        else if(k == LenRight)
        {
            pArray[i] = pArrayLeft[j];
            j ++;
        }
        else
        {
            if(pArrayLeft[j] <= pArrayRight[k])
            {
                pArray[i] = pArrayLeft[j];
                j ++;
            }
            else
            {
                pArray[i] = pArrayRight[k];
                k ++;
            }
        }
    }
    // ------------------------------------------
    // 	方法2.可以在新建的两个数列的最后，各添加一个
    //  最大值，作为“哨兵”。则可以使代码略微简化。
    //  此处，不再细描述。
    // ------------------------------------------
}

//-----------------------(^_^)-------------------------
// 函数: Algo_SortMerge
// 时间: 2017/5/10__Original__11:57:03
// 功能：请仔细理解该处的递归
// 参数: 
// 		int * pArray		待排序数列
// 		int IndexStart		数列待排序起始下标
// 		int IndexEnd		数列待排序终止下标
// 返回: 
// 		void	
//-----------------------------------------------------
void Algo_SortMerge(int * pArray,int IndexStart,int IndexEnd)
{
    int index = 0;
    if(IndexStart < IndexEnd)
    {
        index = (IndexStart + IndexEnd)/2;
#ifndef NDEBUG
        printf("start = %d\tend = %d\n",IndexStart,IndexEnd);
#endif
        Algo_SortMerge(pArray,IndexStart,index);
        Algo_SortMerge(pArray,index + 1,IndexEnd);
        Algo_SoutMerge_0(pArray,IndexStart,index,IndexEnd);
    }
}


//-----------------------(^_^)-------------------------
// 函数: Algo_MaxHeap
// 时间: 2017/5/10__Original__17:51:07
// 功能：维护堆的性质（以最大堆为例）
// 参数: 
// 		int * pArray	数列	
// 		int index		下标
// 		int iLen		总长度（该数用于判断）
// 返回: 
// 		void	
//-----------------------------------------------------
// ------------------------------------------
// 				堆排序
// 此处宏定义，方便使用
// ------------------------------------------
#define LEFT(x)		((x) << 1)
#define RIGHT(x)	(((x) << 1) + 1)
static void Algo_MaxHeap(int * pArray,int index,int iLen)
{
    int indexleft = LEFT(index);
    int indexright = RIGHT(index);
    int indexlargest;

    // ------------------------------------------
    // 	三个数比较大小，得到最大值的下标
    // ------------------------------------------
    if((indexleft <= iLen) && (pArray[indexleft-1] > pArray[index-1]))
    {
        indexlargest = indexleft;
    }
    else
    {
        indexlargest = index;
    }

    if((indexright <= iLen) && (pArray[indexright-1] > pArray[indexlargest-1]))
    {
        indexlargest = indexright;
    }
    // ------------------------------------------
    // 			交换父节点和最大值
    // ------------------------------------------
    if(indexlargest != index)
    {
        int temp = 0;
        temp = pArray[index-1];
        pArray[index-1] = pArray[indexlargest-1];
        pArray[indexlargest-1] = temp;

        Algo_MaxHeap(pArray,indexlargest,iLen);
    }
}

//-----------------------(^_^)-------------------------
// 函数: Algo_BuiltMaxHeap
// 时间: 2017/5/11__Original__11:00:25
// 功能：建立（最大）堆，自底向上
// 参数: 
// 		int * pArray		
// 		int iLen		
// 返回: 
// 		void	
//-----------------------------------------------------
static void Algo_BuiltMaxHeap(int * pArray,int iLen)
{
    int i = iLen/2;
    for(; i >= 1; i--)
    {
        Algo_MaxHeap(pArray,i,iLen);
    }
}

//-----------------------(^_^)-------------------------
// 函数: Algo_SortHeap
// 时间: 2017/5/11__Original__11:31:03
// 功能：堆排序
// 参数: 
// 		int * pArray	待排序数据
// 		int iLen		待排序数据总长度
// 返回: 
// 		void	
//-----------------------------------------------------
void Algo_SortHeap(int * pArray,int iLen)
{
    int i = iLen,temp = 0;
    int heapsize = iLen;
    Algo_BuiltMaxHeap(pArray,iLen);
    for (i = iLen; i >= 2 ; i--)
    {
        // ------------------------------------------
        // 	每次都交换最大堆的根和最后一个元素
        //  相当于将最大值每次都交换到最后一个位置
        // ------------------------------------------
        temp = pArray[0];
        pArray[0] = pArray[i-1];
        pArray[i-1] = temp;

        // ------------------------------------------
        // 				重新维护最大堆的性质
        //  注意：此处堆中不再包含每次循环的最后一个值
        // ------------------------------------------
        heapsize--;
        Algo_MaxHeap(pArray,1,heapsize);

#ifndef NDEBUG
        printf("测试：%d\n",heapsize);
        Algo_Display(pArray,heapsize);
#endif
    }
}


//-----------------------(^_^)-------------------------
// 函数: Algo_Partition
// 时间: 2017/5/12__Original__11:51:48
// 功能：将数据重排，使得左侧的数据均<=pArray[IndexEnd],
//		右侧的数据，均>pArray[IndexEnd]
// 参数: 
// 		int * pArray		
// 		int IndexStart		
// 		int IndexEnd		
// 返回: 
// 		int	
//-----------------------------------------------------
static int Algo_Partition(int * pArray,int IndexStart,int IndexEnd)
{
    int maxData = pArray[IndexEnd];
    int i,temp;
    int index = IndexStart;
    for(i = IndexStart; i < IndexEnd; i ++)
    {
        if(pArray[i] <= maxData)
        {
            temp = pArray[index];
            pArray[index] = pArray[i];
            pArray[i] = temp;

            index++;
        }
    }
    temp = pArray[index];
    pArray[index] = pArray[IndexEnd];
    pArray[IndexEnd] = temp;
    return index;
}

static int Algo_RandPartition(int * pArray,int IndexStart,int IndexEnd)
{
    // ------------------------------------------
    // 		在原来快速排序基础上，增加一个随机
    // 技术，使得参考值的选取是等概率的
    // ------------------------------------------
    int temp;
    int index = (rand() % (IndexEnd - IndexStart + 1)) + IndexStart;
    temp = pArray[index];
    pArray[index] = pArray[IndexEnd];
    pArray[IndexEnd] = temp;

    return Algo_Partition(pArray,IndexStart,IndexEnd);
}

//-----------------------(^_^)-------------------------
// 函数: Algo_QuickSort
// 时间: 2017/5/12__Original__13:12:27
// 功能：快速排序算法，本质：分治思想
// 参数: 
// 		int * pArray		
// 		int IndexStart		
// 		int IndexEnd		
// 返回: 
// 		void	
//-----------------------------------------------------
void Algo_QuickSort(int * pArray,int IndexStart,int IndexEnd)
{
    int index = 0;
    srand((unsigned int)time(0));
    if(IndexStart < IndexEnd)
    {
        // ------------------------------------------
        // 			1.0 一般方式
        // ------------------------------------------
        //index = Algo_Partition(pArray,IndexStart,IndexEnd);
        // ------------------------------------------
        // 			1.1 在1.0基础上增加了随机技术
        // ------------------------------------------
        index = Algo_RandPartition(pArray,IndexStart,IndexEnd);

        Algo_QuickSort(pArray,IndexStart,index - 1);
        Algo_QuickSort(pArray,index + 1,IndexEnd);
    }
}



// ==================================== 测试 ====================================
void Algo_Test()
{
    int * pArray = NULL;
    int cnt = 0;
    int i = 0;
    time_t clk = 0;

    while(1)
    {
        //输入随机数长度
        printf("input the cnt:\t\n");
        if(1 != scanf("%d",&cnt))
        {
            break;
        }
        if(NULL == (pArray = (int *)malloc(cnt * sizeof(int))))
        {
            printf("malloc failed!");
            return;
        }
        //生成随机数
        srand((unsigned int)time(0));
        for(i = 0; i < cnt;i ++)
        {
            //*(pArray + i) = rand() % cnt;
            *(pArray + i) = rand() % 100;
        }

        // ------------------------------------------
        // 				1.显示排序前
        // ------------------------------------------
        Algo_Display(pArray,cnt);
        // ------------------------------------------
        // 				2.排序算法
        // ------------------------------------------
        clk = clock();
        //1.0 插入排序
//		Algo_SortInsert(pArray,cnt,0);
        //1.1 分治法排序
//		Algo_SortMerge(pArray,0,cnt - 1);
        //1.2 堆排序
//		Algo_SortHeap(pArray,cnt);
        //1.3 快速排序
        Algo_QuickSort(pArray,0,cnt-1);
        // ------------------------------------------
        // 				3.显示排序后
        // ------------------------------------------
        Algo_Display(pArray,cnt);

        // ------------------------------------------
        // 				4.判断排序是否成功
        // ------------------------------------------
        if(0 == Algo_Judge(pArray,cnt,0))
        {
            printf("排序失败！\n");
        }
        else
        {
            printf("排序成功！\n");
        }

        printf("time: %8dms\n",clock() - clk);
    }
}