问题
我需要一种算法，它可以找到具有线性时间复杂度 O(n) 和恒定空间复杂度 O(1) 的单链表的中位数。

编辑：单链表是 C 风格的单链表。不允许使用 stl（没有容器，没有函数，禁止所有 stl，例如没有 std::forward_list）。不允许在任何其他容器（例如数组）中移动数字。

O(logn) 的空间复杂度是可以接受的，因为我的列表实际上小于 100。另外，我不允许使用像 nth_element 这样的 STL 函数

基本上，我有一个包含 3*10^6 元素的链表，我需要在 3 秒内得到中位数，所以我不能用排序算法对列表进行排序（它会是 O(nlogn)，它可能需要 10-14 秒）。

我在网上做了一些搜索，发现 std::vector 与 quickselect 的中位数可以在 O(n) 和 O(1) 空间中找到（最坏的情况是 O(n^2)，但很少看到），例如：

但是我找不到任何算法来为链表执行此操作。问题是，我可以使用数组索引随机访问向量，如果我想修改算法，复杂度会大得多，因为。例如，当我将枢轴索引更改为左时，我实际上需要遍历列表以获取新元素并走得更远（这将使我的列表至少 O(k n) 和一个大 k，甚至 O(n^ 2)…)。

编辑2：

我知道我有太多变量，但我一直在测试不同的东西，我仍然在我的代码中。 . .

我当前的代码：

1. #include <bits/stdc++.h>
   
2. 
   
3. using namespace std;
   
4. 
   
5. template <class T> class Node {
   
6.     public:
   
7.     T data;
   
8.     Node<T> *next;
   
9. };
   
10. 
    
11. template <class T> class List {
    
12.     public:
    
13.     Node<T> *first;
    
14. };
    
15. 
    
16. template <class T> T getMedianValue(List<T> & l) {
    
17.     Node<T> *crt,*pivot,*incpivot;
    
18.     int left, right, lung, idx, lungrel,lungrel2, left2, right2, aux, offset;
    
19.     pivot = l.first;
    
20.     crt = pivot->next;
    
21.     lung = 1;
    
22. //lung is the lenght of the linked list (yeah it's lenght in romanian...)
    
23. //lungrel and lungrel2 are the relative lenghts of the part of
    
24. //the list I am processing, e.g: 2 3 4 in a list with 1 2 3 4 5
    
25.     right = left = 0;
    
26.     while (crt != NULL) {
    
27.         if(crt->data < pivot->data){
    
28.             aux = pivot->data;
    
29.             pivot->data = crt->data;
    
30.             crt->data = pivot->next->data;
    
31.             pivot->next->data = aux;
    
32.             pivot = pivot->next;
    
33.             left++;
    
34.         }
    
35.         else right++;
    
36.        // cout<<crt->data<<endl;
    
37.         crt = crt->next;
    
38.         lung++;
    
39.     }
    
40.     if(right > left) offset = left;
    
41. //  cout<<endl;
    
42. //  cout<<pivot->data<<" "<<left<<" "<<right<<endl;
    
43. //  printList(l);
    
44. //  cout<<endl;
    
45.     lungrel = lung;
    
46.     incpivot = l.first;
    
47.    // offset = 0;
    
48.     while(left != right){
    
49.         //cout<<"parcurgere"<<endl;
    
50.         if(left > right){
    
51.             //cout<<endl;
    
52.             //printList(l);
    
53.             //cout<<endl;
    
54.             //cout<<"testleft "<<incpivot->data<<" "<<left<<" "<<right<<endl;
    
55.             crt = incpivot->next;
    
56.             pivot = incpivot;
    
57.             idx = offset;left2 = right2 = lungrel = 0;
    
58.             //cout<<idx<<endl;
    
59.             while(idx < left && crt!=NULL){
    
60.                  if(pivot->data > crt->data){
    
61.                    //  cout<<"1crt "<<crt->data<<endl;
    
62.                      aux = pivot->data;
    
63.                      pivot->data = crt->data;
    
64.                      crt->data = pivot->next->data;
    
65.                      pivot->next->data = aux;
    
66.                      pivot = pivot->next;
    
67.                      left2++;lungrel++;
    
68.                   }
    
69.                   else {
    
70.                       right2++;lungrel++;
    
71.                       //cout<<crt->data<<" "<<right2<<endl;
    
72.                   }
    
73.                   //cout<<crt->data<<endl;
    
74.                   crt = crt->next;
    
75.                   idx++;
    
76.              }
    
77.              left = left2 + offset;
    
78.              right = lung - left - 1;
    
79.              if(right > left) offset = left;
    
80.              //if(pivot->data == 18) return 18;
    
81.              //cout<<endl;
    
82.              //cout<<"l "<<pivot->data<<" "<<left<<" "<<right<<" "<<right2<<endl;
    
83.            //  printList(l);
    
84.         }
    
85.         else if(left < right && pivot->next!=NULL){
    
86.             idx = left;left2 = right2 = 0;
    
87.             incpivot = pivot->next;offset++;left++;
    
88.             //cout<<endl;
    
89.             //printList(l);
    
90.             //cout<<endl;
    
91.             //cout<<"testright "<<incpivot->data<<" "<<left<<" "<<right<<endl;
    
92.             pivot = pivot->next;
    
93.             crt = pivot->next;
    
94.             lungrel2 = lungrel;
    
95.             lungrel = 0;
    
96.            // cout<<"p right"<<pivot->data<<" "<<left<<" "<<right<<endl;
    
97.             while((idx < lungrel2 + offset - 1) && crt!=NULL){
    
98.                  if(crt->data < pivot->data){
    
99.                 //     cout<<"crt "<<crt->data<<endl;
    
100.                      aux = pivot->data;
     
101.                      pivot->data = crt->data;
     
102.                      crt->data = (pivot->next)->data;
     
103.                      (pivot->next)->data = aux;
     
104.                      pivot = pivot->next;
     
105.                  //    cout<<"crt2 "<<crt->data<<endl;
     
106.                      left2++;lungrel++;
     
107.                   }
     
108.                   else right2++;lungrel++;
     
109.                   //cout<<crt->data<<endl;
     
110.                   crt = crt->next;
     
111.                   idx++;
     
112.              }
     
113.              left = left2 + left;
     
114.              right = lung - left - 1;
     
115.                  if(right > left) offset = left;
     
116.             // cout<<"r "<<pivot->data<<" "<<left<<" "<<right<<endl;
     
117.            //  printList(l);
     
118.         }
     
119.         else{
     
120.             //cout<<cmx<<endl;
     
121.             return pivot->data;
     
122.         }
     
123.     }
     
124.     //cout<<cmx<<endl;
     
125.     return pivot->data;
     
126. }
     
127. template <class T> void printList(List<T> const & l) {
     
128.     Node<T> *tmp;
     
129.     if(l.first != NULL){
     
130.         tmp = l.first;
     
131.         while(tmp != NULL){
     
132.             cout<<tmp->data<<" ";
     
133.             tmp = tmp->next;
     
134.         }
     
135.     }
     
136. }
     
137. template <class T> void push_front(List<T> & l, int x)
     
138. {
     
139.     Node<T>* tmp = new Node<T>;
     
140. 
     
141.     tmp->data = x;
     
142. 
     
143.     tmp->next = l.first;
     
144.     l.first = tmp;
     
145. }
     
146. 
     
147. int main(){
     
148.     List<int> l;
     
149.     int n = 0;
     
150.     push_front(l, 19);
     
151.     push_front(l, 12);
     
152.     push_front(l, 11);
     
153.     push_front(l, 101);
     
154.     push_front(l, 91);
     
155.     push_front(l, 21);
     
156.     push_front(l, 9);
     
157.     push_front(l, 6);
     
158.     push_front(l, 25);
     
159.     push_front(l, 4);
     
160.     push_front(l, 18);
     
161.     push_front(l, 2);
     
162.     push_front(l, 8);
     
163.     push_front(l, 10);
     
164.     push_front(l, 200);
     
165.     push_front(l, 225);
     
166.     push_front(l, 170);
     
167.     printList(l);
     
168.     n=getMedianValue(l);
     
169.     cout<<endl;
     
170.     cout<<n;
     
171. 
     
172.     return 0;
     
173. }

复制代码

您对如何使快速选择适应单独列出的链接或其他可以解决我的问题的算法有任何建议吗？

回答
在您的问题中，您提到将枢轴点向左移动时遇到问题，因为这需要遍历列表。如果你做对了，你只需要遍历整个列表两次：

如果你不太在意选择一个好的枢轴，只是喜欢选择列表中的第一个元素作为枢轴（如果数据已经排序，这将导致最坏情况 O(n^ 2）时间复杂度），不需要第一步。

如果第一次遍历链表的尾端，通过保持指向链表尾的指针，就不必再次遍历它来找到尾了。此外，如果您使用标准 Lomuto 分区方案（我不这样做，原因如下所述），您还必须在列表中保留两个指针，表示标准 Lomuto 分区方案的 i 和 j 索引.通过使用这些指针，您永远不必遍历列表来访问单个元素。

此外，如果您保留一个指向每个分区的中间和结尾的指针，那么当您稍后必须对其中一个分区进行排序时，您不必再次遍历该分区来找到中间和结尾。

我现在已经为链表创建了我自己的 QuickSelect 算法实现，我已经在下面发布了。

既然你说链表是单链表，不能升级成双链表，那我就不能用Hoare分区方案了，因为反向迭代单链表代价很大。所以我正在使用通常效率较低的 Lomuto 分区方案。

在使用 Lomuto 分区方案时，通常选择第一个元素或最后一个元素作为轴。然而，选择这两种方法中的任何一种都有一个缺点，即排序数据将导致算法的最坏情况时间复杂度为 O(n^2)。这可以通过根据“三的中值”选择轴来防止。规则，即从第一个元素、中间元素和最后一个元素的中值中选择轴。所以在我的实现中，我使用这个“三位数”。规则。

此外，Lomuto 分区方案通常会创建两个分区，一个用于小于轴的值，一个用于大于或等于轴的值。但是，如果所有值都相同，这将导致 O(n^2) 的最坏情况时间复杂度。所以，在我的实现中，我创建了三个分区，一个用于小于轴的值，一个用于大于轴的值，一个用于等于轴的值。

虽然这些措施并没有完全消除 O(n^2) 的最坏情况时间复杂度的可能性，但它们至少使其极不可能发生。

我遇到的一个重要问题是，对于偶数个元素，中位数被定义为两个“中间”元素的算术平均值。或“中间”元素。所以我不能简单地调用函数 find_nth_element 因为例如，如果元素的总数是 14，那么我将寻找第 7 和第 8 个最大的元素。这意味着我将不得不两次调用这样的函数，这将是低效的。所以我写了一个搜索“中位数”的函数。同时元素。尽管这使代码更加复杂，但与不必调用相同函数两次的优势相比，由于额外代码复杂性导致的性能损失应该是最小的。

请注意，虽然我的实现完全在 C++ 编译器上编译，但我不会将其称为教科书 C++ 代码，因为它禁止使用 C++ 标准模板库中的任何内容。所以我的代码是 C 代码和 C++ 代码的混合体。

1. #include <iostream>
   
2. #include <iomanip>
   
3. #include <cassert>
   
4. 
   
5. //remove the comment in the following line for extra debugging information
   
6. //#define PRINT_DEBUG_INFO
   
7. 
   
8. template <typename T>
   
9. struct Node
   
10. {
    
11.     T data;
    
12.     Node<T> *next;
    
13. };
    
14. 
    
15. // NOTE:
    
16. // The return type is not necessarily the same as the data type. The reason for this is
    
17. // that, for example, the data type "int" requires a "double" as a return type, so that
    
18. // the arithmetic mean of "3" and "6" returns "4.5".
    
19. // This function may require template specializations to handle overflow or wrapping.
    
20. template<typename T, typename U>
    
21. U arithmetic_mean( const T &first, const T &second )
    
22. {
    
23.     return ( static_cast<U>(first) + static_cast<U>(second) ) / 2;
    
24. }
    
25. 
    
26. //the main loop of the function find_median can be in one of the following three states
    
27. enum LoopState
    
28. {
    
29.     //we are looking for one median value
    
30.     LOOPSTATE_LOOKINGFORONE,
    
31. 
    
32.     //we are looking for two median values, and the returned median
    
33.     //will be the arithmetic mean of the two
    
34.     LOOPSTATE_LOOKINGFORTWO,
    
35. 
    
36.     //one of the median values has been found, but we are still searching for
    
37.     //the second one
    
38.     LOOPSTATE_FOUNDONE
    
39. };
    
40. 
    
41. template <
    
42.     typename T, //type of the data
    
43.     typename U  //type of the return value
    
44. >
    
45. U find_median( Node<T> *list )
    
46. {
    
47.     //This variable points to the pointer to the first element of the current partition.
    
48.     //During the partition phase, the linked list will be broken and reassembled afterwards, so
    
49.     //the pointer this pointer points to will be nullptr until it is reassembled.
    
50.     Node<T> **pp_start = &list;
    
51. 
    
52.     //these pointer are maintained for accessing the middle of the list for selecting a pivot using
    
53.     //the "median-of-three" rule
    
54.     Node<T> *p_middle;
    
55.     Node<T> *p_end;
    
56. 
    
57.     //result is not defined if list is empty
    
58.     assert( *pp_start != nullptr );
    
59. 
    
60.     //in the main loop, this variable always holds the number of elements in the current partition
    
61.     int num_total = 1;
    
62. 
    
63.     // First, we must traverse the entire linked list in order to determine the number of elements,
    
64.     // in order to calculate k1 and k2. If it is odd, then the median is defined as the k'th smallest
    
65.     // element where k = n / 2. If the number of elements is even, then the median is defined as the
    
66.     // arithmetic mean of the k'th element and the (k+1)'th element.
    
67.     // We also set a pointer to the nodes in the middle and at the end, which will be required later
    
68.     // for selecting a pivot according to the "median-of-three" rule.
    
69.     p_middle = *pp_start;
    
70.     for ( p_end = *pp_start; p_end->next != nullptr; p_end = p_end->next )
    
71.     {
    
72.         num_total++;
    
73.         if ( num_total % 2 == 0 ) p_middle = p_middle->next;
    
74.     }   
    
75. 
    
76.     // find out whether we are looking for only one or two median values
    
77.     enum LoopState loop_state = num_total % 2 == 0 ? LOOPSTATE_LOOKINGFORTWO : LOOPSTATE_LOOKINGFORONE;
    
78. 
    
79.     //set k to the index of the middle element, or if there are two middle elements, to the left one
    
80.     int k = ( num_total - 1 ) / 2;
    
81. 
    
82.     // If we are looking for two median values, but we have only found one, then this variable will
    
83.     // hold the value of the one we found. Whether we have found one can be determined by the state of
    
84.     // the variable loop_state.
    
85.     T val_found;
    
86. 
    
87.     for (;;)
    
88.     {
    
89.         assert( *pp_start != nullptr );
    
90.         assert( p_middle  != nullptr );
    
91.         assert( p_end     != nullptr );
    
92.         assert( num_total != 0 );
    
93. 
    
94.         if ( num_total == 1 )
    
95.         {
    
96.             switch ( loop_state )
    
97.             {
    
98.             case LOOPSTATE_LOOKINGFORONE:
    
99.                 return (*pp_start)->data;
    
100.             case LOOPSTATE_FOUNDONE:
     
101.                 return arithmetic_mean<T,U>( val_found, (*pp_start)->data );
     
102.             default:
     
103.                 assert( false ); //this should be unreachable
     
104.             }
     
105.         }
     
106. 
     
107.         //select the pivot according to the "median-of-three" rule
     
108.         T pivot;
     
109.         if ( (*pp_start)->data < p_middle->data )
     
110.         {
     
111.             if ( p_middle->data < p_end->data )
     
112.                 pivot = p_middle->data;
     
113.             else if ( (*pp_start)->data < p_end->data )
     
114.                 pivot = p_end->data;
     
115.             else
     
116.                 pivot = (*pp_start)->data;
     
117.         }
     
118.         else
     
119.         {
     
120.             if ( (*pp_start)->data < p_end->data )
     
121.                 pivot = (*pp_start)->data;
     
122.             else if ( p_middle->data < p_end->data )
     
123.                 pivot = p_end->data;
     
124.             else
     
125.                 pivot = p_middle->data;
     
126.         }
     
127. 
     
128. 
     
129.         // We will be dividing the current partition into 3 new partitions (less-than,
     
130.         // equal-to and greater-than) each represented as a linked list. Each list
     
131.         // requires a pointer to the start of the list and a pointer to the pointer at
     
132.         // the end of the list to write the address of new elements to. Also, when
     
133.         // traversing the lists, we need to keep a pointer to the middle of the list,
     
134.         // as this information will be required for selecting a new pivot in the next
     
135.         // iteration of the loop. The latter is not required for the equal-to partition,
     
136.         // as it would never be used.
     
137.         Node<T> *p_less    = nullptr, **pp_less_end    = &p_less,    **pp_less_middle    = &p_less;
     
138.         Node<T> *p_equal   = nullptr, **pp_equal_end   = &p_equal;
     
139.         Node<T> *p_greater = nullptr, **pp_greater_end = &p_greater, **pp_greater_middle = &p_greater;
     
140. 
     
141.         // These pointers are only used as a cache to the location of end node. Despite
     
142.         // their similar name, their function is very different to pp_less_end and
     
143.         // pp_greater_end.
     
144.         Node<T> *p_less_end    = nullptr;
     
145.         Node<T> *p_greater_end = nullptr;
     
146. 
     
147.         // counter for the number of elements in each partition
     
148.         int num_less = 0;
     
149.         int num_equal = 0;
     
150.         int num_greater = 0;
     
151. 
     
152.         // NOTE:
     
153.         // The following loop will temporarily split the linked list. It will be merged later.
     
154.         Node<T> *p_next_node = *pp_start;
     
155.         *pp_start = nullptr;
     
156.         for ( int a = 0; a < num_total; a++ )
     
157.         {
     
158.             assert( p_next_node != nullptr );
     
159. 
     
160.             Node<T> *p_current_node = p_next_node;
     
161.             p_next_node = p_next_node->next;
     
162. 
     
163.             if ( p_current_node->data < pivot )
     
164.             {
     
165.                 //link node to pp_less
     
166.                 assert( *pp_less_end == nullptr );
     
167.                 *pp_less_end = p_current_node;
     
168.                 pp_less_end = &p_current_node->next;
     
169.                 p_current_node->next = nullptr;
     
170. 
     
171.                 num_less++;
     
172.                 if ( num_less % 2 == 0 )
     
173.                 {
     
174.                     pp_less_middle = &(*pp_less_middle)->next;
     
175.                 }
     
176. 
     
177.                 //setting this variable is only done for caching purposes and is not
     
178.                 //directly related to the logic of the other variable pp_less_end
     
179.                 p_less_end = p_current_node;
     
180.             }
     
181.             else if ( p_current_node->data == pivot )
     
182.             {
     
183.                 //link node to pp_equal
     
184.                 assert( *pp_equal_end == nullptr );
     
185.                 *pp_equal_end = p_current_node;
     
186.                 pp_equal_end = &p_current_node->next;
     
187.                 p_current_node->next = nullptr;
     
188. 
     
189.                 num_equal++;
     
190.             }
     
191.             else
     
192.             {
     
193.                 //link node to pp_greater
     
194.                 assert( *pp_greater_end == nullptr );
     
195.                 *pp_greater_end = p_current_node;
     
196.                 pp_greater_end = &p_current_node->next;
     
197.                 p_current_node->next = nullptr;
     
198. 
     
199.                 num_greater++;
     
200.                 if ( num_greater % 2 == 0 )
     
201.                 {
     
202.                     pp_greater_middle = &(*pp_greater_middle)->next;
     
203.                 }
     
204. 
     
205.                 //setting this variable is only done for caching purposes and is not
     
206.                 //directly related to the logic of the other variable pp_greater_end
     
207.                 p_greater_end = p_current_node;
     
208.             }
     
209.         }
     
210. 
     
211.         assert( num_total == num_less + num_equal + num_greater );
     
212. 
     
213. #ifdef PRINT_DEBUG_INFO
     
214.         //when PRINT_DEBUG_INFO is defined, it will print the length of all partitions and their contents
     
215.         {
     
216.             Node<T> *p;
     
217.             std::cout << std::setfill( '0' );
     
218.             std::cout << "partition lengths: ";
     
219.             std::cout <<
     
220.                 std::setw( 2 ) << num_less    << " " <<
     
221.                 std::setw( 2 ) << num_equal   << " " <<
     
222.                 std::setw( 2 ) << num_greater << " " <<
     
223.                 std::setw( 2 ) << num_total   << "\n";
     
224.             std::cout << "less: ";
     
225.             for ( p = p_less; p != nullptr; p = p->next ) std::cout << p->data << " ";
     
226.             std::cout << "\nequal: ";
     
227.             for ( p = p_equal; p != nullptr; p = p->next ) std::cout << p->data << " ";
     
228.             std::cout << "\ngreater: ";
     
229.             for ( p = p_greater; p != nullptr; p = p->next ) std::cout << p->data << " ";
     
230.             std::cout << "\n\n" << std::flush;
     
231.         }
     
232. #endif
     
233. 
     
234.         //insert less-than partition into list
     
235.         assert( *pp_start == nullptr );
     
236.         *pp_start = p_less;
     
237. 
     
238.         //insert equal-to partition into list
     
239.         assert( *pp_less_end == nullptr );
     
240.         *pp_less_end = p_equal;
     
241. 
     
242.         //insert greater-than partition into list
     
243.         assert( *pp_equal_end == nullptr );
     
244.         *pp_equal_end = p_greater;
     
245. 
     
246.         //link list to previously cut off part
     
247.         assert( *pp_greater_end == nullptr );
     
248.         *pp_greater_end = p_next_node;
     
249. 
     
250.         //if less-than partition is large enough to hold both possible median values
     
251.         if ( k + 2 <= num_less )
     
252.         {
     
253.             //set the next iteration of the loop to process the less-than partition
     
254.             //pp_start is already set to the desired value
     
255.             p_middle = *pp_less_middle;
     
256.             p_end = p_less_end;
     
257.             num_total = num_less;
     
258.         }
     
259. 
     
260.         //else if less-than partition holds one of both possible median values
     
261.         else if ( k + 1 == num_less )
     
262.         {
     
263.             if ( loop_state == LOOPSTATE_LOOKINGFORTWO )
     
264.             {
     
265.                 //the equal_to partition never needs sorting, because all members are already equal
     
266.                 val_found = p_equal->data;
     
267.                 loop_state = LOOPSTATE_FOUNDONE;
     
268.             }
     
269.             //set the next iteration of the loop to process the less-than partition
     
270.             //pp_start is already set to the desired value
     
271.             p_middle = *pp_less_middle;
     
272.             p_end = p_less_end;
     
273.             num_total = num_less;
     
274.         }
     
275. 
     
276.         //else if equal-to partition holds both possible median values
     
277.         else if ( k + 2 <= num_less + num_equal )
     
278.         {
     
279.             //the equal_to partition never needs sorting, because all members are already equal
     
280.             if ( loop_state == LOOPSTATE_FOUNDONE )
     
281.                 return arithmetic_mean<T,U>( val_found, p_equal->data );
     
282.             return p_equal->data;
     
283.         }
     
284. 
     
285.         //else if equal-to partition holds one of both possible median values
     
286.         else if ( k + 1 == num_less + num_equal )
     
287.         {
     
288.             switch ( loop_state )
     
289.             {
     
290.             case LOOPSTATE_LOOKINGFORONE:
     
291.                 return p_equal->data;
     
292.             case LOOPSTATE_LOOKINGFORTWO:
     
293.                 val_found = p_equal->data;
     
294.                 loop_state = LOOPSTATE_FOUNDONE;
     
295.                 k = 0;
     
296.                 //set the next iteration of the loop to process the greater-than partition
     
297.                 pp_start = pp_equal_end;
     
298.                 p_middle = *pp_greater_middle;
     
299.                 p_end = p_greater_end;
     
300.                 num_total = num_greater;
     
301.                 break;
     
302.             case LOOPSTATE_FOUNDONE:
     
303.                 return arithmetic_mean<T,U>( val_found, p_equal->data );
     
304.             }
     
305.         }
     
306. 
     
307.         //else both possible median values must be in the greater-than partition
     
308.         else
     
309.         {
     
310.             k = k - num_less - num_equal;
     
311. 
     
312.             //set the next iteration of the loop to process the greater-than partition
     
313.             pp_start = pp_equal_end;
     
314.             p_middle = *pp_greater_middle;
     
315.             p_end = p_greater_end;
     
316.             num_total = num_greater;
     
317.         }
     
318.     }
     
319. }
     
320. 
     
321. 
     
322. // NOTE:
     
323. // The following code is not part of the algorithm, but is only intended to test the algorithm
     
324. 
     
325. template <typename T>
     
326. class List
     
327. {
     
328. public:
     
329.     List() : first( nullptr ) {}
     
330. 
     
331.     // the following is required to abide by the rule of three/five/zero
     
332.     // see: https://en.cppreference.com/w/cpp/language/rule_of_three
     
333.     List( const List<T> & ) = delete;
     
334.     List( const List<T> && ) = delete;
     
335.     List<T>& operator=( List<T> & ) = delete;
     
336.     List<T>& operator=( List<T> && ) = delete;
     
337. 
     
338.     ~List()
     
339.     {
     
340.         Node<T> *p = first;
     
341. 
     
342.         while ( p != nullptr )
     
343.         {
     
344.             Node<T> *temp = p;
     
345.             p = p->next;
     
346.             delete temp;
     
347.         }
     
348.     }
     
349. 
     
350.     void push_front( int data )
     
351.     {
     
352.         Node<T>* tmp = new Node<T>;
     
353. 
     
354.         tmp->data = data;
     
355. 
     
356.         tmp->next = first;
     
357.         first = tmp;
     
358.     }
     
359. 
     
360.     //member variables
     
361.     Node<T> *first;
     
362. };
     
363. 
     
364. int main()
     
365. {
     
366.     List<int> l;
     
367. 
     
368.     int unsorted_data[] = { 6, 19, 3, 7, 4, 9, 8, 2, 18, 4, 10, 11, 12, 10 };
     
369. 
     
370.     //create singly-linked list
     
371.     for ( int i = 0; i < sizeof( unsorted_data ) / sizeof( *unsorted_data ); i++ ) l.push_front( unsorted_data[i] );
     
372. 
     
373.     std::cout << "The median is: " << std::setprecision(10) << find_median<int,double>( l.first ) << std::endl;
     
374. 
     
375.     return 0;
     
376. }

复制代码

我已经用一百万个随机生成的元素成功地测试了我的代码，它几乎立即找到了正确的中位数。

问题
我需要一种算法，它可以找到具有线性时间复杂度 O(n) 和恒定空间复杂度 O(1) 的单链表的中位数。

编辑：单链表是 C 风格的单链表。不允许使用 stl（没有容器，没有函数，禁止所有 stl，例如没有 std::forward_list）。不允许在任何其他容器（例如数组）中移动数字。

O(logn) 的空间复杂度是可以接受的，因为我的列表实际上小于 100。另外，我不允许使用像 nth_element 这样的 STL 函数

基本上，我有一个包含 3*10^6 元素的链表，我需要在 3 秒内得到中位数，所以我不能用排序算法对列表进行排序（它会是 O(nlogn)，它可能需要 10-14 秒）。

我在网上做了一些搜索，发现 std::vector 与 quickselect 的中位数可以在 O(n) 和 O(1) 空间中找到（最坏的情况是 O(n^2)，但很少看到），例如：

但是我找不到任何算法来为链表执行此操作。问题是，我可以使用数组索引随机访问向量，如果我想修改算法，复杂度会大得多，因为。例如，当我将枢轴索引更改为左时，我实际上需要遍历列表以获取新元素并走得更远（这将使我的列表至少 O(k n) 和一个大 k，甚至 O(n^ 2)…)。

编辑2：

我知道我有太多变量，但我一直在测试不同的东西，我仍然在我的代码中。 . .

我当前的代码：

1. #include <bits/stdc++.h>
   
2. 
   
3. using namespace std;
   
4. 
   
5. template <class T> class Node {
   
6.     public:
   
7.     T data;
   
8.     Node<T> *next;
   
9. };
   
10. 
    
11. template <class T> class List {
    
12.     public:
    
13.     Node<T> *first;
    
14. };
    
15. 
    
16. template <class T> T getMedianValue(List<T> & l) {
    
17.     Node<T> *crt,*pivot,*incpivot;
    
18.     int left, right, lung, idx, lungrel,lungrel2, left2, right2, aux, offset;
    
19.     pivot = l.first;
    
20.     crt = pivot->next;
    
21.     lung = 1;
    
22. //lung is the lenght of the linked list (yeah it's lenght in romanian...)
    
23. //lungrel and lungrel2 are the relative lenghts of the part of
    
24. //the list I am processing, e.g: 2 3 4 in a list with 1 2 3 4 5
    
25.     right = left = 0;
    
26.     while (crt != NULL) {
    
27.         if(crt->data < pivot->data){
    
28.             aux = pivot->data;
    
29.             pivot->data = crt->data;
    
30.             crt->data = pivot->next->data;
    
31.             pivot->next->data = aux;
    
32.             pivot = pivot->next;
    
33.             left++;
    
34.         }
    
35.         else right++;
    
36.        // cout<<crt->data<<endl;
    
37.         crt = crt->next;
    
38.         lung++;
    
39.     }
    
40.     if(right > left) offset = left;
    
41. //  cout<<endl;
    
42. //  cout<<pivot->data<<" "<<left<<" "<<right<<endl;
    
43. //  printList(l);
    
44. //  cout<<endl;
    
45.     lungrel = lung;
    
46.     incpivot = l.first;
    
47.    // offset = 0;
    
48.     while(left != right){
    
49.         //cout<<"parcurgere"<<endl;
    
50.         if(left > right){
    
51.             //cout<<endl;
    
52.             //printList(l);
    
53.             //cout<<endl;
    
54.             //cout<<"testleft "<<incpivot->data<<" "<<left<<" "<<right<<endl;
    
55.             crt = incpivot->next;
    
56.             pivot = incpivot;
    
57.             idx = offset;left2 = right2 = lungrel = 0;
    
58.             //cout<<idx<<endl;
    
59.             while(idx < left && crt!=NULL){
    
60.                  if(pivot->data > crt->data){
    
61.                    //  cout<<"1crt "<<crt->data<<endl;
    
62.                      aux = pivot->data;
    
63.                      pivot->data = crt->data;
    
64.                      crt->data = pivot->next->data;
    
65.                      pivot->next->data = aux;
    
66.                      pivot = pivot->next;
    
67.                      left2++;lungrel++;
    
68.                   }
    
69.                   else {
    
70.                       right2++;lungrel++;
    
71.                       //cout<<crt->data<<" "<<right2<<endl;
    
72.                   }
    
73.                   //cout<<crt->data<<endl;
    
74.                   crt = crt->next;
    
75.                   idx++;
    
76.              }
    
77.              left = left2 + offset;
    
78.              right = lung - left - 1;
    
79.              if(right > left) offset = left;
    
80.              //if(pivot->data == 18) return 18;
    
81.              //cout<<endl;
    
82.              //cout<<"l "<<pivot->data<<" "<<left<<" "<<right<<" "<<right2<<endl;
    
83.            //  printList(l);
    
84.         }
    
85.         else if(left < right && pivot->next!=NULL){
    
86.             idx = left;left2 = right2 = 0;
    
87.             incpivot = pivot->next;offset++;left++;
    
88.             //cout<<endl;
    
89.             //printList(l);
    
90.             //cout<<endl;
    
91.             //cout<<"testright "<<incpivot->data<<" "<<left<<" "<<right<<endl;
    
92.             pivot = pivot->next;
    
93.             crt = pivot->next;
    
94.             lungrel2 = lungrel;
    
95.             lungrel = 0;
    
96.            // cout<<"p right"<<pivot->data<<" "<<left<<" "<<right<<endl;
    
97.             while((idx < lungrel2 + offset - 1) && crt!=NULL){
    
98.                  if(crt->data < pivot->data){
    
99.                 //     cout<<"crt "<<crt->data<<endl;
    
100.                      aux = pivot->data;
     
101.                      pivot->data = crt->data;
     
102.                      crt->data = (pivot->next)->data;
     
103.                      (pivot->next)->data = aux;
     
104.                      pivot = pivot->next;
     
105.                  //    cout<<"crt2 "<<crt->data<<endl;
     
106.                      left2++;lungrel++;
     
107.                   }
     
108.                   else right2++;lungrel++;
     
109.                   //cout<<crt->data<<endl;
     
110.                   crt = crt->next;
     
111.                   idx++;
     
112.              }
     
113.              left = left2 + left;
     
114.              right = lung - left - 1;
     
115.                  if(right > left) offset = left;
     
116.             // cout<<"r "<<pivot->data<<" "<<left<<" "<<right<<endl;
     
117.            //  printList(l);
     
118.         }
     
119.         else{
     
120.             //cout<<cmx<<endl;
     
121.             return pivot->data;
     
122.         }
     
123.     }
     
124.     //cout<<cmx<<endl;
     
125.     return pivot->data;
     
126. }
     
127. template <class T> void printList(List<T> const & l) {
     
128.     Node<T> *tmp;
     
129.     if(l.first != NULL){
     
130.         tmp = l.first;
     
131.         while(tmp != NULL){
     
132.             cout<<tmp->data<<" ";
     
133.             tmp = tmp->next;
     
134.         }
     
135.     }
     
136. }
     
137. template <class T> void push_front(List<T> & l, int x)
     
138. {
     
139.     Node<T>* tmp = new Node<T>;
     
140. 
     
141.     tmp->data = x;
     
142. 
     
143.     tmp->next = l.first;
     
144.     l.first = tmp;
     
145. }
     
146. 
     
147. int main(){
     
148.     List<int> l;
     
149.     int n = 0;
     
150.     push_front(l, 19);
     
151.     push_front(l, 12);
     
152.     push_front(l, 11);
     
153.     push_front(l, 101);
     
154.     push_front(l, 91);
     
155.     push_front(l, 21);
     
156.     push_front(l, 9);
     
157.     push_front(l, 6);
     
158.     push_front(l, 25);
     
159.     push_front(l, 4);
     
160.     push_front(l, 18);
     
161.     push_front(l, 2);
     
162.     push_front(l, 8);
     
163.     push_front(l, 10);
     
164.     push_front(l, 200);
     
165.     push_front(l, 225);
     
166.     push_front(l, 170);
     
167.     printList(l);
     
168.     n=getMedianValue(l);
     
169.     cout<<endl;
     
170.     cout<<n;
     
171. 
     
172.     return 0;
     
173. }

复制代码

您对如何使快速选择适应单独列出的链接或其他可以解决我的问题的算法有任何建议吗？

回答
在您的问题中，您提到将枢轴点向左移动时遇到问题，因为这需要遍历列表。如果你做对了，你只需要遍历整个列表两次：

如果你不太在意选择一个好的枢轴，只是喜欢选择列表中的第一个元素作为枢轴（如果数据已经排序，这将导致最坏情况 O(n^ 2）时间复杂度），不需要第一步。

如果第一次遍历链表的尾端，通过保持指向链表尾的指针，就不必再次遍历它来找到尾了。此外，如果您使用标准 Lomuto 分区方案（我不这样做，原因如下所述），您还必须在列表中保留两个指针，表示标准 Lomuto 分区方案的 i 和 j 索引.通过使用这些指针，您永远不必遍历列表来访问单个元素。

此外，如果您保留一个指向每个分区的中间和结尾的指针，那么当您稍后必须对其中一个分区进行排序时，您不必再次遍历该分区来找到中间和结尾。

我现在已经为链表创建了我自己的 QuickSelect 算法实现，我已经在下面发布了。

既然你说链表是单链表，不能升级成双链表，那我就不能用Hoare分区方案了，因为反向迭代单链表代价很大。所以我正在使用通常效率较低的 Lomuto 分区方案。

在使用 Lomuto 分区方案时，通常选择第一个元素或最后一个元素作为轴。然而，选择这两种方法中的任何一种都有一个缺点，即排序数据将导致算法的最坏情况时间复杂度为 O(n^2)。这可以通过根据“三的中值”选择轴来防止。规则，即从第一个元素、中间元素和最后一个元素的中值中选择轴。所以在我的实现中，我使用这个“三位数”。规则。

此外，Lomuto 分区方案通常会创建两个分区，一个用于小于轴的值，一个用于大于或等于轴的值。但是，如果所有值都相同，这将导致 O(n^2) 的最坏情况时间复杂度。所以，在我的实现中，我创建了三个分区，一个用于小于轴的值，一个用于大于轴的值，一个用于等于轴的值。

虽然这些措施并没有完全消除 O(n^2) 的最坏情况时间复杂度的可能性，但它们至少使其极不可能发生。

我遇到的一个重要问题是，对于偶数个元素，中位数被定义为两个“中间”元素的算术平均值。或“中间”元素。所以我不能简单地调用函数 find_nth_element 因为例如，如果元素的总数是 14，那么我将寻找第 7 和第 8 个最大的元素。这意味着我将不得不两次调用这样的函数，这将是低效的。所以我写了一个搜索“中位数”的函数。同时元素。尽管这使代码更加复杂，但与不必调用相同函数两次的优势相比，由于额外代码复杂性导致的性能损失应该是最小的。

请注意，虽然我的实现完全在 C++ 编译器上编译，但我不会将其称为教科书 C++ 代码，因为它禁止使用 C++ 标准模板库中的任何内容。所以我的代码是 C 代码和 C++ 代码的混合体。

1. #include <iostream>
   
2. #include <iomanip>
   
3. #include <cassert>
   
4. 
   
5. //remove the comment in the following line for extra debugging information
   
6. //#define PRINT_DEBUG_INFO
   
7. 
   
8. template <typename T>
   
9. struct Node
   
10. {
    
11.     T data;
    
12.     Node<T> *next;
    
13. };
    
14. 
    
15. // NOTE:
    
16. // The return type is not necessarily the same as the data type. The reason for this is
    
17. // that, for example, the data type "int" requires a "double" as a return type, so that
    
18. // the arithmetic mean of "3" and "6" returns "4.5".
    
19. // This function may require template specializations to handle overflow or wrapping.
    
20. template<typename T, typename U>
    
21. U arithmetic_mean( const T &first, const T &second )
    
22. {
    
23.     return ( static_cast<U>(first) + static_cast<U>(second) ) / 2;
    
24. }
    
25. 
    
26. //the main loop of the function find_median can be in one of the following three states
    
27. enum LoopState
    
28. {
    
29.     //we are looking for one median value
    
30.     LOOPSTATE_LOOKINGFORONE,
    
31. 
    
32.     //we are looking for two median values, and the returned median
    
33.     //will be the arithmetic mean of the two
    
34.     LOOPSTATE_LOOKINGFORTWO,
    
35. 
    
36.     //one of the median values has been found, but we are still searching for
    
37.     //the second one
    
38.     LOOPSTATE_FOUNDONE
    
39. };
    
40. 
    
41. template <
    
42.     typename T, //type of the data
    
43.     typename U  //type of the return value
    
44. >
    
45. U find_median( Node<T> *list )
    
46. {
    
47.     //This variable points to the pointer to the first element of the current partition.
    
48.     //During the partition phase, the linked list will be broken and reassembled afterwards, so
    
49.     //the pointer this pointer points to will be nullptr until it is reassembled.
    
50.     Node<T> **pp_start = &list;
    
51. 
    
52.     //these pointer are maintained for accessing the middle of the list for selecting a pivot using
    
53.     //the "median-of-three" rule
    
54.     Node<T> *p_middle;
    
55.     Node<T> *p_end;
    
56. 
    
57.     //result is not defined if list is empty
    
58.     assert( *pp_start != nullptr );
    
59. 
    
60.     //in the main loop, this variable always holds the number of elements in the current partition
    
61.     int num_total = 1;
    
62. 
    
63.     // First, we must traverse the entire linked list in order to determine the number of elements,
    
64.     // in order to calculate k1 and k2. If it is odd, then the median is defined as the k'th smallest
    
65.     // element where k = n / 2. If the number of elements is even, then the median is defined as the
    
66.     // arithmetic mean of the k'th element and the (k+1)'th element.
    
67.     // We also set a pointer to the nodes in the middle and at the end, which will be required later
    
68.     // for selecting a pivot according to the "median-of-three" rule.
    
69.     p_middle = *pp_start;
    
70.     for ( p_end = *pp_start; p_end->next != nullptr; p_end = p_end->next )
    
71.     {
    
72.         num_total++;
    
73.         if ( num_total % 2 == 0 ) p_middle = p_middle->next;
    
74.     }   
    
75. 
    
76.     // find out whether we are looking for only one or two median values
    
77.     enum LoopState loop_state = num_total % 2 == 0 ? LOOPSTATE_LOOKINGFORTWO : LOOPSTATE_LOOKINGFORONE;
    
78. 
    
79.     //set k to the index of the middle element, or if there are two middle elements, to the left one
    
80.     int k = ( num_total - 1 ) / 2;
    
81. 
    
82.     // If we are looking for two median values, but we have only found one, then this variable will
    
83.     // hold the value of the one we found. Whether we have found one can be determined by the state of
    
84.     // the variable loop_state.
    
85.     T val_found;
    
86. 
    
87.     for (;;)
    
88.     {
    
89.         assert( *pp_start != nullptr );
    
90.         assert( p_middle  != nullptr );
    
91.         assert( p_end     != nullptr );
    
92.         assert( num_total != 0 );
    
93. 
    
94.         if ( num_total == 1 )
    
95.         {
    
96.             switch ( loop_state )
    
97.             {
    
98.             case LOOPSTATE_LOOKINGFORONE:
    
99.                 return (*pp_start)->data;
    
100.             case LOOPSTATE_FOUNDONE:
     
101.                 return arithmetic_mean<T,U>( val_found, (*pp_start)->data );
     
102.             default:
     
103.                 assert( false ); //this should be unreachable
     
104.             }
     
105.         }
     
106. 
     
107.         //select the pivot according to the "median-of-three" rule
     
108.         T pivot;
     
109.         if ( (*pp_start)->data < p_middle->data )
     
110.         {
     
111.             if ( p_middle->data < p_end->data )
     
112.                 pivot = p_middle->data;
     
113.             else if ( (*pp_start)->data < p_end->data )
     
114.                 pivot = p_end->data;
     
115.             else
     
116.                 pivot = (*pp_start)->data;
     
117.         }
     
118.         else
     
119.         {
     
120.             if ( (*pp_start)->data < p_end->data )
     
121.                 pivot = (*pp_start)->data;
     
122.             else if ( p_middle->data < p_end->data )
     
123.                 pivot = p_end->data;
     
124.             else
     
125.                 pivot = p_middle->data;
     
126.         }
     
127. 
     
128. 
     
129.         // We will be dividing the current partition into 3 new partitions (less-than,
     
130.         // equal-to and greater-than) each represented as a linked list. Each list
     
131.         // requires a pointer to the start of the list and a pointer to the pointer at
     
132.         // the end of the list to write the address of new elements to. Also, when
     
133.         // traversing the lists, we need to keep a pointer to the middle of the list,
     
134.         // as this information will be required for selecting a new pivot in the next
     
135.         // iteration of the loop. The latter is not required for the equal-to partition,
     
136.         // as it would never be used.
     
137.         Node<T> *p_less    = nullptr, **pp_less_end    = &p_less,    **pp_less_middle    = &p_less;
     
138.         Node<T> *p_equal   = nullptr, **pp_equal_end   = &p_equal;
     
139.         Node<T> *p_greater = nullptr, **pp_greater_end = &p_greater, **pp_greater_middle = &p_greater;
     
140. 
     
141.         // These pointers are only used as a cache to the location of end node. Despite
     
142.         // their similar name, their function is very different to pp_less_end and
     
143.         // pp_greater_end.
     
144.         Node<T> *p_less_end    = nullptr;
     
145.         Node<T> *p_greater_end = nullptr;
     
146. 
     
147.         // counter for the number of elements in each partition
     
148.         int num_less = 0;
     
149.         int num_equal = 0;
     
150.         int num_greater = 0;
     
151. 
     
152.         // NOTE:
     
153.         // The following loop will temporarily split the linked list. It will be merged later.
     
154.         Node<T> *p_next_node = *pp_start;
     
155.         *pp_start = nullptr;
     
156.         for ( int a = 0; a < num_total; a++ )
     
157.         {
     
158.             assert( p_next_node != nullptr );
     
159. 
     
160.             Node<T> *p_current_node = p_next_node;
     
161.             p_next_node = p_next_node->next;
     
162. 
     
163.             if ( p_current_node->data < pivot )
     
164.             {
     
165.                 //link node to pp_less
     
166.                 assert( *pp_less_end == nullptr );
     
167.                 *pp_less_end = p_current_node;
     
168.                 pp_less_end = &p_current_node->next;
     
169.                 p_current_node->next = nullptr;
     
170. 
     
171.                 num_less++;
     
172.                 if ( num_less % 2 == 0 )
     
173.                 {
     
174.                     pp_less_middle = &(*pp_less_middle)->next;
     
175.                 }
     
176. 
     
177.                 //setting this variable is only done for caching purposes and is not
     
178.                 //directly related to the logic of the other variable pp_less_end
     
179.                 p_less_end = p_current_node;
     
180.             }
     
181.             else if ( p_current_node->data == pivot )
     
182.             {
     
183.                 //link node to pp_equal
     
184.                 assert( *pp_equal_end == nullptr );
     
185.                 *pp_equal_end = p_current_node;
     
186.                 pp_equal_end = &p_current_node->next;
     
187.                 p_current_node->next = nullptr;
     
188. 
     
189.                 num_equal++;
     
190.             }
     
191.             else
     
192.             {
     
193.                 //link node to pp_greater
     
194.                 assert( *pp_greater_end == nullptr );
     
195.                 *pp_greater_end = p_current_node;
     
196.                 pp_greater_end = &p_current_node->next;
     
197.                 p_current_node->next = nullptr;
     
198. 
     
199.                 num_greater++;
     
200.                 if ( num_greater % 2 == 0 )
     
201.                 {
     
202.                     pp_greater_middle = &(*pp_greater_middle)->next;
     
203.                 }
     
204. 
     
205.                 //setting this variable is only done for caching purposes and is not
     
206.                 //directly related to the logic of the other variable pp_greater_end
     
207.                 p_greater_end = p_current_node;
     
208.             }
     
209.         }
     
210. 
     
211.         assert( num_total == num_less + num_equal + num_greater );
     
212. 
     
213. #ifdef PRINT_DEBUG_INFO
     
214.         //when PRINT_DEBUG_INFO is defined, it will print the length of all partitions and their contents
     
215.         {
     
216.             Node<T> *p;
     
217.             std::cout << std::setfill( '0' );
     
218.             std::cout << "partition lengths: ";
     
219.             std::cout <<
     
220.                 std::setw( 2 ) << num_less    << " " <<
     
221.                 std::setw( 2 ) << num_equal   << " " <<
     
222.                 std::setw( 2 ) << num_greater << " " <<
     
223.                 std::setw( 2 ) << num_total   << "\n";
     
224.             std::cout << "less: ";
     
225.             for ( p = p_less; p != nullptr; p = p->next ) std::cout << p->data << " ";
     
226.             std::cout << "\nequal: ";
     
227.             for ( p = p_equal; p != nullptr; p = p->next ) std::cout << p->data << " ";
     
228.             std::cout << "\ngreater: ";
     
229.             for ( p = p_greater; p != nullptr; p = p->next ) std::cout << p->data << " ";
     
230.             std::cout << "\n\n" << std::flush;
     
231.         }
     
232. #endif
     
233. 
     
234.         //insert less-than partition into list
     
235.         assert( *pp_start == nullptr );
     
236.         *pp_start = p_less;
     
237. 
     
238.         //insert equal-to partition into list
     
239.         assert( *pp_less_end == nullptr );
     
240.         *pp_less_end = p_equal;
     
241. 
     
242.         //insert greater-than partition into list
     
243.         assert( *pp_equal_end == nullptr );
     
244.         *pp_equal_end = p_greater;
     
245. 
     
246.         //link list to previously cut off part
     
247.         assert( *pp_greater_end == nullptr );
     
248.         *pp_greater_end = p_next_node;
     
249. 
     
250.         //if less-than partition is large enough to hold both possible median values
     
251.         if ( k + 2 <= num_less )
     
252.         {
     
253.             //set the next iteration of the loop to process the less-than partition
     
254.             //pp_start is already set to the desired value
     
255.             p_middle = *pp_less_middle;
     
256.             p_end = p_less_end;
     
257.             num_total = num_less;
     
258.         }
     
259. 
     
260.         //else if less-than partition holds one of both possible median values
     
261.         else if ( k + 1 == num_less )
     
262.         {
     
263.             if ( loop_state == LOOPSTATE_LOOKINGFORTWO )
     
264.             {
     
265.                 //the equal_to partition never needs sorting, because all members are already equal
     
266.                 val_found = p_equal->data;
     
267.                 loop_state = LOOPSTATE_FOUNDONE;
     
268.             }
     
269.             //set the next iteration of the loop to process the less-than partition
     
270.             //pp_start is already set to the desired value
     
271.             p_middle = *pp_less_middle;
     
272.             p_end = p_less_end;
     
273.             num_total = num_less;
     
274.         }
     
275. 
     
276.         //else if equal-to partition holds both possible median values
     
277.         else if ( k + 2 <= num_less + num_equal )
     
278.         {
     
279.             //the equal_to partition never needs sorting, because all members are already equal
     
280.             if ( loop_state == LOOPSTATE_FOUNDONE )
     
281.                 return arithmetic_mean<T,U>( val_found, p_equal->data );
     
282.             return p_equal->data;
     
283.         }
     
284. 
     
285.         //else if equal-to partition holds one of both possible median values
     
286.         else if ( k + 1 == num_less + num_equal )
     
287.         {
     
288.             switch ( loop_state )
     
289.             {
     
290.             case LOOPSTATE_LOOKINGFORONE:
     
291.                 return p_equal->data;
     
292.             case LOOPSTATE_LOOKINGFORTWO:
     
293.                 val_found = p_equal->data;
     
294.                 loop_state = LOOPSTATE_FOUNDONE;
     
295.                 k = 0;
     
296.                 //set the next iteration of the loop to process the greater-than partition
     
297.                 pp_start = pp_equal_end;
     
298.                 p_middle = *pp_greater_middle;
     
299.                 p_end = p_greater_end;
     
300.                 num_total = num_greater;
     
301.                 break;
     
302.             case LOOPSTATE_FOUNDONE:
     
303.                 return arithmetic_mean<T,U>( val_found, p_equal->data );
     
304.             }
     
305.         }
     
306. 
     
307.         //else both possible median values must be in the greater-than partition
     
308.         else
     
309.         {
     
310.             k = k - num_less - num_equal;
     
311. 
     
312.             //set the next iteration of the loop to process the greater-than partition
     
313.             pp_start = pp_equal_end;
     
314.             p_middle = *pp_greater_middle;
     
315.             p_end = p_greater_end;
     
316.             num_total = num_greater;
     
317.         }
     
318.     }
     
319. }
     
320. 
     
321. 
     
322. // NOTE:
     
323. // The following code is not part of the algorithm, but is only intended to test the algorithm
     
324. 
     
325. template <typename T>
     
326. class List
     
327. {
     
328. public:
     
329.     List() : first( nullptr ) {}
     
330. 
     
331.     // the following is required to abide by the rule of three/five/zero
     
332.     // see: https://en.cppreference.com/w/cpp/language/rule_of_three
     
333.     List( const List<T> & ) = delete;
     
334.     List( const List<T> && ) = delete;
     
335.     List<T>& operator=( List<T> & ) = delete;
     
336.     List<T>& operator=( List<T> && ) = delete;
     
337. 
     
338.     ~List()
     
339.     {
     
340.         Node<T> *p = first;
     
341. 
     
342.         while ( p != nullptr )
     
343.         {
     
344.             Node<T> *temp = p;
     
345.             p = p->next;
     
346.             delete temp;
     
347.         }
     
348.     }
     
349. 
     
350.     void push_front( int data )
     
351.     {
     
352.         Node<T>* tmp = new Node<T>;
     
353. 
     
354.         tmp->data = data;
     
355. 
     
356.         tmp->next = first;
     
357.         first = tmp;
     
358.     }
     
359. 
     
360.     //member variables
     
361.     Node<T> *first;
     
362. };
     
363. 
     
364. int main()
     
365. {
     
366.     List<int> l;
     
367. 
     
368.     int unsorted_data[] = { 6, 19, 3, 7, 4, 9, 8, 2, 18, 4, 10, 11, 12, 10 };
     
369. 
     
370.     //create singly-linked list
     
371.     for ( int i = 0; i < sizeof( unsorted_data ) / sizeof( *unsorted_data ); i++ ) l.push_front( unsorted_data[i] );
     
372. 
     
373.     std::cout << "The median is: " << std::setprecision(10) << find_median<int,double>( l.first ) << std::endl;
     
374. 
     
375.     return 0;
     
376. }

复制代码

我已经用一百万个随机生成的元素成功地测试了我的代码，它几乎立即找到了正确的中位数。