计数排序

• 注意点和使用场景

  • 计数排序只能用于有限数据的排序,并且数字不是非常大的时候

• 计数排序的条件
  1.数组索引必须和排序范围一致,例如如果排序的数字是0_{9,那么数组索引必须为0}9
  2.遍历数组时每次遇到需要排序的数, 就往对应索引的元素中存入原来的值+1
  3.输出数据时输出的是数组的索引,索引中存储的时表示是否需要该索引并且输出次数的值

代码如下:

//需求:输入5个0~9的值,按由小到大输出
int num[10] = {0};
int len = sizeof(nums) / sizeof(nums[1]);
int value = -1;
for(int i = 0;i < 5;i++)
{
     printf("请输入一个数字\n");
     scanf("%i",&value);
     num[value] += 1;
}
for(int i = 0;i < len;i++)
{
    for(int j = 0;j < num[i];j++)
    {
      printf("%i ",i);
    }
}

选择排序

• 选择排序的逻辑
  1.选择排序是先将第一个元素和后面所有元素比较,如果按由小到大排序输出,那么第一个元素如果比后面的元素小就交换
  2.选择排序在经过第一轮比较后最值出现在第一个元素上,如果有n个元素进行排序,那么进行n-1轮比较就产生了最值

//在键盘上输入5个数字,按由小到大输出
//第一轮进行4次比较,第二轮进行3次比较,第三轮进行2次比较,第四轮进行一次比较
//和我们打印图形时打印的倒三角十分相似
int num[5] = {0};
int len = sizeof(nums) / sizeof(nums[1]);
for(n = 0;n < len;n++)
{
     printf("请输入一个数字\n");
     scanf("%i",&num[n]);
}
//进行比较
for(i = 0;i < len - 1;i++)
{
    for(j = i;j < len - 1;j++)
    {
        if(num[i] > num[j+1])
      {
          int temp = num[i];
          num[i] = num[j+1];
          num[j+1] = temp; 
      }
    }
}
//输出
for(int i = 0;i < len;i++)
{
printf("%i ",num[i]);
}

冒泡排序

• 冒泡排序的逻辑
  1.让相邻两个元素进行比较,如果按由小到大输出,那么如果前面一个元素大于后面一个元素就交换
  2.经过第一轮比较,最值出现在最后一个元素上,那么需要经过n-1轮比较

代码如下:

//在键盘上输入5个数字,按由小到大输出
//第一轮进行4次比较,第二轮进行3次比较,第三轮进行2次比较,第四轮进行一次比较
//和我们打印图形时打印的倒三角十分相似
int num[5] = {0};
int len = sizeof(num) / sizeof(num[1]);
for(n = 0;n < len;n++)
{
     printf("请输入一个数字\n");
     scanf("%i",&num[n]);
}
//进行比较
for(i = 0;i < len -1;i++)
{
    for(j = 0;j < len - 1 -i;j++)
    {
      if(num[j] > num[j+1])
        {
          int temp = num[j]
               num[j] = num[j+1];
               num[j+1] = temp;
        }
    }
}
for(int i = 0;i < len;i++)
{
printf("%i ",num[i]);
}

插入排序

• 插入排序逻辑
  1.插入排序从第1个元素开始,依次向前比较,如果按由小到大输出,如果前一个元素比自己打,就交换位置如果比自己小就不交换
  2.如果有n个元素,则需要进行n-1次插入比较

代码如下:

 //需求:从键盘上输入5个数字,按由小到大输出
    //第一轮往前比较一次,第二轮比较两次......
    //和我们打印图形输出尖尖朝上的三角形很类似
    int num[5] = {0};
    int len = sizeof(num) / sizeof(num[1]);
    for(int n = 0;n < len;n++)
    {
         printf("请输入一个数字\n");
         scanf("%i",&num[n]);
    }
    //进行比较
    for(int i = 1;i < len;i++){
        int j = i;
        int temp = num[i];//取出用于比较的元素
        while(j > 0){
            //j>0意味着需要比较
            if(temp < num[j - 1]){
                //把num[j-1]这个元素向后挪一位,而后面的元素是num[j]也是temp
                num[j] = num[j-1];
            }else{
                break;
            }
            j--;
        }
        //循环结束后 j如果全部比较完,j应该是0,如果未全部比较完就跳出元素,则j应该就是那个num[j]>num[j-1]的j
        //这个时候num[j]空缺,未赋值,这个值就应该是用于比较的temp
        num[j] = temp;
    }
for(int i = 0;i < len;i++)
{
printf("%i ",num[i]);
}

• 插入排序的第二种方法
• 注意点:此方法没有第一种方法效率高,交换次数更多

#include <stdio.h>

int main()
{
    int num[5] = {5,1,3,7,9};
    //1.将每个元素和它前面的元素比较,如果按由小到大输出,比较的元素比前面一个元素小则交换否则不交换
    //2.一共5个元素要比四次
    int len = sizeof(num) / sizeof(num[0]);
    for(int i = 1;i < len;i++){
        for(int j = i;j > 0;j--){
            if(num[j]<num[j-1]){
                int temp = num[j];
                num[j] = num[j-1];
                num[j-1] = temp;
            }
        }
    }
    for(int n = 0;n < len;n++){
        printf("num[%i] = %i\n",n,num[n]);
    }
    return 0;
}