当前位置：首页 > news >正文

快速排序--自行实现+qsort+sort

news 来源：原创 2024/5/14 8:45:24

快排呢，就是每次以第一个数为基准，把后面所有数归位，归位即将比它小的放在它的左边，比它大的放在它的右边。

通过递归，再将它左边的数列进行如此排序，右边也如此，之后的之后的子数列也不断如此。

#include <iostream>
#include <cstdio>
using namespace std;
void qsort(int jk[], int left, int right){
	if(left >= right) return;
	int i = left, j = right, temp = jk[left];
	while(i < j){
		while(i < j && jk[j] >= temp) --j;
		jk[i] = jk[j];
		while(i < j && jk[i] <= temp) ++i;
		jk[j] = jk[i];
	}
	jk[i] = temp;
	qsort(jk, left, i-1);
	qsort(jk, i+1, right);
}
int main(){
	int jk[15] = {0, 5, 8, 1, 7, 9, 6, 0, 3, 4, 2};
	qsort(jk, 1, 10);
	for(int i = 1; i <= 10; ++i)
		printf("%d ", jk[i]);
	return 0;
}

下面介绍内置函数qsort

原型: void qsort(void *base, int nelem, int width, int (*fcmp)(const void *,const void *));

参数：
1 待排序数组首地址
2 数组中待排序元素数量
3 各元素的占用空间大小
4 指向函数的指针，用于确定排序的顺序

说明：qsort函数是ANSI C标准中提供的，其声明在C的stdlib.h文件和C++的algorithm中，是根据二分法写的，其时间复杂度为n*log(n)。

其实，algorithm中还有一个sort函数，sort函数是c++中标准模板库的的函数，在qsort()上已经进行了优化，根据情况的不同可以采用不同的算法，所以较快。在同样的元素较多和同样的比较条件下，sort()的执行速度都比qsort()要快。另外，sort()是类属函数，可以用于比较任何容器，任何元素，任何条件。使用时需调用<algorithm>
sort(begin(),end(),cmp)

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int cmp(const void *a, const void *b){
	return *(int *)a - *(int *)b;
}
bool cp(long long a, long long b){	// int int
	return a > b;
}
int main(){
	int jk[15] = {0, 5, 8, 1, 7, 9, 6, 0, 3, 4, 2};
	qsort(jk+1, 10, sizeof jk[1], cmp);		//待排数组的起始地址,待排的个数,待排数组的元素占字,比较函数
	for(int i = 1; i <= 10; ++i)
		printf("%d ", jk[i]);
	cout << endl;
	int hk[15] = {11, 5, 8, 1, 7, 9, 6, 0, 3, 4, 2};
	sort(hk+1, hk+11, cp);		//待排数组的起始地址,待排数组区间尾地址的下一地址,比较函数(不写为升序)
	for(int i = 1; i <= 10; ++i)
		printf("%d ", hk[i]);
	return 0;
}