Funkcja biblioteki C do sortowania

Czy w standardowej bibliotece C jest dostępna jakaś funkcja do sortowania?

qsort()to funkcja, której szukasz. Wołasz to za pomocą wskaźnika do swojej tablicy danych, liczby elementów w tej tablicy, rozmiaru każdego elementu i funkcji porównania.

Robi swoje, a twoja tablica jest sortowana w miejscu. Oto przykład:

#include <stdio.h>
#include <stdlib.h>
int comp (const void * elem1, const void * elem2) 
{
    int f = *((int*)elem1);
    int s = *((int*)elem2);
    if (f > s) return  1;
    if (f < s) return -1;
    return 0;
}
int main(int argc, char* argv[]) 
{
    int x[] = {4,5,2,3,1,0,9,8,6,7};

    qsort (x, sizeof(x)/sizeof(*x), sizeof(*x), comp);

    for (int i = 0 ; i < 10 ; i++)
        printf ("%d ", x[i]);

    return 0;
}

Biblioteka standardowa C / C ++ <stdlib.h>zawiera qsortfunkcję.

To nie jest najlepsza implementacja szybkiego sortowania na świecie, ale jest wystarczająco szybka i BARDZO ŁATWA w użyciu ... formalna składnia qsort to:

qsort(<arrayname>,<size>,sizeof(<elementsize>),compare_function);

Jedyne, co musisz zaimplementować, to funkcja compare_function, która przyjmuje dwa argumenty typu „const void”, które można rzutować na odpowiednią strukturę danych, a następnie zwrócić jedną z tych trzech wartości:

• ujemna, jeśli a powinno być przed b
• 0, jeśli a równa się b
• pozytywny, jeśli a powinno być po b

1. Porównanie listy liczb całkowitych :

po prostu rzucić A i B do liczb całkowitych razie x < y, x-yjest negatywna, x == y, x-y = 0, x > y, x-yjest dodatnia x-yto sposób skrót zrobić :) to odwrócić *x - *ysię *y - *xna sortowanie malejące / odwrotnej kolejności

int compare_function(const void *a,const void *b) {
int *x = (int *) a;
int *y = (int *) b;
return *x - *y;
}

2. Porównanie listy ciągów :

Aby porównać łańcuch, potrzebujesz strcmpfunkcji w <string.h>bibliotece. strcmpdomyślnie zwróci odpowiednio -ve, 0, ve ... aby posortować w odwrotnej kolejności, po prostu odwróć znak zwracany przez strcmp

#include <string.h>
int compare_function(const void *a,const void *b) {
return (strcmp((char *)a,(char *)b));
}

3. Porównanie liczb zmiennoprzecinkowych :

int compare_function(const void *a,const void *b) {
double *x = (double *) a;
double *y = (double *) b;
// return *x - *y; // this is WRONG...
if (*x < *y) return -1;
else if (*x > *y) return 1; return 0;
}

4. Porównanie rekordów na podstawie klucza :

Czasami musisz posortować bardziej złożone rzeczy, takie jak nagranie. Oto najprostszy sposób na zrobienie tego za pomocą qsortbiblioteki.

typedef struct {
int key;
double value;
} the_record;

int compare_function(const void *a,const void *b) {
the_record *x = (the_record *) a;
the_record *y = (the_record *) b;
return x->key - y->key;
}

Na pewno: qsort()to swego rodzaju implementacja (niekoniecznie quicksort, jak sugeruje nazwa).

Spróbuj man 3 qsort lub przeczytaj go pod adresem http://linux.die.net/man/3/qsort

Chociaż nie jest to dokładnie w standardowej bibliotece, https://github.com/swenson/sort ma tylko dwa pliki nagłówkowe, które możesz dołączyć, aby uzyskać dostęp do szerokiej gamy niesamowicie szybkich tras sortowania, takich jak:

#define SORT_NAME int64 #define SORT_TYPE int64_t #define SORT_CMP ( x , y ) (( x ) - ( y )) #include "sort.h" / * Masz teraz dostęp do int64_quick_sort, int64_tim_sort itp., np. * / 
int64_quick_sort ( arr , 128 ); / * Zakłada, że ​​masz jakieś int * arr lub int arr [128]; * /

   
 
  

Powinna być co najmniej dwa razy szybsza niż standardowa biblioteka qsort, ponieważ nie używa wskaźników funkcji i ma wiele innych opcji algorytmu sortowania do wyboru.

Jest w C89, więc powinien działać w zasadzie w każdym kompilatorze C.

spróbuj qsortw stdlib.h.

Użyj qsort()w <stdlib.h>.

@paxdiablo qsort()Funkcja jest zgodna z normą ISO / IEC 9899: 1990 (`` ISO C90 '').

Istnieje kilka sortowania C Funkcje dostępne w stdlib.h. Możesz zrobić man 3 qsortna komputerze z systemem UNIX, aby uzyskać ich listę, ale obejmują one:

• heapsort
• szybkie sortowanie
• scalesort