C语言中用于排序数组的内置函数

Question

C编程语言中是否有用于排序数组的内置函数？还是我需要编写自己的函数？

- CluelessNoob

---

stdlib.h中的qsort函数 - nhahtdh

@nhahtdh 不要把它发布为答案？ - triclosan

@triclosan：写一行注释比写一个完整的答案需要更少的努力。 - nhahtdh

虽然不相关，但bsearch(3)是与qsort(3)类似的libc例程，许多人并不知道它的存在。（通常情况下，它们一起使用：在二分查找之前需要对数组进行排序。=）） - Conrad Meyer

Answer 1

查看qsort

语法:

#include <stdlib.h>
void qsort( void *buf, size_t num, size_t size, int (*compare)(const void *, const void *) );

描述:

qsort()函数使用快速排序算法对buf（包含num个大小为size的项）进行排序。比较函数用于比较buf中的项。如果第一个参数小于第二个参数，则比较应返回负数；如果它们相等，则应返回零；如果第一个参数大于第二个参数，则应返回正数。qsort()按升序对buf进行排序。

- Daniel Leschkowski

---

注意：qsort() 并不一定是快速排序（虽然通常情况下它确实是快速排序）。 - wildplasser

Answer 2

您可以在stdlib.h中使用qsort函数。它是快速排序算法，平均时间复杂度为O(nlogn)，最坏情况复杂度为O(n²)。C99标准甚至较新的C11标准都没有强制要求该函数的实现或时间复杂度。然而，通常实现可能使用能够产生平均情况下O(nlogn)时间复杂度的算法(这是比较排序最佳的时间复杂度)。

您可以使用此函数来对任何类型的数组（甚至包括struct）进行排序——但是，您必须提供一个比较函数来比较数组中的两个元素。

- nhahtdh

---

注意：qsort()不一定是快速排序。（尽管通常是这样） - wildplasser

现在你可以链接到C11标准 :) - pmg

Answer 3

qsort 是众所周知的。还有像heapsort、mergesort等排序算法。请查看链接以获取更多细节。

请注意，它们都将比较函数作为输入，使它们易于与本地和用户创建的数据类型一起使用。

- Jay

---

我很好奇标准库中是否存在mergesort和heapsort...结果发现它们在FreeBSD的libc中。太棒了。+1（注意：它们似乎不存在于glibc中。） - Conrad Meyer

它们是非标准的 C 函数。 - nhahtdh

Answer 4

是的： qsort。它在stdlib.h中。

- ruakh

Answer 5

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

  // This function is used in qsort to decide the relative order 
  // of elements at addresses p and q. 
  int comparator(const void *p, const void *q) 
   { 
      return (*(int*)p-*(int*)q);
      } 

  // A utility function to print an array 
  void printArr(int arr[], int n) 
  { 
     int i; 
     for (i = 0; i < n; ++i) 
     printf("%d ", arr[i]); 
  }  

  // Driver program to test above function 
  int main() 
  { 
     int arr[] = {1, 6, 5, 2, 3, 9, 4, 7, 8, 0}; 
     int size = sizeof(arr) / sizeof(arr[0]); 
     qsort((void*)arr, size, sizeof(arr[0]), comparator); 
     printf("Output array is\n"); 
     printArr(arr, size);  
     return 0; 
   } 

- Ayush Kapri

Answer 6

简单语法：

int function (const void * a, const void * b) {return ( *(int*)a-(int*)b);}
`qsort(arr_name , sizeofarray , sizeof(int), function);

- Lalit Verma