c - 插入排序错误 C

Question

全部，

我可能在这里遗漏了一些简单的东西，但是我正在查看 C 中的一些简单算法，并且无法使下面代码中的插入排序起作用。冒泡排序似乎有效。

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


void bubbleSort(char *pStringPointers[], int size);
void insertionSort(char *pStringPointers[], int size);
void ArrayTest(char string[][100],int size);

void swap(char **pString1, char**pString2);

int main (int argc, const char *args[]){
    char *pStrings[]={"jeff", "bob","kelli","bill","joe"};
    char testArray[][100]={"jeff", "bob","kelli","bill","joe"};
    ArrayTest(testArray,5);

    insertionSort(pStrings, 5);


    return 0;
}


//Start Algorithms

void ArrayTest(char string[][100], int size){
    printf("\n\nIteration Start:\n");

    for (int i=0;i<size;i++){
        printf(":%s\n",string[i]);   
    }

}


//  Bubble Sort Start

void bubbleSort(char *pStringPointers[], int size){

    char unsorted=1;

    while(unsorted){
        unsorted=0;
        for(int i=1;i<size;i++){
            if(strcmp(pStringPointers[i-1],pStringPointers[i])>0)
            {
                swap(&(pStringPointers[i-1]), &(pStringPointers[i]));
                unsorted=1;
            }
        }
    }

}

//  Bubble Sort End


//  Insertion Sort Start

void insertionSort(char *pS[], int size){
    int i,j;

    for(i=1;i<size;i++){
        printf("\n\nIteration Start:\n");
        for (int i=0;i<size;i++){
            printf(":%s\n",pS[i]);   
        }
        char *temp2=pS[i];
        j=i-1;
        while(j>=0&&strcmp(pS[j],temp2)>0){

            swap(&(pS[i]),&(pS[j]));
            j--;
        }
        pS[j+1]=pS[i];

    }
}



//  Insertion Sort End


//End Algorithms

void swap(char **pString1, char **pString2){
    char *temp=*pString1;
    *pString1=*pString2;
    *pString2=temp;
}

如果您有任何建议，请让我知道。

Answer 1

您不应该比较pS[i]and pS[j]，而是pS[j]and pS[j+1]，因为您在腾出空间时要向上移动旧元素 - 要插入的元素将始终位于第 -j个元素旁边。

而且pS[j+1] = pS[i];不应该在那里 - 你已经完成了交换。

这给了我们这样的东西：

for(i = 1; i < size; i++){
    printf("\n\nIteration Start:\n");
    for (int j = 0; j < size; j++){
        printf(":%s\n", pS[j]);   
    }
    j = i-1;
    while(j >= 0 && strcmp(pS[j], pS[j+1]) > 0){
        swap(&(pS[j+1]), &(pS[j]));
        j--;
    }
}

测试。