使用指針功能的氣泡排序

Question

我想通過使用指針來實現在c中的氣泡排序但不起作用。誰能幫我？這裏是代碼：

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

void bubbleSort(void** base, size_t length, int (*compar)(const void*, const void*)); 

int main(int argc, char* argv[]) { 
    int cmp(const void*, const void*); 
    int vet[] = {1, 2, 5, 7, 6, 1, 3, 2, 9, 15, 14, 20}; 
    bubbleSort((void**) &vet, sizeof(vet)/sizeof(vet[0]), cmp); 
    int i; 
    for (i = 0; i < sizeof(vet)/sizeof(vet[0]); i++) { 
     printf("%d\n", vet[i]); 
    } 
    return 0; 
} 

int cmp(const void* x, const void* y) { 
    return **((int* const*) x) - **((int* const*) y); 
} 

void bubbleSort(void** base, size_t length, int (*compar)(const void*, const void*)) { 
    int i, j; 
    void swap(void*, void*); 
    for (i = 0; i < length; i++) { 
     for (j = 1; j < length; j++) { 
      if ((*compar)(base[i], base[i]) < 0) { 
       swap(base[i], base [j]); 
      } 
     } 
    } 
} 

void swap(void* a, void* b) { 
    void* tmp = a; 
    a = b; 
    b = tmp; 
} 

輸出是沒有排序相同的向量。 （對不起，我的英文版）

Answer 1

當我在機器上運行上面的代碼時，我得到了一個SIGSEGV。然後我發現代碼中有很多錯誤。

首先，你的swap函數實際上什麼都不做！您將傳遞給該函數的數組元素的兩個指針。你只是交換了這些以前指向的地址。它相當無用。它可以用許多不同的方式書寫。我更喜歡以下內容：

void swap(void* a, void* b) { 
//get the int pointers... 
int* t_a = (int*)a; 
int* t_b = (int*)b; 

//now change the values in them... 
int tmp = *t_a; 
*t_a = *t_b; 
*t_b = tmp; 

}

我鑄造他們先int的原因是，它的意義將值分配到void*。

即將到來的bubbleSort代碼，您認爲base[i]在您的代碼中引用了什麼？它不是數組中ith元素的值。它是一個雙指針，base[i]實際上是指ith指向某個其他數組的指針。

由於這裏只有一個數組，所以base[0]是我們唯一有效的地址。如果你嘗試引用其他指針，那麼它的一個SIGSEGV，這是我在運行代碼之前預期的方式。

你需要做的是，首先得到一個指向數組第一個元素的指針（比如ptr）。現在ptr不過是我們的初始數組。然後使用這個。

void bubbleSort(void** base, size_t length, int (*compar)(const void*, const void*)) { 
    int i, j; 
    int *ptr = &(*base); 
    for (i = 0; i < length; i++) { 
     for (j = 1; j < length; j++) { 
      if ((*compar)(&ptr[i], &ptr[j]) < 0) { 
       swap(&ptr[i], &ptr[j]); 
      } 
     } 
    } 
} 

希望這有助於...

Answer 2

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

int cmp(const void *x, const void *y){ 
    int a = *(const int *)x; 
    int b = *(const int *)y; 
    return a < b ? -1 : (a > b); 
} 

void swap(void *a, void *b, size_t type_size) { 
    void *tmp = malloc(type_size); 
    memcpy(tmp, a, type_size); 
    memcpy(a, b, type_size); 
    memcpy(b, tmp, type_size); 
    free(tmp); 
} 

void bubbleSort(void *base, size_t length, size_t type_size, int (*compar)(const void*, const void*)) { 
    int i, j; 
    for (i = 0; i < length - 1; ++i) { 
     for (j = i+1; j < length; ++j){ 
      char *data_i = (char*)base + type_size * i; 
      char *data_j = (char*)base + type_size * j; 
      if(compar(data_i, data_j) > 0) 
       swap(data_i, data_j, type_size); 
     } 
    } 
} 

int main() { 
    int vet[] = {1, 2, 5, 7, 6, 1, 3, 2, 9, 15, 14, 20}; 
    bubbleSort(vet, sizeof(vet)/sizeof(*vet), sizeof(*vet), cmp); 
    int i; 
    for (i = 0; i < sizeof(vet)/sizeof(*vet); i++) { 
     printf("%d\n", vet[i]); 
    } 
    return 0; 
}