中国大学算法与数据结构_10答案(慕课2023课后作业答案)

点击查看答案

学习通算法与数据结构_10

算法与数据结构是计算机科学的核心，也是程序员必须掌握的基本理论。学习通算法与数据结构_10主要介绍了排序算法和查找算法。

排序算法

在计算机科学中，排序算法是将一串数据按照特定的顺序进行排列的算法，本节将介绍常见的几种排序算法。

冒泡排序

冒泡排序是一种简单的排序算法，它重复地遍历要排序的序列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。

void bubbleSort(int arr[], int n)        {             int i, j;            for (i = 0; i < n-1; i++)                // Last i elements are already sorted            for (j = 0; j < n-i-1; j++)                if (arr[j] >arr[j+1])                    swap(&arr[j], &arr[j+1]);        }    

选择排序

选择排序是一种简单的排序算法，它的工作原理是每次从待排序的数据元素中选出最小（或最大）的一个元素，存放到序列的起始位置，直到全部待排序的数据元素排完。

void selectionSort(int arr[], int n)        {             int i, j, min_idx;            // One by one move boundary of unsorted subarray            for (i = 0; i < n-1; i++)            {                 // Find the minimum element in unsorted array                min_idx = i;                for (j = i+1; j < n; j++)                if (arr[j] < arr[min_idx])                    min_idx = j;                // Swap the found minimum element with the first element                swap(&arr[min_idx], &arr[i]);            }        }    

快速排序

快速排序是一种常用的排序算法，采用分治法来处理数据。它的基本思想是先从数列中取出一个数作为基准数，然后将比这个数小的数放到左边，比这个数大的数放到右边。

int partition (int arr[], int low, int high)        {             int pivot = arr[high];    // pivot            int i = (low - 1);  // Index of smaller element            for (int j = low; j <= high- 1; j++)            {                 // If current element is smaller than or                // equal to pivot                if (arr[j] <= pivot)                {                     i++;    // increment index of smaller element                    swap(&arr[i], &arr[j]);                }            }            swap(&arr[i + 1], &arr[high]);            return (i + 1);        }        void quickSort(int arr[], int low, int high)        {             if (low < high)            {                 /* pi is partitioning index, arr[p] is now                   at right place */                int pi = partition(arr, low, high);                // Separately sort elements before                // partition and after partition                quickSort(arr, low, pi - 1);                quickSort(arr, pi + 1, high);            }        }    

查找算法

查找算法是一种在数据集合中寻找某一特定数据的算法。常见的查找算法有线性查找和二分查找。

线性查找

线性查找，也叫顺序查找，是一种最简单的查找算法。它的基本思想是从数据集合的一端开始，逐个比较数据元素，直到找到所要查找的数据为止。

int linearSearch(int arr[], int n, int x)        {             int i;            for (i = 0; i < n; i++)                if (arr[i] == x)                    return i;            return -1;        }    

二分查找

二分查找，也叫折半查找，是一种在有序数组中查找某一特定元素的查找算法。它的基本思想是将数组分为两个部分，如果中间元素比目标元素小，则在右侧部分查找，如果中间元素比目标元素大，则在左侧部分查找。

int binarySearch(int arr[], int l, int r, int x)        {             if (r >= l) {                 int mid = l + (r - l) / 2;                // If the element is present at the middle                // itself                if (arr[mid] == x)                    return mid;                // If element is smaller than mid, then                // it can only be present in left subarray                if (arr[mid] >x)                    return binarySearch(arr, l, mid - 1, x);                // Else the element is in right subarray                return binarySearch(arr, mid + 1, r, x);            }            // We reach here when element is not present            // in array            return -1;        }    

总结

本节主要介绍了排序算法和查找算法。排序算法包括冒泡排序、选择排序和快速排序等。查找算法包括线性查找和二分查找等。程序员需要根据具体情况选择合适的算法，以提高程序的效率。