Quicksort比Mergesort慢？ - 腾讯云开发者社区 - 腾讯云

开发者社区

文档建议反馈控制台

文章/答案/技术大牛

发布

ThreadLocal比FastThreadLocal慢在哪里？

吊打 ThreadLocal，谈谈 FastThreadLocal 为啥能这么快？

6731 0

精益求精单链表归并排序与快速排序

通过2个快慢指针，快指针每一步走2个节点，慢指针每一步走1个节点，当快指针到达链表尾部时，慢指针到达链表的中间节点。...(head); } ListNode* __mergesort(ListNode* node) { if(!...node->next) return node; ListNode *fast=node;//快指针走两步 ListNode *slow=node;//慢指针走一步 ListNode...); } 3.改变链接的快速排序改变链接的指向思路：将比枢椎（这里选择第一个节点）小的值，链接到一个小于枢椎的链表中；比枢椎大的值，链接到一个大于枢椎的链表中；将小于枢椎值的链表，枢椎节点，大于枢椎值的链表链接起来..., pivot); quickSort(pivot->next, tail); } } ListNode* sortList3(ListNode* head) { quickSort

2.3K3 0

您找到你想要的搜索结果了吗？

是的

没有找到

基础算法之排序算法

每次迭代，比flag大的放右边，比flag小的放左边，重点在partition上 def quicksort(nums, l, r): if l < r: p = partition...(nums, l, r) quicksort(nums, l, p-1) quicksort(nums, p+1, r) return nums def...self.quicksort(nums, l, p-1) self.quicksort(nums, p+1, r) return nums...class mergesort: def mergesort(self, nums): if len(nums) <= 1: return nums mid =...len(nums) // 2 left = self.mergesort(nums[:mid]) right = self.mergesort(nums[mid:])

6665 0

C++快速排序原理深究优化

(vector& A) { _mergesort(A, 0, A.size()-1); } 快速排序原理核心思想：选取一个基准元素 pivot，比 pivot 小的放到左边，比 pivot...", arr1, mergesort); sort_helper::testsort("quicksort", arr2, quicksort); //...", arr3, mergesort); sort_helper::testsort("quicksort", arr4, quicksort);...", arr5, mergesort); sort_helper::testsort("quicksort", arr6, quicksort); } 运行结果如下...", arr1, mergesort); sort_helper::testsort("quicksort2", arr2, quicksort2); /

8870 1

Sort Algorithm排序算法

也是一样的，直接进入到第三次迭代，这时候就是指向1了，所以5和1比，需要换： ? 1和4比，又有： ? 和2比，又有： ? 就是这样以此类推。...使用10000个数据进行排序（python实现本来就慢。） ? 插入排序还是比选择排序要慢。...但是它前面还有一个系数，这个系数是比归并排序的系数大的，所以一开始小数据量插入排序是比归并排序要快的，只是到后面的增长超过了而已，所以可以切分到10或者20个然后插入排序即可。...但是quick sort还是比merge sort要快很多。...('mergeSort', mergetime, 's') print('quickSort', quicktime, 's') print('quickSort_rand', quicktime_random

1.4K2 0

java的几种排序算法(常用排序算法)

堆排序踩坑 v1.0 巨慢不能用 v2.0 太慢不能用 v3.0 9. 其他排序 7....(s < e){ mergeSort(a,s,m); mergeSort(a,m+1,e); //归并 merge(a,s,m,e);...insertSort耗时: 2 ms selectSort耗时: 3 ms //---1w--- quickSort耗时: 2 ms mergeSort: 3 ms listSort耗时: 19 ms...耗时: 15044 ms insertSort耗时: 797 ms selectSort耗时: 4073 ms //---20w--- quickSort耗时: 26 ms mergeSort: 34...增加了堆排序 // 20w数据 quickSort耗时: 39 ms mergeSort: 32 ms 创建完毕 heapSort耗时: 21 ms listSort耗时: 111 ms arraysSort

9022 0

数据结构-排序

void QuickSort(int* a, int left, int right) { if (left >= right) return; if ((right - left + 1)...(a, left, keyi - 1); QuickSort(a, keyi + 1, right); } } 三数取中 int GetMidi(int* a, int left,...} } STDestroy(&st); } 利用前后指针法继续快速排列用两个指针较快的指针走前面较慢的指针走后门如果较快的指针找到了小于keyi的值，就和慢指针进行交换...（慢指针的下一个不能是快指针，如果是的话跳过），当快指针越界后，把keyi和慢指针所指的数据进行交换。...== end) return; int mid = (begin + end) / 2; //递 _MergeSort(a, tmp, begin, mid); _MergeSort(a,

2021 0

C#经典排序算法总结（三）之三种快速排序算法

(arr, left, pivotIndex - 1,aa); QuickSort(arr, pivotIndex + 1, right,aa); } }...(arr, left, mid,aa); MergeSort(arr, mid + 1, right,aa); Merge(arr, left, mid, right,aa...虽然归并排序的时间复杂度与快速排序相同，但它的算法稳定性比快速排序更好，通常情况下效率也不低，因此对于大型数据排序和数据量不是特别大的情况下，归并排序是一种很好的选择。...其实际行时间比快速排序略慢，但是更适用于大数据量的排序，并且是外排序产生的基础算法。因此，一般来说，当待排序序列的数据量较大时，归并排序是更佳选择。...它具有不错的实际应用性能，同时对于数据有一定规模的情况下，它的效率比快速排序还要高。

951 0

【排序算法（二）】——冒泡排序、快速排序和归并排序—＞深层解析

//_QuickSort⽤于按照基准值将区间[left,right)中的元素进⾏划分 int meet = _QuickSort(a, left, right); QuickSort(a, left...从左到右找出比基准值大的数据，从右到左找出比基准值小的数据，左右指针数据交换，进入下一次循环这里可能有一些问题， 1.跳出循环后，right位置的值一定不大于key？ ...，找到后立即放入左边 "坑" 中，当前位置变为新的 "坑"，然后从左往右找出比基准值大的数据，找到后立即放入右边坑中，当前位置变为新的 "坑"，结束循环后将最开始存储的分界值放入当前的 "坑"中，返回当前...代码实现： //归并排序 void _MergeSort(int* arr, int left, int right,int* tmp) { if (left >= right) { return...; } int mid = (left + right) / 2; _MergeSort(arr, left, mid, tmp); _MergeSort(arr, mid+1, right,

3101 0

为什么Python比C++慢很多？

接下来需要分析的无非是Python慢在哪个细节，以及能否改进的问题。下面是两段用来测试的代码，首先是Python的： class="highlight"> #!

1.1K5 0

常见几种java排序算法

堆排序踩坑 v1.0 巨慢不能用 v2.0 太慢不能用 v3.0 9. 其他排序 7. 比较 0....(s < e){ mergeSort(a,s,m); mergeSort(a,m+1,e); //归并 merge(a,s,m,e);...insertSort耗时: 2 ms selectSort耗时: 3 ms //---1w--- quickSort耗时: 2 ms mergeSort: 3 ms listSort耗时: 19 ms...耗时: 15044 ms insertSort耗时: 797 ms selectSort耗时: 4073 ms //---20w--- quickSort耗时: 26 ms mergeSort: 34...增加了堆排序 // 20w数据 quickSort耗时: 39 ms mergeSort: 32 ms 创建完毕 heapSort耗时: 21 ms listSort耗时: 111 ms arraysSort

3672 0

排序算法的 Python 实现以及时间复杂度分析

() 函数为了保证归并排序函数 MergeSort () 输入只有未排序的数组，这里调用前面的辅助函数 sort ()： def MergeSort(nums): aux = nums.copy...pivot 选取的理想情况是：让分区中比 pivot 小的元素数量和比 pivot 大的元素数量差不多。...': MergeSort(a) if sortname == 'QuickSort': QuickSort(a) if sortname == 'QuickSort3Ways...total time:") print(timeRandomInput('MergeSort',length,numberOfArrays)) print("QuickSort's total time...: 0.08862972259521484 总结 BubbleSort SelectSort InsertSort MergeSort QuickSort QuickSort3Ways 随机数据集 30.023

1.9K2 0

归并快排算法比较及求第K大元素

递推公式： merge_sort(p...r) = merge(mergesort(p...q), mergesort(q+1...r)) 终止条件： p >= r 不用继续分解 mergesort(...将这个排序问题转化为两个子问题 mergesort(p...q) 和mergesort(q+1...r)，其中 q 为 p 和 r 的中间位置，即(p+r)/2。...快速排序核心思想：选取一个基准元素 pivot，比 pivot 小的放到左边，比 pivot 大的放到右边，对 pivot 左右两边的序列递归进行以上操作。...地推公式如下：递推公式： quicksort(p…r) = quicksort(p…q-1) + quicksort(q+1...r) 终止条件： p >= r 在wikipedia看到一个比较好的快速排序实现...r); quicksort(A, l, p-1); quicksort(A, p+1, r); } } int partition(vector&

1.1K3 0

基于C++的归并排序、快速排序、希尔排序对比测试

/辅助空间的数据覆盖到原空间 for (int i = 0; i < length; i++) { arr[start + i] = temp[i]; } } //归并排序 void MergeSort...(arr, start, mid, temp); //右半边 MergeSort(arr, mid + 1, end, temp); //合并 Merge(arr, start, end,mid...= start; int j = end; int temp = arr[start]; //基准数 if (i < j) { while (i < j) { //从右向左找比基准数小的数字...temp) { j--; } //填坑 if (i < j) { arr[i] = arr[j]; i++; } //从左向右找比基准数大的数字...(arr, start, i - 1); //对右半边进行快速排序 QuickSort(arr, i + 1, end); } } int main(void) { int* myArr

7803 0

【数据结构初阶第十九节】八大排序系列(下篇)—

arr, int left, int right) { int hole = left; int key = arr[left]; while (left < right) { //从右往左找比基准值小的...right && arr[right] > key) { right--; } arr[hole] = arr[right]; hole = right; //从左往右找比基准值大的...(arr,left,right); //2.左子序列进行排序 QuickSort(arr, left, key - 1); //3.右子序列进行排序 QuickSort(arr, key + 1...{ return; } int mid = (left + right) / 2; _MergeSort(arr, left, mid, tmp); _MergeSort(arr, mid+...// while (left <= right && arr[left] < arr[key]) // { // left++; // } // //找比基准值小的 // while (

2090 0

【C++】常用排序算法

快速排序（Quick Sort）：选择一个基准元素，将序列分为比基准小的元素和比基准大的元素。递归地对划分后的子序列进行快速排序。...) { arr[k] = R[j]; j++; k++; } delete[] L; delete[] R; } void mergeSort...(arr, left, mid); mergeSort(arr, mid + 1, right); merge(arr, left, mid, right);...} } // 快速排序 quickSort int partition(int arr[], int low, int high) { int pivot = arr[high]; int...(arr, low, pi - 1); quickSort(arr, pi + 1, high); } } // 打印数组 void printArray(int arr[],

4051 0

Java数据结构与算法--排序算法

插入排序；归并排序；快速排序；前三种是基本排序算法，后两个是高级的排序算法；冒泡排序最慢的排序算法之一，数据值会像气泡一样从数组的一段漂浮到另一端基本思路： 1.依次比较相邻的两个数，如果第一个比第二个小...如果第一个比第二个大，调换顺序。一轮下来，最后一个是最大的数 2.对除了最后一个之外的数重复第一步，直到只剩一个数图形展示： ?...(left), mergeSort(right)); return merge(mergeSort(left), mergeSort(right)); } //测试一下 var dataStore...比基准小的放到左边，比基准大的放到右边 2.再按此方法对这两部分数据分别进行快速排序（递归进行） 3.不能再分后退出递归，并将数组合并图形展示： ?...(quickSort(dataStore));

5092 0

（五）算法基础——分治

实例称硬币 16硬币，有可能有1枚假币，假币比真币轻。有一架天平，用最少称量次数确定有没有假币，若有的话，假币是哪一枚。 ...(int a[],int s,int e,int tmp[]) { if( s < e) { int m = s + (e-s)/2; MergeSort(a,s,m,tmp); MergeSort...这样的话复杂度是O(n+mlogm)，在大部分情况下，比第一种解法要更好。...操作如何将前k大的都弄到最右边设key=a[0], 将key挪到适当位置，使得比key小的元素都在 key左边，比key大的元素都在key右边（线性时间完成）选择数组的前部或后部再进行 arrangeRight...(int a[],int s,int e,int tmp[]) { if( s < e) { int m = s + (e-s)/2; MergeSort(a,s,m,tmp); MergeSort

3891 0

几种排序算法

并归排序 public class MergeSort { private static void merge(int a[], int first, int mid, int last)...递归排序 * * @param a * @param first * @param last */ private static void mergeSort...(a, first, mid); // 右边有序 mergeSort(a, mid + 1, last); merge(a, first...当i根节点的值比左孩子节点的值要小的时候，就把i根节点和左孩子节点所对应的值交换，当i根节点的值比右孩子的节点所对应的值要小的时候，就把i根节点和右孩子节点所对应的值交换。...(a, start, i - 1); // quickSort(a, i + 1, end); return i; } /** * 选取第k个数

4202 0

数据结构（C语言篇）：（十九）归并排序和非比较排序

int begin4 = clock(); HeapSort(a4, N); int end4 = clock(); int begin5 = clock(); QuickSort...printf("SelectSort:%d\n", end3 - begin3); printf("HeapSort:%d\n", end4 - begin4); printf("QuickSort...free(a3); free(a4); free(a5); free(a6); free(a7); } 我们分析代码的运行结果，可以得到以下结论：快速排序（QuickSort...）：最快，时间最短；堆排序（HeapSort）：略慢于快速排序，但性能稳定；归并排序（MergeSort）：与堆排序接近，略慢于快速排序；希尔排序（ShellSort）：比上述三种算法慢，但远快于简单排序...；插入排序（InsertSort）：明显慢于希尔排序；选择排序（SelectSort）：比插入排序更慢；冒泡排序（BubbleSort）：最慢，可能需要极长的时间。

1241 0

点击加载更多

相关资讯

热门标签

活动推荐

运营活动

活动名称

广告关闭