美的企业微信网站,免费在线自助建站,长治软件制作平台,微网站分销交换排序——快速排序 7.7 交换排序——快速排序快速排序概念c语言的库函数qsort快速排序框架quickSort 7.7 交换排序——快速排序
快速排序概念
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法#xff08;下文简称快排#xff09;#xff0c;其基本思想为下文简称快排其基本思想为任取待排序元素序列中的某元素作为基准值按照该排序码将待排序集合分割成两子序列左子序列中所有元素均小于基准值右子序列中所有元素均大于基准值然后最左、右子序列分别重复该过程直到所有元素都排列在相应位置上为止。 虽然快排是Hoare发明的但Hoare并没有用自己的名字去给这个算法命名而是用快速来对这个排序命名用于彰显这个排序算法的特点快。 例如我们设基准值为div则排序的目的是为了完成这个目标 这个是二叉树结构的交换排序所以div左边和div右边的区间还要分别重复这个过程。
c语言的库函数qsort
c语言中就有一个库函数qsort
void qsort( void *base, size_t num, size_t width, int (__cdecl *compare )(const void *elem1, const void *elem2 ) );它的4个参数表示的含义
base被用来排序的数组的数组名或数组的首元素地址。num数组的元素个数。width数组的单个元素占用的内存大小。compare程序员自定义的比较函数。
用户自定义的比较函数需要返回两个元素之间的差值。这很大程度上局限了这个函数的玩法比如实现自定义类型数组的排序可能会比较麻烦。但这个函数的底层实现就是快速排序比一般的排序算法的速度要快。
应用实例
#includestdio.h
#includestdlib.h
#includetime.h
#includestdlib.h
#includestdbool.htypedef int Datatype;//用户自定义的比较函数
int cmp(const void* a, const void* b) {//升序排序return (*(Datatype*)a) - (*(Datatype*)b);//这个函数通过差值判断是否交换
}void f() {srand((size_t)time(0));//随机数的种子Datatype a[30] { 0 };int i 0;for (i 0; i 30; i) {a[i] rand() % 100 1;//生成随机数printf(%d , a[i]);}printf(\n);//四个形参分别是数组名要排序的元素个数单个元素的大小程序员自定义的比较函数qsort(a, sizeof(a)/sizeof(a[0]), sizeof(Datatype), cmp);for (i 0; i 30; i)printf(%d , a[i]);
}int main() {f();return 0;
}快速排序框架quickSort
// 假设按照升序对array数组中[left, right)区间中的元素进行排序
void quickSort(Datatype* array, int left, int right)
{if (right - left 0)//区间只有1个值或区间不存在时没必要继续分return;// 按照基准值对array数组的 [left, right)区间中的元素进行划分int keyi partSort(array, left, right);// 划分成功后以keyi为边界形成了左右两部分 [left, keyi) 和 [keyi1, right)// 递归排[left, div)quickSort(array, left, keyi - 1);// 递归排[div1, right)quickSort(array, keyi 1, right);
}上述为快速排序递归实现的主框架发现与二叉树前序遍历规则非常像我们在写递归框架时可想想二叉树前序遍历规则即可快速写出来后序只需分析如何按照基准值来对区间中数据进行划分的方式即可。
虽然快速排序性能很优异但并不是所有情况快排都是最优选。甚至数据量小的情况比如10个数据快排对这10个数据排序耗时说不定比插入排序慢。我们学习排序是为了能判断所有情况并根据情况选择合适的排序算法来处理数据。 10个数据组成的数组看成完全二叉树就是4层递归的话还要多调用3次函数每次调用函数都要向内存申请空间加大时间和空间的成本。 若使用插入排序来处理这种数量比较小的数据则减少了多余的递归调用。能使排序完成时间缩短。 以满二叉树为例子最底层占 50 % 50\% 50%的结点后层数网上逐级减半3层的优化效率就是 50 % 25 % 12.5 % 87.5 % 50\%25\%12.5\%87.5\% 50%25%12.5%87.5%。 虽然我们不知道这个优化效率是怎么算出来的但是我们可以通过高精度计时库来计算10个元素时两种排序的耗时。参考程序如下c程序 #includestdio.h
#includestdlib.h
#includetime.h
#includestdlib.h
#includestdbool.h
#includechrono
#includeiostream
using namespace std;typedef int Datatype;int cmp(const void* a, const void* b) {return (*(Datatype*)a) - (*(Datatype*)b);
}void insertSort(Datatype* a, int n) {int i 0;for (i 0; i n - 1; i) {int end i;int tmp a[i 1];while (end 0)if (a[end] tmp) {a[end 1] a[end];--end;}else break;a[end 1] tmp;}
}void f() {srand((size_t)time(0));Datatype a[10], b[10];int i 0;for (i 0; i 10; i) {a[i] rand() % 1000 1;b[i] a[i];}auto begin std::chrono::high_resolution_clock::now();qsort(a, 10, 4, cmp);//用快排对10个数据进行排序auto end std::chrono::high_resolution_clock::now();std::chrono::durationdouble time1 end - begin;std::cout time1.count() endl;auto begin2 std::chrono::high_resolution_clock::now();insertSort(b, 10);//用插入排序对10个数据进行排序auto end2 std::chrono::high_resolution_clock::now();std::chrono::durationdouble time2 end2 - begin2;std::cout time2.count() endl;//如果快排用时比插入排序用时长则输出1否则输出0cout (time1.count() - time2.count() 1e-15) endl;
}int main() {f();return 0;
} chrono 库的 high_resolution_clock 可以提供高精度的时间点通过计算两个时间点的差值来得到代码执行的时间间隔 durationdouble 用于以秒为单位表示时间间隔 count() 函数返回该时间间隔的值。 用大量数据时表现不好小量数据时表现优异的算法处理这种小规模数据的优化方式有人称作小区间优化。这种优化的本质是一种锦上添花的行为无法改变算法本身的弊端。 到这里为冒泡排序惋惜1秒钟我确实没遇到过最适合冒泡排序的应用场景。
关于partSort函数的实现因为内容太多分成几篇来写。
