**Medians and Order Statistics**

------

**Overview**

Order Statistics:

Order statistics, that is ranked the number to find out n bits in the number of i, denoted by ith

Medians:

The median in the middle is the number of

------

**Medians values**

Assuming all the numbers are not the same, then:

n = odd, only an intermediate number, i = (n +1) / 2,

n = even, there are two middle numbers, i = n / 2 and i = n / 2 + 1,

Can be combined as:

i =

lower ((n + 1) / 2),

upper ((n + 1) / 2),

For the odd 2 are the same as those for even 2 different

------

**Maximum & minimum**

By n-1 comparisons to find the maximum or minimum value,

If you want to find two persons, you can merge and let the number of comparisons is less than 2 * (n-1), because if a small number of the number than the other one, the number certainly not the maximum, and vice versa,

------

**Order to find - each division 2 group achieved**

Overview:

Achieved by separating the function to find,

Efficiency:

Complexity: the expected efficiency is O (n)

Space complexity: O (n)

Ideas:

Quicksort-based transformation, but each time taking only half of them, thus reducing efficiency to O (n),

The logic of separating the function:

* Take-separated values,

* If separated value is the target, then ok

* If the array is separated by about 2,

* Determine the number of targets within the array in which to retain the array, separated by their function call loop

*

Time complexity of proof:

Strategy, see <Introduction to Algorithms> chp9.2

------

**Order to find - each division to achieve 5**

More complex, the worst-case time complexity is O (n),

References: <Introduction to Algorithms> chp9.3

------

**Example:**

**(Sequence number to find - each division 2 group achieved)**

* Js (order_statistic.js)

var arr_order_statistic = [ 78, 13, 6, 177, 26, 90, 288, 45, 62, 83 ]; /** * <p> * order statistic , I find the value of the order of * </p> * <b> Ideas :</b><br /> * Transformation based on quicksort , But each time only to take one of the half, down to the efficiency of O(n),<br /> * * <pre> * The logic of separating the function : * Separated values obtained , * If the target value is separated, then ok * Otherwise, the array is separated About 2 , * Determine the number of targets within the array in which to retain the array , Separate function calls to their circulation * </pre> * * <b> Time complexity :</b>O(n)<br /> * <b> Space complexity :</b>O(n)<br /> * * @author kuchaguangjie * @date 2011 In January 3 Date * @return */ function OrderStatistic(inputArr) { this.inputArr = inputArr; } /** * Separated by a single * * @param arr * @param i * The order in arr , From 0 * @return There are sub-array or target Target */ OrderStatistic.prototype.partitionSingle = function(arr, i) { if (arr.length <= 1) { // length == 1 Situation, length == 0 should be excluded in the upper function , return new OrderStaticResult(true, undefined, undefined, arr[0]); } var partLeftArr = []; var partRightArr = []; var partMiddle = arr[arr.length - 1]; // Finally, an element , Separated values for for ( var x = 0; x < arr.length - 1; x++) { if (arr[x] <= partMiddle) { partLeftArr[partLeftArr.length] = arr[x]; } else { partRightArr[partRightArr.length] = arr[x]; } } if (partLeftArr.length == i) { // Separated values is Target return new OrderStaticResult(true, undefined, undefined, partMiddle); } else if (partLeftArr.length > i) { // Target in Left subarray return new OrderStaticResult(false, partLeftArr, i); } else { // Target in The right sub-array i -= (partLeftArr.length + 1); // Adjustment i return new OrderStaticResult(false, partRightArr, i); } }; /** * Separate function, to find the target worth value * * @param i * @return */ OrderStatistic.prototype.partition = function(i) { var arr = this.inputArr; var osr; while (true) { osr = this.partitionSingle(arr, i); if (osr.ok) { return osr.v; } else { arr = osr.subArr; i = osr.i; } } }; /** * According to order No. Find several * * @param order * Order number, from the 1 Start * @return */ OrderStatistic.prototype.getByOrder = function(order) { if (this.inputArr.length == 0 || this.inputArr.length < order) { alert(' Entered incorrectly !'); } else { var i = order - 1; // index From 0 , The sequence number starting from 1 , Be adjusted here return this.partition(i); } }; /** * Delimited single The return value after the * * @param ok * boolean Values that It has been found * @param subArr * Sub-array where the target value, when ok = false When using this array * @param i * Target sub-array in order, from the 0 The beginning, when ok = false When using this value * @param v * Target, when ok = true Only when using this value * @return */ function OrderStaticResult(ok, subArr, i, v) { this.ok = ok; this.subArr = subArr; this.i = i; this.v = v; }

* Html

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> <html> <head> <meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /> <script type="text/javascript" src="js/order_statistic.js"></script> </head> <body> <input type="button" value="order statistic""var i = 6;alert(arr_order_statistic + ' In ,\n Ranked '+ i +' position is : '+ new OrderStatistic(arr_order_statistic).getByOrder(i));" /> </body> </html>

*

------