南宁师范师大学818计算机基础2017-2019答案.docx

2017AB卷答案 2018AB卷答案 2019AB卷答案 配知识点总结： 4.快速排序基本思想：快速排序是由冒泡排序改进而得的，他的基本思想是在待排序的n个元素中任取一个元素（通常取第一个元素）作为基准，把该元素放入适当的位置后，数据序列被此元素划分成两部分。所有关键字比该元素小的元素放置在前一部分，所有比它大的元素放置在后一部分，并把该元素排在这两部分中间（称为元素归位），这个过程称为一趟快速排序，即一趟划分。之后对产生的两个部分分别重复上述过程，直至每部分内只有一个元素或者空为止。 快速排序最坏时间复杂度为O(n²)，最好时间复杂度为O(nlog2n)，平均时间复杂度为O(nlog2n)，空间复杂度为O(log2n),排序算法不稳定 5.简单选择排序思想：设排序元素放在数组R[0....n-1]中，排序过程中，R被划分成两个子区间，有序区R[0...i-1]和无序区R[i...n-1]。初始时，有序区没有元素。简单选择排序的一趟操作是从当前无序区中选择关键字最小的元素R[k],将它与无序区第一个元素R[i]交换，使R[0...i]变成新的有序区，以此类推排好所有元素 。。。等