Pertanyaan Fungsi perpustakaan C untuk melakukan sortir


Apakah ada fungsi perpustakaan yang tersedia di perpustakaan standar C untuk melakukan sortir?


75
2017-11-24 05:29


asal


Jawaban:


qsort() adalah fungsi yang Anda cari. Anda menyebutnya dengan pointer ke array data Anda, jumlah elemen dalam array itu, ukuran setiap elemen dan fungsi perbandingan.

Itu melakukan sihir dan array Anda diurutkan di tempat. Contoh berikut:

#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;
}

94
2017-11-24 05:42



C / C ++ pustaka standar <stdlib.h> mengandung qsort fungsi.

Ini bukan implementasi cepat terbaik di dunia tetapi cukup cepat dan SANGAT MUDAH digunakan ... sintaks formal qsort adalah:

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

Satu-satunya hal yang perlu Anda terapkan adalah fungsi compare_function, yang mengambil dua argumen tipe "const void", yang dapat dilemparkan ke struktur data yang sesuai, dan kemudian kembalikan salah satu dari tiga nilai ini:

  • negatif, jika seharusnya sebelum b
  • 0, jika sama dengan b
  • positif, jika harus setelah b

1. Membandingkan daftar bilangan bulat:

cukup cor a dan b ke integer jika x < y,x-y negatif, x == y, x-y = 0, x > y, x-y positif x-y adalah cara pintas untuk melakukannya :) membalikkan *x - *y untuk *y - *x untuk menyortir dalam urutan menurun / terbalik

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

2. Membandingkan daftar string:

Untuk membandingkan string, Anda membutuhkannya strcmp berfungsi di dalam <string.h> lib. strcmp secara default akan mengembalikan-ve, 0, ve dengan tepat ... untuk mengurutkan dalam urutan terbalik, hanya membalik tanda yang dikembalikan oleh strcmp

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

3. Membandingkan angka floating point:

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. Membandingkan rekaman berdasarkan kunci:

Terkadang Anda perlu mengurutkan barang yang lebih rumit, seperti catatan. Inilah yang paling sederhana cara menggunakannya qsort Perpustakaan.

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;
}

52
2017-11-24 16:06



Tentunya: qsort() adalah implementasi dari semacam (tidak harus quicksort seperti namanya mungkin menyarankan).

Coba man 3 qsort atau baca di http://linux.die.net/man/3/qsort


6
2017-11-24 05:32



mencoba qsort di stdlib.h.


4
2017-11-24 05:31



Meskipun tidak di perpustakaan standar, https://github.com/swenson/sort hanya memiliki dua file header yang dapat Anda sertakan untuk mendapatkan akses ke berbagai rute penyortiran yang sangat cepat, seperti:

#define SORT_NAME int64
#define SORT_TYPE int64_t
#define SORT_CMP (x, y) ((x) - (y))
#include "sort.h"
/ * Anda sekarang memiliki akses ke int64_quick_sort, int64_tim_sort, dll., Misalnya, * /
int64_quick_sort (arr, 128); / * Asumsikan Anda memiliki beberapa int * arr atau int arr [128]; * /

Ini harus setidaknya dua kali lebih cepat dari pustaka standar qsort, karena tidak menggunakan pointer fungsi, dan memiliki banyak opsi algoritma pengurutan lain untuk dipilih.

Ini di C89, jadi harus bekerja pada dasarnya setiap kompiler C.


3
2018-05-04 05:18



Ada beberapa fungsi penyortiran C yang tersedia di stdlib.h. Anda dapat melakukan man 3 qsort pada mesin unix untuk mendapatkan daftar dari mereka tetapi mereka termasuk:

  • heapsort
  • quicksort
  • mergesort

2
2017-11-24 05:31



Gunakan qsort () di stdlib.

@paxdiablo Fungsi qsort () sesuai dengan ISO / IEC 9899: 1990 (`` ISO C90 '').


2
2017-11-24 06:32