【九月打卡】第17天【养成记】嵌入式挑战第17天 学习快速排序

课程名称:

物联网/嵌入式工程师

课程章节(阶段二第七周 快速排序 1-7):

快速排序课程链接

老师:

大白老师

课程内容:

学习常用排序中的快速排序

学习笔记:

概念:

• 快速排序: 编程中经常使用到的一种排序方法,主要采用了分治法的想法。

思路:

1. 先从数组中选取一个数作为基准数，用key来表示。（通常选取数组的第一个元素）
2. 开始分的过程，一般是定义两个变量i和j，分别表示第一个元素和最后一个元素的下标
3. 从j开始依次向前走，拿a[j]和key比较， 若是a[j] < key，把a[j]放到a[i]的位置。否则向前走。
4. 从i开始向后走,拿a[j]和key比较， 若是a[i] > key, a[i]的值放到a[j]的位置。否则向后走。
5. 如此循环
6. 我们将比key小的值全部存放到key的左边，将比key的值全部f存储到key的右边

主要代码实现

void quick_sort(int a[],int low,int high)
{
        int i = 0,j = 0;
        int key = 0;
        i = low;  //保存第一个有效元素的下标
        j = high; //保存最后一个有效元素的下标

        key = a[low];

        while(i < j)
        {
                while(i < j && a[j] >= key )
                        j--;

                if(i < j)
                {
                        a[i] = a[j];
                }

                while(i < j && a[i] <= key)
                        i++;

                if(i < j)
                {
                        a[j] = a[i];        
                }
        }

        //填充key的值到a[i]的值
        a[i] = key;

        if(j - 1 > low)
        {
                quick_sort(a,low,j - 1);        
        }

        if(i + 1 < high)
        {
                quick_sort(a,i + 1,high);        
        }

        return ;
}

打卡:

课程评价

本节主要讲解快速排序，代码确实不容易想，也比较复杂。大白老师说很多朋友对快速排序有畏难情绪，认为快速排序使用到了递归，是一种非常复杂的程序，其实未必如此。只要我们使用好了方法，就可以自己实现快速排序。感谢大白老师。