学步园

在快排的基础上进行算法实现，只是每次分区之后只选择第i大的元素所在的区域进行查找。平均算法复杂度为O(n)，最差算法复杂度为O(n^2)，如同快排一样，出现最差情况的概率极低。

#ifndef RANDOMSELECT_H<br /> #define RANDOMSELECT_H<br /> #include <iostream></p> <p>/**<br /> * @brief Exception class which means that i is larger than the number of elements in the array<br /> */<br /> class OutOfRange<br /> {<br /> public:<br /> OutOfRange(){}<br /> OutOfRange(std::string mes);<br /> OutOfRange(OutOfRange &a);<br /> ~OutOfRange(){}<br /> std::string Message() const;<br /> private:<br /> std::string message;<br /> };<br /> OutOfRange::OutOfRange(std::string mes): message(mes)<br /> {<br /> }<br /> OutOfRange::OutOfRange(OutOfRange &a)<br /> {<br /> message = a.Message();<br /> }<br /> std::string OutOfRange::Message() const<br /> {<br /> return message;<br /> }<br /> /**<br /> * @brief Partition the array<br /> *<br /> * @tparam T: template type<br /> * @param array: the array to be partitioned<br /> * @param start: the start position of the array<br /> * @param end: the index of the last element in the array<br /> *<br /> * @return The partition position<br /> */<br /> template <typename T><br /> int Partition(T *array, int start, int end)<br /> {<br /> T x = array[end];<br /> int i = start;<br /> int j = end - 1;<br /> //i is to find the element who is larger than array[end]<br /> //j is to find the element who is smaller than array[end]<br /> while (i <= j)<br /> {<br /> if (array[i] <= x)<br /> {<br /> ++i;<br /> }<br /> else<br /> {<br /> while (i <= j)<br /> {<br /> if (array[j] > x)<br /> {<br /> --j;<br /> }<br /> else<br /> {<br /> //swap element at i and j<br /> T temp = array[i];<br /> array[i++] = array[j];<br /> array[j--] = temp;<br /> break;<br /> }<br /> }<br /> }<br /> }<br /> //i will be the first element who is larger than array[end] after arrange the array<br /> //if there is no element larger than array[end], i will point to array[end]<br /> T temp = array[i];<br /> array[i] = x;<br /> array[end] = temp;<br /> return i;<br /> }<br /> /**<br /> * @brief Get the i'th element in the array. The badest complexity is O(n^2), the average complexity is O(n).<br /> *<br /> * @tparam V: template type<br /> * @param array: the array to be searched<br /> * @param start: the start position of the array<br /> * @param end: the index of the last element in the array<br /> * @param i: find the i'th element<br /> *<br /> * @return the i'th element<br /> */<br /> template <typename V><br /> V RandomSelect(V *array, int start, int end, int i)<br /> {<br /> if (i + start > end + 1)<br /> {<br /> OutOfRange a("ERROE: i is larger than the number of elements in the array!");<br /> throw a;<br /> }<br /> if (start == end)<br /> {<br /> return array[start];<br /> }<br /> int p = Partition(array, start, end);<br /> //k means the order of p in the array<br /> int k = p + 1 - start;<br /> if (i == k)<br /> {<br /> return array[p];<br /> }<br /> if (i < k)<br /> {<br /> return RandomSelect(array, start, p - 1, i);<br /> }<br /> else<br /> {<br /> return RandomSelect(array, p + 1, end, i - k);<br /> }<br /> }<br /> #endif /* end of include guard: RANDOMSELECT_H */<br />