排序算法，插入排序 12和0没有调换过来的原因是什么#include <stdio.h>

插入排序，12和0没有调换过来的原因是什么

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

typedef int ElemType;
typedef struct STLNode{
    ElemType *data;
    int len;
}STLNode;
//初始化
void Init_Table(STLNode &ST,int len){
    ST.len = len;
    ST.data = (ElemType*)malloc(sizeof(ElemType)*ST.len); 
} 
//打印
void print_Table(STLNode ST){
    int i;
    for(i=0;i<ST.len;i++){
        printf("%3d",ST.data[i]);
    }
    printf("\n");
}

//交换(冒泡)
void swap(int &a,int &b){
    int temp;
    temp = a;
    a = b;
    b = temp;
} 
//冒泡排序
int ButtleSort(ElemType *A,int n){
    int i,j;
    for(i=0;i<n;i++){//i越大，说明排好的元素越多 
        for(j=n-1;j>i;j--){//j表示还要排的元素 
            if(A[j-1] > A[j]){//
                swap(A[j-1],A[j]); 
            } 
        }
    }
}
//快速排序核心代码（挖坑）
int Partition(ElemType *A,int low,int high){
    //1.储存第一个值
    ElemType poivt = A[low];
    //2.进入循环
    while(low<high){
        //3.循环high
        while(low<high && poivt<=A[high]){
            high--;
        }
        A[low] = A[high];
        //4.循环low
        while(low<high && poivt>=A[low]){
            low ++;
        }
        A[high] = A[low]; 
    }
    //5.将保存的元素赋给中间
    A[low] = poivt;
    return low; 
} 
//快速排序
int QuiteSort(ElemType *A,int low,int high){
    //递归结束的条件
    if(low<high){
        int povit_pos = Partition(A,low,high);
        QuiteSort(A,low,povit_pos-1);
        QuiteSort(A,povit_pos+1,high); 
    } 
}
//插入排序
void InsertSort(ElemType *A,int len){
    int i,j,insertVal;
    for(i=1;i<len;i++){
        insertVal = A[i];
        for(j=i-1;j>0 && A[j] > insertVal;j--){
            A[j+1] = A[j];
        }
        A[j+1] = insertVal;
    }
}

int main(){
    //12 63 58 95 41 35 65 0 38 44
    STLNode ST;
    //初始化
    Init_Table(ST,10);
    //读取
    ElemType str[10];
    ElemType B[10];
    int i;
    for(i=0;i<10;i++){
        scanf("%d",&str[i]);
    }
    memcpy(ST.data,str,sizeof(str));
    //冒泡排序
    ButtleSort(ST.data,10);
    print_Table(ST);
    //快速排序
    memcpy(ST.data,str,sizeof(str));//将str在重新赋给ST，使St混乱 
    QuiteSort(ST.data,0,9); 
    print_Table(ST); 
    //插入排序
    memcpy(ST.data,str,sizeof(str)); 
    InsertSort(ST.data,10);
    print_Table(ST);  
} 

void InsertSort(ElemType *A, int len) {
    int i, j, insertVal;
    for (i = 1; i < len; i++) {
        insertVal = A[i];
        for (j = i - 1; j >= 0 && A[j] > insertVal; j--) {
            A[j + 1] = A[j];
        }
        A[j + 1] = insertVal;
    }
}

修改如下，改动处见注释，供参考：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

typedef int ElemType;
typedef struct STLNode{
    ElemType *data;
    int len;
}STLNode;
//初始化
void Init_Table(STLNode &ST,int len){
    ST.len = len;
    ST.data = (ElemType*)malloc(sizeof(ElemType)*ST.len);
}
//打印
void print_Table(STLNode ST){
    int i;
    for(i=0;i<ST.len;i++){
        printf("%3d",ST.data[i]);
    }
    printf("\n");
}
 
//交换(冒泡)
void swap(int &a,int &b){
    int temp;
    temp = a;
    a = b;
    b = temp;
} 
//冒泡排序
int ButtleSort(ElemType *A,int n){
    int i,j;
    for(i=0;i<n;i++){//i越大，说明排好的元素越多 
        for(j=n-1;j>i;j--){//j表示还要排的元素 
            if(A[j-1] > A[j]){//
                swap(A[j-1],A[j]); 
            } 
        }
    }
}
//快速排序核心代码（挖坑）
int Partition(ElemType *A,int low,int high){
    //1.储存第一个值
    ElemType poivt = A[low];
    //2.进入循环
    while(low<high){
        //3.循环high
        while(low<high && poivt<=A[high]){
            high--;
        }
        A[low] = A[high];
        //4.循环low
        while(low<high && poivt>=A[low]){
            low ++;
        }
        A[high] = A[low]; 
    }
    //5.将保存的元素赋给中间
    A[low] = poivt;
    return low; 
} 
//快速排序
int QuiteSort(ElemType *A,int low,int high){
    //递归结束的条件
    if(low<high){
        int povit_pos = Partition(A,low,high);
        QuiteSort(A,low,povit_pos-1);
        QuiteSort(A,povit_pos+1,high); 
    } 
}
//插入排序
void InsertSort(ElemType *A,int len){
    int i,j,insertVal;
    for(i=1;i<len;i++){
        insertVal = A[i];
        for(j=i; j>0 && A[j-1] > insertVal;j--){ // 修改
        //for(j=i-1;j>0 && A[j] > insertVal;j--)
            A[j] = A[j-1];  // A[j+1] = A[j];  修改
        }
        A[j] = insertVal; // A[j+1] = insertVal; 修改
    }
}
 
int main(){
    //12 63 58 95 41 35 65 0 38 44
    STLNode ST;
    //初始化
    Init_Table(ST,10);
    //读取
    ElemType str[10];
    ElemType B[10];
    int i;
    for(i=0;i<10;i++){
        scanf("%d",&str[i]);
    }
    memcpy(ST.data,str,sizeof(str));
    //冒泡排序
    ButtleSort(ST.data,10);
    print_Table(ST);
    //快速排序
    memcpy(ST.data,str,sizeof(str));//将str在重新赋给ST，使St混乱
    QuiteSort(ST.data,0,9);
    print_Table(ST);
    //插入排序
    memcpy(ST.data,str,sizeof(str));
    InsertSort(ST.data,10);
    print_Table(ST);
}

不知道你这个问题是否已经解决, 如果还没有解决的话:

• 这个问题的回答你可以参考下: https://ask.csdn.net/questions/771830
• 以下回答来自chatgpt:

  经过分析，插入排序中12和0没有调换位置的原因是因为在插入排序算法中，只有当arr[j]大于key时，才会将arr[j]向后移动一位。而在这个代码片段中，当j等于0时，arr[j]为12，大于key的值0，因此不会执行arr[j + 1] = arr[j]的语句，导致12没有被正确插入到0的前面。

  为了解决这个问题，可以在插入排序的while循环中多加一个判断条件，当j等于-1时，也就是已经遍历到数组的头部时，将key插入到数组的开头位置。

  以下是修改后的代码片段：

  #include <stdio.h>
  
  void insertionSort(int arr[], int n){
      int i, key, j;
      for (i = 1; i < n; i++){
          key = arr[i];
          j = i - 1;
          while (j >= 0 && arr[j] > key){
              arr[j + 1] = arr[j];
              j = j - 1;
          }
          arr[j + 1] = key;
      }
  }
  
  int main(){
      int arr[] = {12, 0, 5, 8, 2};
      int n = sizeof(arr) / sizeof(arr[0]);
      insertionSort(arr, n);
      printf("Sorted array: \n");
      for (int i = 0; i < n; i++){
          printf("%d ", arr[i]);
      }
      return 0;
  }
  

  这样修改后的代码能保证在插入排序过程中，所有元素都会被正确地排序。运行结果为：0 2 5 8 12。

  希望这个解决方案能帮助到您！如果有任何问题，请随时向我提问。

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^