写在前面

在 cplusplus.com 里有关于qsort函数的详细解释,
void qsort(void* base, size_t num, size_t size, int (*compar)(const void*, const void*));是它的函数原型. 它的功能: 对指向的数组的元素进行快速排序, 此函数使用的排序算法通过调用指定的函数来比较元素对,
并将指向它们的指针作为参数. 这里就是利用了回调函数, 详见 C 语言指针详解(2)

参数的意义:

  • base: 指向要排序的数组的第一个对象的指针, 类型 void*
  • num: 指向数组中的元素数, 类型无符号整型 size_t
  • size: 数组中每个元素的大小, 单位(字节), 类型无符号整型 size_t
  • compar: 指向比较两个元素的函数的指针, 这个函数遵循原型:int compar (const void* p1, const void* p2);

qsort可以对任意类型的数据进行排序, 它将比较函数抽离出来, 谁调用qsort, 谁就提供compar函数.
一般比较函数如下所示: compar

int compareMyType (const void * a, const void * b)
{
  if ( *(MyType*)a <  *(MyType*)b ) return -1;
  if ( *(MyType*)a == *(MyType*)b ) return 0;
  if ( *(MyType*)a >  *(MyType*)b ) return 1;
}

但是请注意, 不是所有的类型的数据都可以用>``<``=来比较大小.

实现(冒泡排序)

int cmp_int(const void* x, const void* y) {
	return (*(int*)x - *(int*)y);
}
void swap_int(void* x, void* y) {
	int tmp = *(int*)x;
	*(int*)x = *(int*)y;
	*(int*)y = tmp;
}
void swap(void* x, void* y, int size) {
	for (int i = 0; i < size; i++) {
		char tmp = *((char*)x+i);
		*((char*)x + i) = *((char*)y + i);
		*((char*)y + i) = tmp;
	}
}
void my_qsort(void* base, size_t num, size_t size, int (*cmp)(const void* p1, const void* p2)) {
	for (unsigned int i = 0; i < num - 1; i++) {
		// num 个元素最多排 num-1 趟
		int is_order = 1;//
		for (unsigned int j = 0; j < num - 1 - i; j++) {
			// 每排完一趟, 比较的元素就少一个

			////升序
			//if (cmp((char*)base + j*size, (char*)base + (j + 1)*size) > 0){
			//	// 只需要把元素的首地址传给cmp, 通过回调函数自己实现比较
			//	is_order = 0;
			//	//swap_int((char*)base + j * size, (char*)base + (j + 1) * size);
			//  swap((char*)base + j * size, (char*)base + (j + 1) * size, size);
			// 
			//}

			//降序
			if (cmp((char*)base + j * size, (char*)base + (j + 1) * size) < 0) {
				// 只需要把元素的首地址传给cmp, 通过回调函数自己实现比较
				is_order = 0;
				//swap_int((char*)base + j * size, (char*)base + (j + 1) * size);
				swap((char*)base + j * size, (char*)base + (j + 1) * size, size);
			}
		}
		if (is_order == 1) {
			break;
		}
	}
}
int main() {
	int arr[10] = { 5,1,7,3,9,4,8,2,10,6 };
	int size = sizeof arr / sizeof arr[0];
	my_qsort(arr, size, sizeof(arr[0]), cmp_int);
	printf("after my_qsort:\n");
	for (int i = 0; i < size; i++) {
		printf("%d ", arr[i]);
	}
	return 0;
}

写在最后