在数据结构的简单选择排序里面，为什么会出现情况，该如何解决
不知道为什么，在数据结构的简单选择排序里面，在头歌平台自测运行没有问题，但是一点评测就会出现这样的错误，希望得到各位的帮忙指点
我记得这个重新排列就可以，除非在简单选择的时候，不对
- 你可以参考下这个问题的回答, 看看是否对你有帮助, 链接: https://ask.csdn.net/questions/24353
- 你也可以参考下这篇文章：验证歌德巴赫猜想：任何一个不小于6的偶数可以表示为两个素数之和（C语言）
- 除此之外, 这篇博客: C语言程序设计·头歌实训合集中的 第8关：计算两个正整数的最大公约数 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:
任务描述
编程计算两个正整数的最大公约数。其中求最大公约数的函数原型已经给出，请在主函数中编程调用函数，输出最大公约数。
程序的运行示例：
12,3↙
3
####函数原型说明
求最大公约数的函数原型如下：
int MaxCommonFactor( int a, int b);
返回值：返回的是最大公约数；若输入的数据有任意一个不满足条件，返回值是-1。
参数：a，b是两个整型数
相关知识
本任务主要考察函数的调用方法。
####编程要求
根据提示，在右侧编辑器Begin-End处补充代码，编程计算两个正整数的最大公约数。
输入：输入格式:“%d,%d”
输出：输出格式：“%d\n”
测试说明
平台会对你编写的代码进行测试，若是与预期输出相同，则算通关。
样例输入：
467,465
样例输出：
1
开始你的任务吧，祝你成功！#include<stdio.h> int MaxCommonFactor( int a, int b) { int c; if(a<=0||b<=0) return -1; while(b!=0) { c=a%b; a=b; b=c; } return a; } int main(void) { /*********Begin*********/ int a,b; scanf("%d,%d",&a,&b); printf("%d",MaxCommonFactor(a,b)); /*********End**********/ return 0; }- 您还可以看一下 朱有鹏老师的蜂鸣器-第1季第11部分课程中的 1.11.5.让蜂鸣器唱歌1小节, 巩固相关知识点
- 以下回答由chatgpt基于相关博客总结生成:
问题标题: 简单选择排序中的错误，如何解决？
问题内容: 我在数据结构的课程中学习了简单选择排序算法，并在某个在线编程平台上进行了自测，结果没有出现问题。但是，当我提交到另一个在线评测平台时，却遇到了错误。我很困惑，希望能得到你们的帮助和指导。请问是什么原因导致了这种情况，应该如何解决？
回答如下: 问题出现的原因可能是与算法实现或数据类型有关。我来帮你分析一下可能的解决方案和错误原因。
首先，简单选择排序算法的思路是，对于未排序部分的数组，在每一轮中选择最小的元素，并将它与未排序部分的第一个元素交换位置。
根据参考资料段落3的描述，简单选择排序的具体实现可能有一些问题。在排序过程中，根据描述，每次都是冒泡移动最小的元素，在每次找到最小元素时，都会进行一次交换操作。
可能的问题是，交换操作可能会导致额外的时间和空间开销。特别是使用链表而不是数组来实现排序，可能会导致指针操作的复杂性和效率低下。
解决方案可以是使用数组而不是链表来实现简单选择排序。另外，可以通过维护一个索引最小值而不是进行交换操作来优化算法。
以下是一个可能的解决方案，展示如何使用数组实现简单选择排序算法：
def selection_sort(arr): n = len(arr) for i in range(n-1): min_idx = i for j in range(i+1, n): if arr[j] < arr[min_idx]: min_idx = j if min_idx != i: arr[i], arr[min_idx] = arr[min_idx], arr[i] return arr # 测试代码 arr = [64, 25, 12, 22, 11] sorted_arr = selection_sort(arr) print(sorted_arr)通过使用数组替代链表，并优化交换操作，可以提高算法的效率和准确性。
希望我的回答能够对你有所帮助。如果还有其他问题，请随时提问。
直接插入排序
直接插入排序（Straight Insertion Sorting）的基本思想：在要排序的一组数中，假设前面(n-1) [n>=2] 个数已经是排好顺序的，现在要把第n个数插到前面的有序数中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。
直接插入排序是一种稳定的排序方法,最好的时间复杂是O(n)也就是已经排好的序列,最差的时间复杂度是O(n^2)逆序
//插入排序是一种稳定的排序方法,最好的时间复杂是O(n)也就是已经排好的序列,最差的时间复杂度是O(n^2)逆序
public void insertSort(int nums[]){
int tmp;
for(int i=1;i<nums.length;i++){
int j=i;
while (j>0 && nums[j]<nums[j-1]){
tmp=nums[j];
nums[j]=nums[j-1];
nums[j-1]=tmp;
j--;
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
希尔排序
希尔排序(Shell’s Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
算法思想
对于直接插入排序问题，数据量巨大时。将数的个数设为n，取奇数k=n/2，将下标差值为k的数分为一组，构成有序序列。再取k=k/2 ，将下标差值为k的书分为一组，构成有序序列。重复第二步，直到k=1执行简单插入排序。
希尔排序是一种非常不稳定的排序方法，它的时间复杂度为O(n^（1.3—2）)
//希尔排序是一个不稳定的排序算法,它的时间复杂度为O(n^（1.3—2）)
public void shellSortHelper(int nums[],int incr){
int tmp;
for(int i=incr;i<nums.length;i+=incr){
int j=i;
while (j>0 && nums[j]<nums[j-incr]){
tmp=nums[j];
nums[j]=nums[j-incr];
nums[j-incr]=tmp;
j-=incr;
}
}
}
//希尔排序
public void shellSort(int nums[]){
for(int i=nums.length/2;i > 0;i/=2){
shellSortHelper(nums,i);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
选择排序
常用于取序列中最大最小的几个数时。
(如果每次比较都交换，那么就是交换排序；如果每次比较完一个循环再交换，就是简单选择排序。)
遍历整个序列，将最小的数放在最前面。
遍历剩下的序列，将最小的数放在最前面。
重复第二步，直到只剩下一个数。
选择排序的时间复杂度为O(n^2) 选择排序不是一个稳定的排序
//交换排序是一种稳定的排序方法，最好最坏的时间复杂度都是O(n^2)
public void swapSort(int nums[])
{
int tmp;
for(int i=0;i<nums.length;i++){
for(int j=i+1;j<nums.length;j++){
if(nums[i]>nums[j]){
tmp=nums[j];
nums[j]=nums[i];
nums[i]=tmp;
}
}
}
}
//选择排序是一种不稳定的排序方法，最好最坏的时间复杂度都是O(n^2)
public void selectSort(int nums[]){
for(int i=0;i<nums.length;i++){
int values=nums[i];
int position=i;
for(int j=i+1;j<nums.length;j++){
if(nums[j]<values){
values=nums[j];
position=j;
}
}
//swap
nums[position]=nums[i];
nums[i]=values;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
冒泡排序
很简单，用到的很少，据了解，面试的时候问的比较多！将序列中所有元素两两比较，将最大的放在最后面。将剩余序列中所有元素两两比较，将最大的放在最后面。重复第二步，直到只剩下一个数。
冒泡排序的时间复杂度为O(n^2) 冒泡排序是一个稳定的排序
//冒泡排序 一种稳定的排序算法，最好最坏的时间复杂度都是O(n^2)
public void bubbleSort(int nums[]){
int tmp;
for(int i=0;i<nums.length;i++){
for (int j=0;j<nums.length-i-1;j++){
if(nums[j]>nums[j+1]){
tmp=nums[j+1];
nums[j+1]=nums[j];
nums[j]=tmp;
}
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
快速排序
要求时间最快时。
选择第一个数为p，小于p的数放在左边，大于p的数放在右边。
递归的将p左边和右边的数都按照第一步进行，直到不能递归。
快速排序是由一种不稳定的排序算法，最好的时间复杂度是O(nLogN)，最差时间复杂度是O(n^2)
//快速排序是由一种不稳定的排序算法，最好的时间复杂度是O(nLogN)，最差时间复杂度是O(n^2)
private void quickSortHelper(int nums[],int start,int end){
if(start>end) return;
int high=end;
int low=start;
int target=nums[start];
while (low<high){
while (low<high && nums[high]>=target){
high--;
}
nums[low]=nums[high];
while (low<high && nums[low]<=target){
low++;
}
nums[high]=nums[low];
}
nums[low]=target;
quickSortHelper(nums,start,low-1);
quickSortHelper(nums,low+1,end);
}
public void quickSort(int nums[])
{
quickSortHelper(nums,0,nums.length-1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
归并排序
速度仅次于快速排序，内存少的时候使用，可以进行并行计算的时候使用。
选择相邻两个数组成一个有序序列。
选择相邻的两个有序序列组成一个有序序列。重复第二步，直到全部组成一个有序序列。
归并排序,是一种稳定的排序是算法这个算法的时间复复杂度都是O(NlogN)
//归并排序,是一种稳定的排序是算法这个算法的时间复复杂度都是O(NlogN)
public void mergeSrot(int nums[],int start,int end){
if(start>=end) return;
int mid=(start+end)/2;
mergeSrot(nums,start,mid);
mergeSrot(nums,mid+1,end);
mergeSrotHelper(nums,start,mid,end);
}
// 将两个有序序列归并为一个有序序列(二路归并)
private void mergeSrotHelper(int[] nums, int start, int mid, int end) {
int[] arr=new int[end+1];
int low=start;
int left=start;
int center=mid+1;
while (left<=mid && center<=end){
arr[low++] = nums[left] <= nums[center] ? nums[left++] : nums[center++];
}
while (left<=mid){
arr[low++]=nums[left++];
}
while (center<=end){
arr[low++]=nums[center++];
}
for(int i=start;i<=end;i++){
nums[i]=arr[i];
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
堆排序
对简单选择排序的优化。
将序列构建成大顶堆。
将根节点与最后一个节点交换，然后断开最后一个节点。
重复第一、二步，直到所有节点断开。
//堆排序
private boolean isLeaf(int nums[],int pos)
{
//没有叶子节点
return pos*2+1>=nums.length;
}
private void swap(int[] nums,int pos1,int pos2)
{
int tmp;
tmp=nums[pos2];
nums[pos2]=nums[pos1];
nums[pos1]=tmp;
}
private void shiftdown(int[] nums,int pos)
{
while(!isLeaf(nums,pos))
{
int left=pos*2+1;
int right=pos*2+2;
if(right<nums.length)
{
left=nums[left]>nums[right]?left:right;
}
//是否需要调整堆
if(nums[pos]>=nums[left]) return;
swap(nums,pos,left);
pos=left;
}
}
public void buildHeap(int nums[])
{
for(int i=nums.length/2-1;i>=0;i--)
{
shiftdown(nums,i);
}
}
public void heapSort(int nums[])
{
for(int i=nums.length-1;i>=0;i--)
{
swap(nums,0,i);
shiftdown(nums,i);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
总结
一、稳定性:
稳定：冒泡排序、插入排序、归并排序和基数排序
不稳定：选择排序、快速排序、希尔排序、堆排序
二、平均时间复杂度
O(n^2):直接插入排序，简单选择排序，冒泡排序。
在数据规模较小时（9W内），直接插入排序，简单选择排序差不多。当数据较大时，冒泡排序算法的时间代价最高。性能为O(n^2)的算法基本上是相邻元素进行比较，基本上都是稳定的。
O(nlogn):快速排序，归并排序，希尔排序，堆排序。
其中，快排是最好的，其次是归并和希尔，堆排序在数据量很大时效果明显。
三、排序算法的选择
数据规模较小
（1）待排序列基本序的情况下，可以选择直接插入排序；
（2）对稳定性不作要求宜用简单选择排序，对稳定性有要求宜用插入或冒泡
数据规模不是很大
（1）完全可以用内存空间，序列杂乱无序，对稳定性没有要求，快速排序，此时要付出log（N）的额外空间。
（2）序列本身可能有序，对稳定性有要求，空间允许下，宜用归并排序
数据规模很大
（1）对稳定性有求，则可考虑归并排序。
（2）对稳定性没要求，宜用堆排序