06-C语言基本排序算法

计数排序(Counting Sort)

• 排序思路
  • 1.找出待排序数组的最大值
  • 2.定义一个索引最大值为待排序数组最大值的数组
  • 3.遍历待排序数组,将待排序数组遍历到的值作新数组索引
  • 4.在新数组对应索引存储值原有基础上+1

• 注意点:

  • 1.数组索引必须和需要排序范围一致,例如需要排序的是0~9,那么数组索引必须是0`9

  • 2.遍历数组时每次遇到需要排序的数,就往对应的索引的元素存入原来的值加1;

  • 3.输出时输出的是数组的索引;

  • 4.计数排序只能用于有限数字的排序

  • 5.计数排序的效率是最高的

#include <stdio.h>
void printArray(int nums[], int len);
int main()
{
    //需求: 要求从键盘输入5个 0~9的数, 然后排序之后输出
    //计数排序:
    // 定义一个0~9数组
    int nums[10] = {0};
    // 接收数组的长度
    int len = sizeof(nums) / sizeof(nums[0]);
    // 定义对应的索引
    int value = -1;
    // 循环输入一数据
    for(int i = 0; i < 5; i++){
        // 提示用户输入
        printf("第%i次:请输入一个0~9的数\n",i+1);
        // 接收用户输入
        scanf("%i",&value);
        // 将用户输入的数据作为索引,往数组对应的索引存入
        nums[value] += 1;
    }
    printf("----------------\n");
    // 将排序后输入
    for(int i = 0; i < len; i++){
        // 是否是重复数据
        for(int j = 0; j < nums[i]; j++){
            printf("%i\n", i);
        }
    }
    //printArray(nums, 10);
    return 0;
}

void printArray(int nums[], int len){
    for(int i = 0; i < len; i++){
        printf("nums[%i] = %i\n", i, nums[i]);
    }
}

选择排序

• 排序思路
  • 假设按照升序排序
  • 1.用第0个元素和后面所有元素依次比较
  • 2.判断第0个元素是否大于当前被比较的元素,一旦小于就交换位置;
  • 3.第0个元素和后续所有元素比较完成后,第0个元素就是最小值
  • 4.排除第0个元素,用第一个元素重复1-3操作,比较完成后第一个元素就是倒数第二小的值
  • 以此类推,直到当前元素没有可比较的元素,排序完成

#include <stdio.h>
void printArray(int nums[], int len);
int main()
{
    // 需求: 要求从键盘输入5个 0~9的数, 然后排序之后输出
    // 选择排序
    // 定义一个0~9数组
    int nums[5] = {0};
    // 接收数组的长度
    int len = sizeof(nums) / sizeof(nums[0]);
    // 循环输入一数据
    for(int i = 0; i < len; i++){
        // 提示用户输入
        printf("第%i次:请输入一个0~9的数\n",i+1);
        // 接收用户输入
        scanf("%i",&nums[i]);
    }
    printf("----------------\n");
    /*
     * 实现选择排序的步骤:
     * 1. 打印倒三角
     * 2. 输出需要比较的索引
     * 3. 添加条件满足就交换位置
     *
    */
    for (int i = 0; i < len -1; i++){
        for(int j = i ; j < len-1; j++){
            // printf("*");
            // printf("%i,%i\n",i,j+1);
            if(nums[i] > nums[j+1]){
                int temp = nums[i];
                nums[i] = nums[j+1];
                nums[j+1] = temp;
            }

        }
        //printf("\n");
    }
    printArray(nums, len);
    return 0;
}

void printArray(int nums[], int len){
    for(int i = 0; i < len; i++){
        printf("nums[%i] = %i\n", i, nums[i]);
    }
}

冒泡排序

• 排序思路
  • 假设按照升序排序
  • 1.从第0个元素开始,每次都用相邻两个元素进行比较
  • 2.一旦发现后面一个元素小于前面一个元素就交换位置
  • 3.经过一轮比较之后最后一个元素就是最大值
  • 4.排除最后一个元素,以此类推,每次比较完成之后最大值都会出现再被比较所有元素的最后;
  • 5.知道当前元素没有可比较的元素,排序完成;

#include <stdio.h>
void printArray(int nums[], int len);
int main()
{
    // 需求: 要求从键盘输入5个 0~9的数, 然后排序之后输出
    // 冒泡排序
    // 定义一个0~9数组
    int nums[5] = {0};
    // 接收数组的长度
    int len = sizeof(nums) / sizeof(nums[0]);
    // 循环输入一数据
    for(int i = 0; i < len; i++){
        // 提示用户输入
        printf("第%i次:请输入一个0~9的数\n",i+1);
        // 接收用户输入
        scanf("%i",&nums[i]);
    }
    printf("----------------\n");
    /*
     * 实现选择排序的步骤:
     * 1. 打印倒三角
     * 2. 输出需要比较的索引
     * 3. 添加条件满足相邻两个数就交换位置
     *
    */
    for (int i = 0; i < len -1; i++){
        for(int j = 0 ; j < len - i - 1; j++){
            // printf("*");
            // printf("%i,%i\n",j,j+1);
            if(nums[j] > nums[j+1]){
                int temp = nums[j];
                nums[j] = nums[j+1];
                nums[j+1] = temp;
            }

        }
        //printf("\n");
    }
    printArray(nums, len);
    return 0;
}

void printArray(int nums[], int len){
    for(int i = 0; i < len; i++){
        printf("nums[%i] = %i\n", i, nums[i]);
    }
}

• 封装冒泡和选择函数

#include <stdio.h>
void printArray(int value[],int len);
void selectSort(int Value[], int len);
void bubbleSort(int value[],int len);
void swapEle(int value[], int i, int j);
int main()
{
    /*
        选择排序: 就是每次拿第一个数用于与之后的数进行比较,
        经过一轮操作后,最值出现在前面,重复上诉操作

        冒泡排序: 每次都是用相邻两个数进行比较,经过一轮比较后
        最值出现在右边


        步骤:
            1.打印倒三角
            2.实现输出需要比较的索引
            3.添加条件,交换位置

    */

    int nums[5] = {3, 14, 2, 8, 6};
    int len = sizeof(nums) / sizeof(nums[0]);
    printArray(nums, len);
    printf("------------------\n");
    selectSort(nums,len); // 选择排序
    printArray(nums, len);
    printf("------------------\n");
    bubbleSort(nums,len); // 冒泡排序
    printArray(nums, len);
    return 0;
}




// 选择排序
void selectSort(int value[], int len){
    for(int i = 0; i< len - 1; i++){
        for(int j = i; j < len -1; j++){
            // printf("*");
            // printf("i=%i, j=%i\t",i,j + 1);
            if(value[i] > value[j + 1]){
//                int temp = value[i];
//                value[i] = value[j + 1];
//                value[j + 1] = temp;
                swapEle(value,i, j+1);
            }
        }
        //printf("\n");
    }
}
// 冒泡排序
void bubbleSort(int value[],int len){
    for(int i = 0; i < len -1; i++){
        for(int j = 0; j < len - i - 1; j++){
            // printf("*");
            // printf("%i,%i\t",j,j+1);
            if(value[j] > value[j + 1]){
//                int temp = value[j];
//                value[j] = value[j + 1];
//                value[j + 1] = temp;
                swapEle(value, j , j+1);
            }
        }
        //printf("\n");
    }
}

/*
    注意: 在判断函数内存会不会修改外面的实参的时候
    只看函数形参是什么类型:
    如果函数形参是基本数据类型,那么修改形参就不会影响实参
    如果函数形参是数组类型,那么修改形参就会影响实参
*/
// void swapEle(int num1, int num2){  // 错误写法
void swapEle(int value[], int i, int j){
    int temp = value[i];
    value[i] = value[j];
    value[j] = temp;
}

// 输出
void printArray(int value[],int len){
    for(int i = 0; i < len; i++){
        printf("value[%i] = %i\n", i, value[i]);
    }
}

插入排序

• 排序思路
  • 假设按照升序排序
  • 1.从索引为1的元素开始向前比较,一旦前面一个元素大于自己就让前面的元素先后移动
  • 2.直到没有可比较元素或者前面的元素小于自己的时候,就将自己插入到当前空出来的位置;

• 方式一:

#include <stdio.h>
void printArray(int nums[], int len);
int main()
{
    // 插入排序
    int nums[4] = {4, 6, 2, 8};
    int len = sizeof(nums) / sizeof(nums[0]);
    for(int i = 1; i < len; i++){
        // 取出用于和其它元素比较的元素
        int temp = nums[i];
        int j = i;
        while(j > 0){
            //printf("%i,%i\n",j,j-1);
            /*
             * 1,0  : i = 1; temp = 2; j = 1
             *        nums[1] < nums[0];  小于就交换
             *
             * 2,1  : i = 2 ; temp = 1;
             *        j = 2 ; j - 1 = 1;
             *        nums[2] < num[1];   小于就交换
             *
             * 1,0  : j = 1; j - 1 = 0;
             *         nums[1] < nums[0]; 小于就交换
             *         // 完成索引号为2的元素比较
             *
             * 3,2
             * 2,1
             * 1,0
            */

            if(temp < nums[j-1]){
               nums[j] = nums[j -1];

            }else{
                break;
            }
            j--;
        }
        // 此时nums[j] = nums[j -1];
        nums[j] = temp;
    }
     printArray(nums,len);
    return 0;
}

void printArray(int nums[], int len){
    for(int i =0; i < len; i++){
         printf("nums[%i] = %i\n", i, nums[i]);
    }
}

• 方式二:

#include <stdio.h>
void printArray(int nums[], int len);
int main()
{
    int nums[4] = {4, 6, 2, 8};
    int len = sizeof(nums) / sizeof(nums[0]);
    for(int i = 0; i < len ; i++){
        for(int j = i; j > 0; j--){
            //printf("%i,%i\n",j,j-1);
            if(nums[j] < nums[j -1]){
                int temp = nums[j];
                nums[j] = nums[j -1];
                nums[j -1] = temp;
            }else{
                break;
            }
        }
    }
    printArray(nums, len);
    return 0;
}

void printArray(int nums[], int len){
    for(int i =0; i < len; i++){
         printf("nums[%i] = %i\n", i, nums[i]);
    }
}

希尔排序

• 排序思路
  • 1.希尔排序可以理解为插入排序的升级版,带将待排序数组按照指定步长划分为几个小数组
  • 2.利用插入排序对小数组进行排序,然后将几个排序的小数组重新合并为原始数组;
  • 重复上诉操作,直到步长为1,再利用插入排序即可;
• 希尔排序和插入排序的唯一的区别就是插入排序的步长是1,而希尔排序的步长是我们自己计算的;

#include <stdio.h>
void printArray(int nums[], int len);
int main()
{
    // 希尔排序
    int nums[8] = {4, 7, 6, 3, 1, 5, 2};
    int len = sizeof(nums) / sizeof(nums[0]);
    int gap = len / 2;
    // printf("%i\n",gap);
    //       i = 3;     i< 7
    // printArray(nums,len);
    do{
        for(int i = gap; i < len; i++){
            for(int j = i; j - gap >= 0; j--){
                //printf("%i, %i\n",j,j-gap);
                if(nums[j] < nums[j - gap]){
                    int temp = nums[j];
                    nums[j] = nums[j - gap];
                    nums[j - gap] = temp;
                }else{
                    break;
                }
            }
            // printf("\n");
        }
        // printf("---------- gap = %i ----------------\n",gap);
        gap = gap / 2;
    }while(gap >=1);
    printArray(nums,len);
    return 0;
}
void printArray(int nums[], int len){
    for(int i =0; i < len; i++){
         printf("nums[%i] = %i\n", i, nums[i]);
    }
}

折半查找

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

• 注意点: 折半查找必须是有序数组

#include <stdio.h>

int main()
{
    // 需求: 有一个有序的数组, 要求找到指定元素对应的位置
    // 折半查找
    int nums[5] = {1, 3, 5, 7, 9};
    // 定义要查找的数
    int key = 9;
    int len = sizeof(nums) / sizeof(nums[0]);
    // 定义数组的最小和最大索引
    int min = 0;
    int max = len -1;
    int mid = (min + max) / 2;
    while(max >= min){
        if(key > nums[mid]){
            min = mid + 1;
            mid = (min + max) / 2;
        }else if(key < nums[mid]){
            max = mid -1;
            mid = (min + max) / 2;
        }else{
            printf("index = %i\n", mid);
            return;
        }
    }
    return 0;
}

• 现在有一个有序的数组, 还有一个key, 要求找到key插入数组之后还能保持数组是有序的位置

#include <stdio.h>

int main()
{
    // 现在有一个有序的数组, 还有一个key,
    // 要求找到key插入数组之后还能保持数组是有序的位置
    int nums[] = {1, 3, 5, 7, 9};
    int key = 2;
    int len = sizeof(nums) / sizeof(nums[0]);
    int min = 0;
    int max = len -1;
    int mid = (min + max) / 2;
    while(max >= min){
        if(key > nums[mid]){
            min = mid +1;
            mid = (min + max) / 2;
        }else if(key < nums[mid]){
            max = mid -1;
            mid = (min + max) / 2;
        }
    }
    printf("index = %i \n", min);
    return 0;
}