网站总体规划设计说明,家装建材公司网站建设,如何在公司网站上添加内容,网页开发书籍目录
一、实现快速排序三种方法 1、hoare法
2、挖坑法
3、双指针法
4、快速排序的优化
5、测试对比
结语#xff1a; 前言#xff1a; 快速排序作为多种排序方法中效率最高的一种#xff0c;其底层原理被广泛运用#xff0c;他的核心思想与二叉树结构中的递归逻辑相似…
目录
一、实现快速排序三种方法 1、hoare法
2、挖坑法
3、双指针法
4、快速排序的优化
5、测试对比
结语 前言 快速排序作为多种排序方法中效率最高的一种其底层原理被广泛运用他的核心思想与二叉树结构中的递归逻辑相似首先标记一个元素作为基准点然后利用该基准点把数组分成左右两个区间并且使小于该基准点的元素放在左区间大于该基准点的元素放在右区间如此反复递归直到数组为一个有序数组。 实现快速排序的原理有三种方法hoare方法挖坑方法双指针方法。 一、实现快速排序三种方法 1、hoare法 比如将一个数组的起始位置记成left最后一个元素位置记成right那么标记left的位置的元素把该元素看成基准点key。 .这时候right要不断的向左移动若right所在位置的元素是小于key位置的元素那么right停止移动。left要不断的向右移动若left所在位置的元素是大于key位置的元素那么left停止移动。总结就是left找大right找小。注意若将left设置为key则先移动right然后才能移动left 当left和right都停下来后把他们的元素进行交换交换过后继续移动。 如此反复操作最后left会走到right的位置这时候left和right是处于同一位置的把该位置的元素和key位置的元素进行交换更新key的位置。 可以观察到此时数组有了一个特点以key为中心点左边区间的元素都是小于基准点key元素的右边区间的元素都是大于key元素的。 但是此时数组并不是一个有序的数组所以要通过多重递归因此将左边区间又看成一个小数组右边区间也看成一个小数组。此时左边区间的left就是下标为0的位置左边区间的right是key-1的位置。右边区间的left是key1的位置right是整个大数组的末尾处既大数组的right。通过递归不断让每个小数组变得有序最后整个数组也就有序了。 递归逻辑图如下 hoare版本快速排序代码实现
#includestdio.hvoid swap(int* p1, int* p2)//交换函数
{int temp *p1;*p1 *p2;*p2 temp;
}
int PatrSort1(int* a, int left, int right)//hoare法
{int key left;//定义基准点keywhile (left right)//当leftright说明还没相遇继续数组内元素的交换{while (left right a[right] a[key])//right找小{right--;}while (left right a[left] a[key])//left找大{left;}swap(a[right], a[left]);//交换left和right位置的元素}swap(a[key], a[left]);//跳出循环说明他们相遇了将他们位置的元素与key位置的元素交换key left;//更新key的位置return left;//返回key元素当前的下标
}void Qsort(int* a, int begin, int end)//快速排序递归法这里的beginleftendright
{if (begin end)//{return;}int key PatrSort1(a, begin, end);//每次递归都会找到一个属于该数组的keyQsort(a, begin, key - 1);//递归左右区间Qsort(a, key 1, end);
}void PrintArr(int* a, int n)//打印数组
{for (int i 0; i n; i){printf(%d , a[i]);}printf(\n);
}void Test_Qsort()//快排递归测试
{int arr[] { 5,10,6,1,2,4,3,9 };int sz sizeof(arr) / sizeof(int);PrintArr(arr, sz);Qsort(arr, 0, sz - 1);printf(hoare法);PrintArr(arr, sz);
}int main()
{Test_Qsort();return 0;
} 运行结果 2、挖坑法 思路和hoare法一样先定义一个基准点只不过把这个基准点叫做“坑”“坑”里的元素是要被抹除的也就是“坑”里不能有元素因此先用一个变量key来保存“坑”里的元素。right向左移动找到小于该基准点“坑”的元素就把这个元素填到“坑”里这时候“坑”里有了元素可以表示“坑”被填满了但是right位置的就变成了新的“坑”因为right位置的元素被用来“填坑”了。 下一次就是left找大的元素给到right位置的”坑“然后left的位置就成了新坑如此反复直到left和righ相遇待到他们相遇的位置必然是一个”坑“这时候把key存储的元素放到这个”坑“里此时会发现数组也以5key为中心点分成了两个区间而且左区间的元素都是小于key的右区间的元素都是大于key的。 挖坑法代码实现快速排序
#includestdio.hvoid swap(int* p1, int* p2)//交换函数
{int temp *p1;*p1 *p2;*p2 temp;
}
int PatrSort2(int* a, int left, int right)//挖坑法
{int key a[left];//把基准点元素的值保存起来int hole left;//设置hole更加形象表示坑while (left right)//相遇前进行相互“填坑”{if (left right a[right] key)//right找小{right--;}a[left] a[right];//填坑hole right;//right处变成新坑if (left right a[left] key)//left找大{left;}a[right] a[left];//填坑hole left;//left处变成新坑}a[hole] key;//最后left处是一个坑把key存的元素给到此处此处作为基准点return hole;//返回基准点的下标
}void Qsort(int* a, int begin, int end)//快速排序递归法
{if (begin end)//{return;}int key PatrSort2(a, begin, end);//每次递归都会找到一个属于该数组的keyQsort(a, begin, key - 1);//递归左右区间Qsort(a, key 1, end);
}void PrintArr(int* a, int n)//打印数组
{for (int i 0; i n; i){printf(%d , a[i]);}printf(\n);
}void Test_Qsort()//快排递归
{int arr[] { 5,10,6,1,2,4,3,9 };int sz sizeof(arr) / sizeof(int);PrintArr(arr, sz);Qsort(arr, 0, sz - 1);printf(挖坑法);PrintArr(arr, sz);
}int main()
{Test_Qsort();return 0;
} 运行结果 从结果可以看到不管是挖坑法还是hoare法都可以实现排序因为他们本身的逻辑是一样的。
3、双指针法 顾名思义就是依靠两个类似指针的变量去变量数组并且完成排序首先定义一个变量prev和一个变量cur分别在数组的第一个元素位置和第二个元素位置cur在prev的后边既cur在第二个元素位置并且把prev的位置设置成key基准点。当cur遇到比key小的元素则prev往后走一步然后prev的元素与cur的元素进行交换交换过后cur继续走。当cur遇到比key大的元素则prev不动cur继续走。 最后当cur走到数组外面表示遍历结束这时候prev所在位置的元素与key元素交换并且作为新的基准点。 此时数组也被分成了两个区间并且左边区间的元素小于key右边区间的元素大于key。 双指针法实现快速排序代码如下
#includestdio.hvoid swap(int* p1, int* p2)//交换函数
{int temp *p1;*p1 *p2;*p2 temp;
}
int PatrSort3(int* a, int left, int right)//双指针法
{int key left;//定义基准点int prev left;//定义两个变量int cur left 1;while (cur right)//当cur还在数组内时{if (a[cur] a[key] prev ! cur)//若cur元素小于keyi元素{prev;//prev向后走一步swap(a[cur], a[prev]);//交换cur和prev位置的元素}cur;//cur一直往后走}swap(a[prev], a[key]);//最后交换prev和key的元素key prev;//更新key的位置return key;//返回key的下标
}void Qsort(int* a, int begin, int end)//快速排序递归法
{if (begin end)//{return;}int key PatrSort3(a, begin, end);//每次递归都会找到一个属于该数组的keyQsort(a, begin, key - 1);//递归左右区间Qsort(a, key 1, end);
}void PrintArr(int* a, int n)//打印数组
{for (int i 0; i n; i){printf(%d , a[i]);}printf(\n);
}void Test_Qsort()//快排递归
{int arr[] { 5,10,6,1,2,4,3,9 };int sz sizeof(arr) / sizeof(int);PrintArr(arr, sz);Qsort(arr, 0, sz - 1);printf(双指针法);PrintArr(arr, sz);
}int main()
{Test_Qsort();return 0;
} 运行结果 从结果来看三个方法都可以实现快速排序。 三种方法的效率其实也不相上下但是目前快速排序有一个问题如果快速排序每次选key时都能选到中位数则快速排序的效率就很好时间复杂度为ON*logN但是快速排序在面对有序数组的排序下效率会很慢因为第一位数不是中位数其时间复杂度为ON^2。
4、快速排序的优化 针对以上的问题如果每次选key的时候都能选到数组偏中位数的值那么就解决了该问题因此当我们有了一个数组的left和right那么可以假设一个中间值midleftright/2通过对比他们三者之间的关系从而得到三者的中间值。 三数取中代码如下
int GetMid(int* a, int left, int right)//针对有序数组排序的三数取中
{int mid (left right) / 2;//先定义一个mid中间值//对比他们三者之间的关系选出三者之间的中间值if (a[left] a[mid]){if (a[right] a[left])return left;else if (a[mid] a[right])return right;elsereturn mid;}else{if (a[mid] a[right])return mid;else if (a[right] a[left])return left;elsereturn right;}
}
5、测试对比 通过测试对比优化前的快速排序的效率和优化后快速排序的效率测试代码如下
#includestdio.h
#includestdlib.h
#includetime.hint GetMid(int* a, int left, int right)//针对有序数组排序的三数取中
{int mid (left right) / 2;//先定义一个mid中间值//对比他们三者之间的关系选出三者之间的中间值if (a[left] mid){if (a[right] a[left])return left;else if (a[mid] a[right])return right;elsereturn mid;}else{if (a[mid] a[right])return mid;else if (a[right] a[left])return left;elsereturn right;}
}void swap(int* p1, int* p2)//交换函数
{int temp *p1;*p1 *p2;*p2 temp;
}
int PatrSort3(int* a, int left, int right)//双指针法
{int key left;//定义基准点int temp GetMid(a, left, right);swap(a[temp], a[key]);//使keyi处的元素是三数取中的结果int prev left;//定义两个变量int cur left 1;while (cur right)//当cur还在数组内时{if (a[cur] a[key] prev ! cur)//若cur元素小于keyi元素{prev;//prev向后走一步swap(a[cur], a[prev]);//交换cur和prev位置的元素}cur;//cur一直往后走}swap(a[prev], a[key]);//最后交换prev和key的元素key prev;//更新key的位置return key;//返回key的下标
}void Qsort(int* a, int begin, int end)//快速排序递归法
{if (begin end)//{return;}int key PatrSort3(a, begin, end);//每次递归都会找到一个属于该数组的keyQsort(a, begin, key - 1);//递归左右区间Qsort(a, key 1, end);
}void Contrast_test()//对比测试
{//手动构建数组int n 100000;srand(time(0));int* n1 (int*)malloc(sizeof(int) * n);int* n2 (int*)malloc(sizeof(int) * n);int* n3 (int*)malloc(sizeof(int) * n);int* n4 (int*)malloc(sizeof(int) * n);int* n5 (int*)malloc(sizeof(int) * n);int* n6 (int*)malloc(sizeof(int) * n);for (int i 0; i n; i){n1[i] rand() % 10000;n2[i] n1[i];n3[i] n1[i];n4[i] n1[i];n5[i] n1[i];n6[i] n1[i];}//先让数组排成有序//clock函数返回的是系统启动到调用该函数的时间单位是毫秒并存到变量中int start1 clock();Qsort(n1, 0, n - 1);int end1 clock();//在进行对有序数组的排序int start2 clock();Qsort(n1, 0, n - 1);int end2 clock();printf(key为中间值对有序数组的排序:\n);printf(Test_PatrSort3:%d\n, end1 - start1);printf(Test_PatrSort3:%d\n, end2 - start2);free(n1);free(n2);free(n3);free(n4);free(n5);free(n6);
}int main()
{Contrast_test();return 0;
} 运行结果优化前 运行结果优化后 通过结果可以发现优化之后的快速排序在面对有序的数组效率依然很高。
结语 以上就是关于快速排序的介绍最后希望本文可以给你带来更多的收获如果本文对你起到了帮助希望可以动动小指头帮忙点赞关注收藏如果有遗漏或者有误的地方欢迎大家在评论区补充~谢谢大家(▽)
