Tag: 排序

使用std :: sort（）按元素块排序: 我有一个边数组，它被定义为C风格的双精度数组，其中每4个双精度定义一个边，如下所示： double *p = …; printf(“edge1: %lf %lf %lf %lf\n”, p[0], p[1], p[2], p[3]); printf(“edge2: %lf %lf %lf %lf\n”, p[4], p[5], p[6], p[7]); 所以我想用std::sort()按边长度排序。如果它是一个struct Edge { double x1, y1, x2, y2; }; Edge *p; struct Edge { double x1, y1, x2, y2; }; Edge *p; ，我会很高兴。但在这种情况下，double数组的块大小不是由指针类型表示的。 qsort()允许您显式指定块大小，但std::sort()通过指针类型推断块大小。出于性能原因（内存使用和CPU），让我们说创建新数组或以某种方式转换数组是不可取的。出于性能原因，让我们说我们确实想使用std::sort()而不是qsort() 。是否可以在转换数据时不浪费单个CPU周期来调用std::sort() ？ […]

给定一个整数数组，找到第一个唯一的整数: 给定一个整数数组，找到第一个唯一的整数。我的解决方案：使用std::map 将整数（数字作为键，其索引作为值）逐一放入(O(n^2 lgn)) ，如果有重复，则在将所有数字放入之后从地图中删除条目(O(lg n))映射，迭代映射并找到索引为O（n）最小的密钥。 O(n^2 lgn)因为地图需要进行排序。效率不高。更好的解决方案？

使用一组有限的操作对2个50000个数字的链表进行排序: 所以我有这个项目用于学校：我有一个包含5万个数字和第二个空列表的链表。我只有一个非常有限的指示小组。他们是： “sa”交换了列表1的前两个元素 “sb”交换了清单2的前两个元素 “ss”同时是“sa”和“sb” “pa”：在列表1的顶部推送列表2的顶部元素 “pb”：在列表2的顶部推送列表1的顶部元素 “ra”：旋转列表1（第一个元素成为最后一个） “rb”：旋转列表2（第一个成为最后一个） “rr”：“ra”和“rb”立刻 “rra”：旋转列表1（最后成为第一个） “rrb”：旋转列表2（最后成为第一个） “rrr”：“rra”和“rrb”立刻我必须在c中实现排序算法，目标是使用最少量的指令。我尝试了一个非常简单的算法，旋转列表一直到最大值位于顶部，然后反复将其推入列表2，直到所有内容都在列表2中，然后将所有内容推回到列表1中，但我无法对列表进行排序在合理的时间内超过5k的数字

排序数组的最快搜索方法是什么？: 回答另一个问题，我编写了下面的程序来比较排序数组中的不同搜索方法。基本上我比较了插值搜索和二分搜索的两种实现。我通过计算不同变体所花费的周期（使用相同的数据集）来比较性能。但是我确信有一些方法可以优化这些function，使它们更快。有没有人对如何更快地使这个搜索function有任何想法？使用C或C ++的解决方案是可以接受的，但我需要它来处理具有100000个元素的数组。 #include #include #include #include #include static __inline__ unsigned long long rdtsc(void) { unsigned long long int x; __asm__ volatile (“.byte 0x0f, 0x31” : “=A” (x)); return x; } int interpolationSearch(int sortedArray[], int toFind, int len) { // Returns index of toFind in sortedArray, or -1 if not […]

一个很好的参考卡/备忘单与C中的基本排序算法？: 我一直在寻找（没有好运）完美的参考卡与C中的所有基本排序算法（或者可能在伪代码中）。维基百科是一个非常好的信息来源，但这一次我正在寻找一些更便携的东西（如果可能的话口袋大小），当然也可以打印。任何建议将不胜感激！

合并排序错误C.: 我正在尝试实现合并排序算法。我遵循CLRS书中提到的算法。这是我的代码 #include #include void merge_sort(int *arr,int start_index,int end_index); void merge(int *arr,int start_index,int middle_index,int end_index); int main(){ int arr[]={5,2,1,6,0,3,3,4}; //8 elements last index 7 int i; printf(“Before sorting.\n”); for(i=0;i<8;i++) printf("%d",arr[i]); merge_sort(arr,0,7); printf("\nAfter sorting.\n"); for(i=0;i<8;i++) printf("%d",arr[i]); return 0;} void merge_sort(int *arr,int start_index,int end_index){ int middle_index; if(start_index<end_index) { middle_index=(start_index+end_index)/2; merge_sort(arr,start_index,middle_index); merge_sort(arr,(middle_index+1),end_index); merge(arr,start_index,middle_index,end_index); } } void merge(int *arr, […]

C中的链表排序: 我正在为我的一个类编写一个简单的文件，这是一个简单的链表活动，我需要对链表进行排序。到目前为止这是我的源代码： /* * Simple list manipulation exercise. * 1. Create a list of integers. * 2. Print the list. * 3. Sort the list. * 4. Print the list * 5. Free the list nodes. */ #include #include struct node { int value ; struct node *next ; } ; extern struct node *mk_node(int […]

C中的自然排序 – “包含数字和字母的字符串数组”: 寻找一种经过validation的生产算法。看到这个例子，但没有在网上或书中找到其他东西。即file_10.txt> file_2.txt 谢谢。

无法快速排序变得稳定排序？: 方法1 CAR Hoare引入了分区逻辑（如下所示），这是在学校教授的， low = pivot = 0; i = 1; j = high = listSize-1; while (true) { while (a[i] <= a[pivot] && (i = a[pivot] && (j > low)) { j = j – 1; } if (i >= j) break; swap(a[i], a[j]) } swap(a[j], a[pivot]); // pivot element is positioned(once) return j; […]