网站开发可演示的版本,用树莓派做网站服务器好吗,邯郸市城乡住房建设局网站,网站建好了 怎么建后台一#xff0c;选择排序 选择排序算是简单排序中的渣渣#xff0c;这种算法基本上是没有什么用处的。但是作为一个初学者#xff0c;我又必须要会写这种算法。这种算法的实现实现思想和它的名字一样#xff0c;就是在一个范围内选择最大或者最小的数据然后再交换数据实现排序…
一选择排序 选择排序算是简单排序中的渣渣这种算法基本上是没有什么用处的。但是作为一个初学者我又必须要会写这种算法。这种算法的实现实现思想和它的名字一样就是在一个范围内选择最大或者最小的数据然后再交换数据实现排序。比如我有如下数据需要排序 将数据具象化以后变成这样 现在我们可以选择的范围是哪些呢 范围 begin:0 end:n-1。 然后我们要在这个范围内选择最大的数据或者最小的数据与尾/首的数据进行交换再将选择范围缩小 先设置begin的后一个为最小值end的前一个为最大值然后遍历调整得到真的最大和最小值的下标。然后将最小值和begin指向的位置交换最大值和end指向的下标的值交换。用这个逻辑不断地走不断地缩小查找范围当查找范围没了即endbegin不再成立以后排序就完成了。 代码
void swap(int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}
void selectSort(int* a, int n)
{ //初始的查找范围int end n - 1;int begin 0;//while循环判断查找空间是否还有while (begin end){ //实现交换逻辑int maxi end-1;int mini begin1;for (int i begin;i end;i){if (a[i] a[maxi]){maxi i;}if (a[i] a[mini]){mini i;}}swap(a[maxi], a[end]);//处理特殊情况当mini与end指向同一数据时需要处理一下if (mini end){mini maxi;}swap(a[mini], a[begin]);//缩小查找范围end--;begin;}} 二堆排序 堆排序也是选择排序的一种。但是堆排序的速度比原始的选择排序快多了。 比如下面的数据 如果使用堆排序的话就要先将这些数据看成满二叉树的结构 然后就要建堆了 建堆原则排升序建大堆排降序建小堆。 建堆排升序变成这样 建堆完成以后便要执行下面的操作 1.交换首尾数据。 2.缩小范围。 3.向下调整。 经过这几步以后堆排序就写好了。 堆排序代码
void AdjustDown(int* a, int n,int parent)
{int child 2 * parent 1;while (child n){if (child 1 n a[child 1] a[child]){child;}if (a[child] a[parent]){swap(a[parent], a[child]);}parent child;child parent * 2 1;}}
void heapSort(int* a, int n)
{//向下调整建堆for (int i (n - 1 - 1) / 2;i 0;i--){AdjustDown(a, n,i);}int end n - 1;for (int i end; i 0;i--){ //交换首尾数据swap(a[end], a[0]);//向下调整AdjustDown(a, end, 0);//缩小调整范围end--;}
}三性能比较 堆排序是一个很好的算法选择排序是一个很慢的算法。但是口说无凭现在就写一段代码来验证这个事实。 代码
void test()
{ //创建两个数组并将两个数组内的数据搞成随机值srand(time(0));int n 100000;int* a1 (int*)malloc(sizeof(int) * n);int* a2 (int*)malloc(sizeof(int) * n);int i 0;for ( i 0;i n;i){int j rand();a1[i] j;a2[i] a1[i];}//记录选择排序的时间int begin1 clock();selectSort(a1, n);int end1 clock();//记录堆排序的时间int begin2 clock();heapSort(a2, n);int end2 clock();//打印两个排序的时间printf(selectSort:%d\n, end1 - begin1);printf(heapSort:%d\n, end2 - begin2);//释放内存free(a1);free(a2);
}
排十万个数据的时间单位ms)
selectSort:5051
heapSort:30
从结果可以看到堆排序的效率暴打选择排序。
