目 录CONTENT

文章目录

C语言基础——顺序表处理

smallkun
2022-04-17 / 0 评论 / 0 点赞 / 106 阅读 / 2,214 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-06-12,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我删除。

顺序表处理

二分查找

二分查找原理

  • 线性袁中的记录必须按关键码有序
  • 必须采用顺序存储

基本思想

  • 在有序表中,或中间记录作为比较对象,若给定值与中间记录的关键码相等,则查找成功;若给定值
    小于中间记家的关键码,则在中间记灵的左半区继续查找;若给定值大于中间记录的关键码,则在中
    间记录的右半区继续查找。不断重复上述过程,直到查找成功,或所查找的区域无记录,查找失购

image-20220416122640085

二分查找举例

  • 例如,考虑一个已经进行升序排列的整数序列,并且我们将要查找数字68:
    image-20220416123440508

  • 我们对序列中目标值的位置感兴趣,因此我们把搜索空间看成序列的索引。

  • 初始时,搜索空间包含从索引1到11。由于搜索的空间是一个区闻,它足够用来存储最低和最高两
    个索引。正如上面所描述的,我们现在选择中间值,也就是萦引为6的值(1和11之间的中间点)
    这个值是41,比目标值要小。

  • 查找数字terage=68
    image-20220416123709690

    image-20220416123740781image-20220416123916892

    image-20220416124211568

    image-20220416124243314

    image-20220416124308660

  • 二分查找流程图
    image-20220416124344773

#include "stdio.h"


int binarySearch(int array[], int targetNumber, int low, int high);
int main(){

    int array[] = {0, 4, 13, 19, 22, 41, 55, 68, 72, 81, 98};

    int targetNumber, result;

    int arrLength = sizeof(array)/sizeof(array[0]);
    printf("请输入在以下数组中要查找的数字:\n");

    for (int i = 0; i < arrLength; i++)
    {
        if(i != arrLength - 1)
            printf("%d ", array[i]);
        else
            printf("%d\n", array[i]);
    }
    scanf("%d", &targetNumber);

    result = binarySearch(array, targetNumber, 0, arrLength - 1);
    
    if (result == -1){
        printf("没有找到数字%d\n", targetNumber);
    }else{
        printf("找到了,%d是第%d个数字。\n",targetNumber, result);
    }






    return 0;
}

int binarySearch(int array[], int targetNumber, int low, int high){

    if (low > high){
        return -1;
    }

    int mid = (high + low)/2;

    if (array[mid] == targetNumber){
        return mid;
    }else if(array[mid] < targetNumber){
        low = mid + 1;
    }else{
        high = mid - 1;
    }
    return binarySearch(array, targetNumber, low, high);
}

小结

  • 二分查找的前提条件
    数据必须有序
  • 二分查找的优势
    比顺序查找速度快很多
  • 二分查找可以解决的问题
    查找数据
    解决数学问题
    解决几何问题

冒泡排序

冒泡排序的原理

  • 冒泡排序和气泡在水中不断往上冒的情况有些类似。气泡大的(大的数搶,在下面,气泡小的小的数据)在上面。
  • 冒泡排序的编程原理对存放原始数据的数组,按从前往后的方向进行多次扫描,每次扫描称为一趟。当戋现相祁两少数据的次序与排序要求的大小次序不符合时,即将这两个数据进行互换。这样,较小的数据就会逐个向前移动,好象气泡向上浮起一样。

冒泡排序的执行流程

  • 例:用冒泡排序的方法将下面一组无序数组排成从小到大的顺序。

排成从小到大的顺序。

{49, 38, 65, 97, 76, 13, 27, 49}

  • 分析:首先为了方便分析,我们把所给的数据先用一个表格列出来,如下:

原始数据和序号
image-20220416131014297

第一次排序步骤:

image-20220416131258135

image-20220416131338262

问:为了使这一组无序数组完全按照要求排成从小到大,我们还需不需要再继续排序呢?
image-20220416131634385

  • 算法流程图
    image-20220416131941471
    image-20220416132032020
  • 代码
#include "stdio.h"
#include "stdlib.h"

void printArray(int array[], int length);
void bubbleSort(int array[], int length);
int main(){

    int array[] = {49, 38, 65, 97, 76, 13, 27, 49};
    int length = sizeof(array)/sizeof(array[0]);

    printf("待排序的数组是:");
    printArray(array, length);

    bubbleSort(array, length);

    printf("排序后的数组是:");
    printArray(array, length);    



    return 0;
}

void printArray(int array[], int length){
    for (int i = 0; i < length; i++)
    {
        if (i == 0)
            printf("%d", array[i]);
        else
            printf(" %d", array[i]);
    }
    printf("\n");
}
void bubbleSort(int array[], int length){
    
    for (int i = 0; i < length - 1; i++)
    {
        for (int j = 0; j < length - 1 - i; j++)
        {
            if (array[j] > array[j+1]){
                int temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
            }
        }   
    }
}

//优化
void bubbleSort(int array[], int length){
    int flag = 0;
    for (int i = 0; i < length - 1; i++)
    {
        for (int j = 0; j < length - 1 - i; j++)
        {
            flag = 1;
            if (array[j] > array[j+1]){
                int temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
            }
        }
        if (!flag) break;
    }
}

冒泡排序的时间性能分析

image-20220416133414020


选择排序

  • 选择排序的主要操作是选择,其主要思想是:每趟排序在当前待排序房列中选出关键码最小的记录,添加到有序序列中。
    image-20220416133917317

选择排序的原理

  • 基本思想:第i趟在n-i+l(i-1,2,n-1)个记录中选取关键码最小的记录作为有序序列中的第i个记录。
    需要解决的关键问题?

    1. 如何在待排序序列中选出关键码最小的记录?
      解决方法:
      定义一个整形变量min,用于记录在一趟比较的过程中关键码最小的记录位置。
      image-20220416134931236

      min = i;
      for(j=i+1;j<n;j++)
          if(r[j] < r[min])
              min = j;
      if(min != i)
          r[i]<-->r[index];
      
    2. 如何确定待排序列中关键码最小的记录在有序序列中的位置?

选择排序示例

image-20220416134431101

image-20220416134601861

#include "stdio.h"
#include "stdlib.h"

void printArray(int array[], int length);
void selectSort(int array[], int length);
int main(){

    int array[] = {49, 38, 65, 97, 76, 13, 27, 49};
    int length = sizeof(array)/sizeof(array[0]);

    printf("待排序的数组是:");
    printArray(array, length);

    selectSort(array, length);

    printf("排序后的数组是:");
    printArray(array, length);    



    return 0;
}

void printArray(int array[], int length){
    for (int i = 0; i < length; i++)
    {
        if (i == 0)
            printf("%d", array[i]);
        else
            printf(" %d", array[i]);
    }
    printf("\n");
}

void selectSort(int array[], int length){

    for (int i = 0; i < length - 1; i++)
    {
        int min = i;
        for (int j = i + 1; j < length - 1; j++)
        {
            if (array[min] > array[j]){
                min = j;
            }
        }
        if (i != min){
            int temp = array[i];
            array[i] = array[min];
            array[min] = temp;
        }
    }
}

选择排序的性能分析

image-20220416140032117


插入排序

直接插入排序

基本思想:在插入第i(>1)个记录时,前面的i-1个记录已经排好序。

image-20220416140247503

  • 需要解决的关键问题?

    1. 如何构造初始的有序序列?
      将第1个记录看成是初始有序表,然后从第2个记永起依次插人到这个有序表中,直到将笰n个记录插入。

      for(i = 2;i <= n;i++){
          //插入第i个记录,即第i趟直接插入排序
      }
      
    2. 如何查找待插入记录的插入位置?
      在i1个记录的有序区r(ll~rli-1]中插入记录r,首先顺序查找r的正确插入位置,然后将r插入到相
      应位置。

      r[0]=r[i]; j=i-1;
      while(r[0] < r[j]){
          r[j+1] = r[j]
          j--;
      }
      r[j] = r[0]
      

直接插入排序的过程示例

image-20220416141635478

#include "stdio.h"
#include "stdlib.h"

void printArray(int array[], int length);
void insertSort(int array[], int length);
int main(){

    int array[] = {0, 49, 38, 65, 97, 76, 13, 27, 49};
    int length = sizeof(array)/sizeof(array[0]);

    printf("待排序的数组是:");
    printArray(array, length);

    insertSort(array, length);

    printf("排序后的数组是:");
    printArray(array, length);    



    return 0;
}

void printArray(int array[], int length){
    for (int i = 1; i < length; i++)
    {
        if (i == 0)
            printf("%d", array[i]);
        else
            printf(" %d", array[i]);
    }
    printf("\n");
}

void insertSort(int array[], int length){

    for (int i = 2; i < length; i++)
    {
        array[0]  = array[i];
        int j  = i - 1;
        while(array[0] < array[j]){
            array[j+1] =  array[j];
            j--;
        }
        array[j+1] = array[0];
    }
    
}

直接插入排序算法性能分析

image-20220416142754738

image-20220416142813347

如何改进插入排序?

注意到,在插入第i(i>1)个记录时,前面的以个记录已经排好序,则在寻找插八位置时,可以用二分(折半)查找来代替顺序查找,从而减少比较次数。

#include "stdio.h"
#include "stdlib.h"

void printArray(int array[], int length);
void insertSort2(int array[], int length);
int binarySearch(int array[], int target, int low, int high);

int main(){

    int array[] = {0, 1, 2, 1, 2};
    int length = sizeof(array)/sizeof(array[0]);

    printf("待排序的数组是:");
    printArray(array, length);

    insertSort2(array, length);

    printf("排序后的数组是:");
    printArray(array, length);    



    return 0;
}

void printArray(int array[], int length){
    for (int i = 1; i < length; i++)
    {
        if (i == 0)
            printf("%d", array[i]);
        else
            printf(" %d", array[i]);
    }
    printf("\n");
}


void insertSort2(int array[], int length){

    for (int i = 2; i < length; i++)
    {
        array[0]  = array[i];
        int target = binarySearch(array, array[i], 1, i - 1);
        int j;
        for(j = i - 1;j > target;j--)
            array[j+1] = array[j];
        array[j+1] = array[0];
    }
}

int binarySearch(int array[], int target, int low, int high){

    int mid = low + high >> 1;

    if (low > high){
        return mid;
    }

    if (target <  array[mid]){
         high = mid - 1;
    }else{
        low = mid + 1;
    }

    return binarySearch(array, target, low, high);
}
0

评论区