当前位置:首页 > 公众号精选 > 嵌入式大杂烩
[导读]哈喽,大家好,我是瓜哥,致力于为大家分享互联网各领域干货。这篇文章可以说是一本书了,排版,码字耗费了瓜哥很长的时间,10 万字C语言从入门到精通保姆级教程2021年版,觉得有价值记得一键三连支持。计数排序(CountingSort)计数排序是一个非基于比较的排序算法,该算法于19...

哈喽,大家好,我是瓜哥,致力于为大家分享互联网各领域干货。

这篇文章可以说是一本书了,排版,码字耗费了瓜哥很长的时间,10 万 字 C 语言从入门到精通保姆级教程2021年版,觉得有价值记得一键三连支持。

计数排序(Counting Sort)

  • 计数排序是一个非基于比较的排序算法,该算法于1954年由 Harold H. Seward 提出。它的优势在于在对一定范围内的整数排序时,快于任何比较排序算法。
  • 排序思路:
  • 1.找出待排序数组最大值
  • 2.定义一个索引最大值为待排序数组最大值的数组
  • 3.遍历待排序数组, 将待排序数组遍历到的值作新数组索引
  • 4.在新数组对应索引存储值原有基础上 1
  • 简单代码实现:
int main()
{
    // 待排序数组
    int nums[5] = {3, 1, 2, 0, 3};
    // 用于排序数组
    int newNums[4] = {0};
    // 计算待排序数组长度
    int len = sizeof(nums) / sizeof(nums[0]);
    // 遍历待排序数组
    for(int i = 0; i < len; i ){
        // 取出待排序数组当前值
        int index = nums[i];
        // 将待排序数组当前值作为排序数组索引
        // 将用于排序数组对应索引原有值 1
        newNums[index] = newNums[index]  1;
    }
    
    // 计算待排序数组长度
    int len2 = sizeof(newNums) / sizeof(newNums[0]);
    // 输出排序数组索引, 就是排序之后结果
    for(int i = 0; i < len2; i ){
        for(int j = 0; j < newNums[i]; j ){
            printf("%i\n", i);
        }
    }
    /*
    // 计算待排序数组长度
    int len2 = sizeof(newNums) / sizeof(newNums[0]);
    // 还原排序结果到待排序数组
    for(int i = 0; i < len2; i ){
        int index = 0;
        for(int i = 0; i < len; i ){
            for(int j = 0; j < newNums[i]; j ){
                nums[index ] = i;
            }
        }
    }
    */
    return 0;
}

选择排序

选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小元素,然后放到排序序列末尾。以此类推,直到所有元素均排序完毕。
  • 排序思路:
  • 假设按照升序排序
  • 1.用第0个元素和后面所有元素依次比较
  • 2.判断第0个元素是否大于当前被比较元素, 一旦小于就交换位置
  • 3.第0个元素和后续所有元素比较完成后, 第0个元素就是最小值
  • 4.排除第0个元素, 用第1个元素重复1~3操作, 比较完成后第1个元素就是倒数第二小的值
  • 以此类推, 直到当前元素没有可比较的元素, 排序完成
  • 代码实现:
// 选择排序void selectSort(int numbers[], int length) {        // 外循环为什么要-1?    // 最后一位不用比较, 也没有下一位和它比较, 否则会出现错误访问    for (int i = 0; i < length; i ) {        for (int j = i; j < length - 1; j ) {            // 1.用当前元素和后续所有元素比较            if (numbers[i] < numbers[j   1]) {                //  2.一旦发现小于就交换位置                swapEle(numbers, i, j   1);            }        }    }}// 交换两个元素的值, i/j需要交换的索引void swapEle(int array[], int i, int j) {    int temp = array[i];    array[i] = array[j];    array[j] = temp;}

冒泡排序

  • 冒泡排序(Bubble Sort)是一种简单的排序算法。它重复 地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
  • 排序思路:
  • 假设按照升序排序
  • 1.从第0个元素开始, 每次都用相邻两个元素进行比较
  • 2.一旦发现后面一个元素小于前面一个元素就交换位置
  • 3.经过一轮比较之后最后一个元素就是最大值
  • 4.排除最后一个元素, 以此类推, 每次比较完成之后最大值都会出现再被比较所有元素的最后
  • 直到当前元素没有可比较的元素, 排序完成
  • 代码实现:
// 冒泡排序
void bubbleSort(int numbers[], int length) {
    for (int i = 0; i < length; i ) {
        // -1防止`角标越界`: 访问到了不属于自己的索引
        for (int j = 0; j < length - i - 1; j ) {
           //  1.用当前元素和相邻元素比较
            if (numbers[j] < numbers[j   1]) {
                //  2.一旦发现小于就交换位置
                swapEle(numbers, j, j   1);
            }
        }
    }
}
// 交换两个元素的值, i/j需要交换的索引
void swapEle(int array[], int i, int j) {
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

插入排序

  • 插入排序(Insertion-Sort)的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。
  • 排序思路:
  • 假设按照升序排序
  • 1.从索引为1的元素开始向前比较, 一旦前面一个元素大于自己就让前面的元素先后移动
  • 2.直到没有可比较元素或者前面的元素小于自己的时候, 就将自己插入到当前空出来的位置
  • 代码实现:
int main()
{
    // 待排序数组
    int nums[5] = {3, 1, 2, 0, 3};
    // 0.计算待排序数组长度
    int len = sizeof(nums) / sizeof(nums[0]);

    //  1.从第一个元素开始依次取出所有用于比较元素
    for (int i = 1; i < len; i )
    {
        // 2.取出用于比较元素
        int temp = nums[i];
        int j = i;
        while(j > 0){
            // 3.判断元素是否小于前一个元素
            if(temp < nums[j - 1]){
                // 4.让前一个元素向后移动一位
                nums[j] = nums[j - 1];
            }else{
                break;
            }
            j--;
        }
        // 5.将元素插入到空出来的位置
        nums[j] = temp;
    }
}
int main()
{
    // 待排序数组
    int nums[5] = {3, 1, 2, 0, 3};
    // 0.计算待排序数组长度
    int len = sizeof(nums) / sizeof(nums[0]);

    //  1.从第一个元素开始依次取出所有用于比较元素
    for (int i = 1; i < len; i )
    {
        // 2.遍历取出前面元素进行比较
        for(int j = i; j > 0; j--)
        {
            // 3.如果前面一个元素大于当前元素,就交换位置
            if(nums[j-1] > nums[j]){
                int temp = nums[j];
                nums[j] = nums[j - 1];
                nums[j - 1] = temp;
            }else{
                break;
            }
        }
    }
}

希尔排序

  • 1959年Shell发明,第一个突破O(n2)的排序算法,是简单插入排序的改进版。它与插入排序的不同之处在于,它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。
  • 排序思路:
  • 1.希尔排序可以理解为插入排序的升级版, 先将待排序数组按照指定步长划分为几个小数组
  • 2.利用插入排序对小数组进行排序, 然后将几个排序的小数组重新合并为原始数组
  • 3.重复上述操作, 直到步长为1时,再利用插入排序排序即可
  • 代码实现:
int main(){    // 待排序数组    int nums[5] = {3, 1, 2, 0, 3};    // 0.计算待排序数组长度    int len = sizeof(nums) / sizeof(nums[0]);// 2.计算步长    int gap = len / 2;    do{        //  1.从第一个元素开始依次取出所有用于比较元素        for (int i = gap; i < len; i )        {            // 2.遍历取出前面元素进行比较            int j = i;            while((j - gap) >= 0)            {                printf("%i > %i\n", nums[j - gap], nums[j]);                // 3.如果前面一个元素大于当前元素,就交换位置                if(nums[j - gap] > nums[j]){                    int temp = nums[j];                    nums[j] = nums[j - gap];                    nums[j - gap] = temp;                }else{                    break;                }                j--;            }        }        // 每个小数组排序完成, 重新计算步长        gap = gap / 2;    }while(gap >= 1);}
江哥提示: 对于初学者而言, 排序算法一次不易于学习太多, 咋们先来5个玩一玩, 后续继续讲解其它5个 公众号代码情缘欢迎关注

折半查找

  • 基本思路
  • 在有序表中,取中间元素作为比较对象,若给定值与中间元素的要查找的数相等,则查找成功;若给定值小于中间元素的要查找的数,则在中间元素的左半区继续查找;
  • 若给定值大于中间元素的要查找的数,则在中间元素的右半区继续查找。不断重复上述查找过 程,直到查找成功,或所查找的区域无数据元素,查找失败
  • 实现步骤

  • 在有序表中,取中间元素作为比较对象,若给定值与中间元素的要查找的数相等,则查找成功;

  • 若给定值小于中间元素的要查找的数,则在中间元素的左半区继续查找;

  • 若给定值大于中间元素的要查找的数,则在中间元素的右半区继续查找。

  • 不断重复上述查找过 程,直到查找成功,或所查找的区域无数据元素,查找失败。

  • 代码实现

int findKey(int values[], int length, int key) {
    // 定义一个变量记录最小索引
    int min = 0;
    // 定义一个变量记录最大索引
    int max = length - 1;
    // 定义一个变量记录中间索引
    int mid = (min   max) * 0.5;
    
    while (min <= max) {
        // 如果mid对应的值 大于 key, 那么max要变小
        if (values[mid] > key) {
            max = mid - 1;
            // 如果mid对应的值 小于 key, 那么min要变
        }else if (values[mid] < key) {
            min = mid   1;
        }else {
            return mid;
        }
        // 修改完min/max之后, 重新计算mid的值
        mid = (min   max) * 0.5;
    }
    return -1;
}

进制转换(查表法)

  • 实现思路:
  • 将二进制、八进制、十进制、十六进制所有可能的字符都存入数组
  • 利用按位与运算符和右移依次取出当前进制对应位置的值
  • 利用取出的值到数组中查询当前位输出的结果
  • 将查询的结果存入一个新的数组, 当所有位都查询存储完毕, 新数组中的值就是对应进制的值
  • 代码实现
#include 
void toBinary(int num)
{
    total(num, 1, 1);
}
void toOct(int num)
{
    total(num, 7, 3);
}
void toHex(int num)
{
    total(num, 15, 4);
}

void total(int num , int base, int offset)
{
    //    1.定义表用于查询结果
    char cs[] = {
        '0''1''2''3''4''5',
        '6''7''8''9''a''b',
        'c''d''e''f'
    };
    //    2.定义保存结果的数组
    char rs[32];
    //    计算最大的角标位置
    int length = sizeof(rs)/sizeof(char);
    int pos = length;//8

    while (num != 0) {
        int index = num 
本站声明: 本文章由作者或相关机构授权发布,目的在于传递更多信息,并不代表本站赞同其观点,本站亦不保证或承诺内容真实性等。需要转载请联系该专栏作者,如若文章内容侵犯您的权益,请及时联系本站删除。
关闭
关闭