C语言快排函数qsort()

#C语言快排函数qsort()| 来源: 网络整理| 查看: 265

原本以为C语言中的快排函数都要靠自己去实现，今天才知道，原来qsort就是C语言中的快排函数，包含在stdlib.h头文件中，函数一共有四个参数，没有返回值。

//int (*cmp)(const void *,const void *); qsort(*s, n, sizeof(s[0]), cmp); 其中第一个参数s是一个地址，即参与排序的首地址； n是需要排序的数量； sizeof(s[0])则是每一个元素占用的空间大小；指向函数的指针，用于确定排序的顺序。简单的说：对一个长为1000的数组进行排序时，int a[1000]; qsort(a, 1000, sizeof(int), cmp); //其中cmp函数应写为： int cmp(const void *a, const void *b) { return *(int*)a - *(int*)b; //由小到大排序 //return *(int *)b - *(int *)a; 由大到小排序 } cmp函数的返回值，0(进行置换)，0(不进行置换)。

首先，我们先来手动实现一下快排。

#include int a[100], n, temp; void QuickSort(int h, int t) { if(h >= t) return; int mid = (h + t) / 2, i = h, j = t, x; x = a[mid]; while(1) { while(a[i] < x) i++; while(a[j] > x) j--; if(i >= j) break; temp = a[i]; a[i] = a[j]; a[j] = temp; } a[j] = x; QuickSort(h, j - 1); QuickSort(j + 1, t); return ; } int main() { int i; scanf("%d", &n); for(i = 0; i < n; i++) scanf("%d", &a[i]); QuickSort(0, n - 1); for(i = 0; i < n; i++) printf("%d ", a[i]); return 0; }

接着，是对int型数组进行快排。

#include #include #include int s[10000], n, i; int cmp(const void *a, const void *b) { return (*(int *)a - *(int *)b); } int main() { scanf("%d", &n); for(i = 0; i < n; i++) scanf("%d", &s[i]); qsort(s, n, sizeof(s[0]), cmp); for(i = 0; i < n; i++) printf("%d ", s[i]); return 0; }

double型。

#include #include double s[1000]; int i, n; int cmp(const void * a, const void * b) { return((*(double*)a - *(double*)b>0)?1:-1); } int main() { scanf("%d", &n); for(i = 0; i < n; i++) scanf("%lf", &s[i]); qsort(s, n, sizeof(s[0]), cmp); for(i = 0; i < n; i++) printf("%lf ", s[i]); return 0; }

char型。

#include #include #include char s[10000], i, n; int cmp(const void *a,const void *b) { return (*(char *)a - *(char *)b); } int main() { scanf("%s", s); n = strlen(s); qsort(s, n, sizeof(s[0]), cmp); printf("%s", s); return(0); }

struct型。

#include #include struct node { double date1; int no; } s[100]; int i, n; int cmp(const void *a,const void *b) { struct node *aa = (struct node *)a; struct node *bb = (struct node *)b; return (((aa->date1) > (bb->date1)) ? 1 : -1); } int main() { scanf("%d", &n); for(i = 0; i < n; i++) { s[i].no = i + 1; scanf("%lf", &s[i].date1); } qsort(s, n, sizeof(s[0]), cmp); for(i = 0; i < n; i++) printf("%d %lf\n", s[i].no, s[i].date1); return(0); }

对结构体排序，加入no来使其稳定(即data值相等的情况下按原来的顺序排)。

#include #include struct node { double date1; int no; } s[100]; int i, n; int cmp(const void *a, const void *b) { struct node *aa = (struct node *)a; struct node *bb = (struct node *)b; if(aa->date1 != bb->date1) return(((aa->date1) > (bb->date1)) ? 1 : -1); else return((aa->no) - (bb->no)); } int main() { scanf("%d", &n); for(i = 0; i < n; i++) { s[i].no = i + 1; scanf("%lf", &s[i].date1); } qsort(s, n, sizeof(s[0]), cmp); for(i = 0; i < n; i++) printf("%d %lf\n", s[i].no, s[i].date1); return 0; }

对字符串数组的排序(char s[][]型)。

#include #include #include char s[100][100]; int i, n; int cmp(const void *a, const void *b) { return (strcmp((char*)a, (char*)b)); } int main() { scanf("%d", &n); for(i = 0; i < n; i++) scanf("%s", s[i]); qsort(s, n, sizeof(s[0]), cmp); for(i = 0; i < n; i++) printf("%s\n", s[i]); return 0; }

对字符串数组排序(char *s[]型)。

#include #include #include char *s[100]; int i, n; int cmp(const void *a, const void *b) { return (strcmp(*(char**)a, *(char**)b)); } int main() { scanf("%d", &n); for(i = 0; i < n; i++) { s[i] = (char*)malloc(sizeof(char*)); scanf("%s", s[i]); } qsort(s, n, sizeof(s[0]), cmp); for(i = 0; i < n; i++) printf("%s\n", s[i]); return 0; }

大致就这样吧，收集了不少资料，看了不少博客才总结在一起了。

【本文地址】

公司简介

联系我们