使用快速选择算法的未排序数组的中位数 _快速选择算法

本文概述

C ++
Java
Python3
C#

给定一个长度为N的未排序数组arr[]，任务是找到这个数组的中位数。
一个大小为N的有序数组的中位数定义为N为奇数时的中间元素，N为偶数时的中间两个元素的平均值。
例子：

【使用快速选择算法的未排序数组的中位数】输入：arr [] = {12, 3, 5, 7, 4, 19, 26}
输出：7
给定数组arr [] = {3, 4, 5, 7, 12, 19, 26}的排序序列
元素数量为奇数, 中位数为给定数组arr []的排序序列中的第4个元素, 即7
输入：arr [] = {12, 3, 5, 7, 4, 26}
输出：6
元素是偶数, 中位数是给定数组arr []的排序序列中第3个元素和第4个元素的平均值, 这意味着(5 + 7)/ 2 = 6

简单的方法：

对数组排序arr []按升序排列。
如果元素数量arr []是奇数, 则中位数是arr [n / 2].
如果元素数arr []是偶数, 中位数是arr [n / 2]和arr [n / 2 + 1]的平均值.

以上方法的实现请参阅本文。
有效方法:使用随机快速选择

从中随机选择枢轴元素arr []和使用分割步骤来自快速排序算法将所有小于枢轴的元素排列在其左侧, 并将所有元素大于其枢轴排列在其右侧。
如果在上一步之后, 所选枢轴的位置在数组的中间, 则它是给定数组的所需中间值。
如果位置在中间元素之前, 则对子数组重复该步骤, 从先前的起始索引开始, 然后将所选的枢轴作为结束索引。
如果位置在中间元素之后, 则对子数组重复该步骤, 从选定的枢轴开始, 到上一个结束索引结束。
请注意, 在偶数个元素的情况下, 必须找到中间两个元素, 它们的平均值将是数组的中位数。

下面是上述方法的实现：
C ++

//CPP program to find median of //an array #include "bits/stdc++.h" using namespace std; //Utility function to swapping of element void swap( int * a, int * b) { int temp = *a; *a = *b; *b = temp; } //Returns the correct position of //pivot element int Partition( int arr[], int l, int r) { int lst = arr[r], i = l, j = l; while (j < r) { if (arr[j] < lst) { swap(& arr[i], & arr[j]); i++; } j++; } swap(& arr[i], & arr[r]); return i; } //Picks a random pivot element between //l and r and partitions arr[l..r] //around the randomly picked element //using partition() int randomPartition( int arr[], int l, int r) { int n = r - l + 1; int pivot = rand () % n; swap(& arr[l + pivot], & arr[r]); return Partition(arr, l, r); } //Utility function to find median void MedianUtil( int arr[], int l, int r, int k, int & a, int & b) { //if l < r if (l < = r) { //Find the partition index int partitionIndex = randomPartition(arr, l, r); //If partion index = k, then //we found the median of odd //number element in arr[] if (partitionIndex == k) { b = arr[partitionIndex]; if (a != -1) return ; } //If index = k - 1, then we get //a & b as middle element of //arr[] else if (partitionIndex == k - 1) { a = arr[partitionIndex]; if (b != -1) return ; } //If partitionIndex> = k then //find the index in first half //of the arr[] if (partitionIndex> = k) return MedianUtil(arr, l, partitionIndex - 1, k, a, b); //If partitionIndex < = k then //find the index in second half //of the arr[] else return MedianUtil(arr, partitionIndex + 1, r, k, a, b); } return ; } //Function to find Median void findMedian( int arr[], int n) { int ans, a = -1, b = -1; //If n is odd if (n % 2 == 1) { MedianUtil(arr, 0, n - 1, n /2, a, b); ans = b; } //If n is even else { MedianUtil(arr, 0, n - 1, n /2, a, b); ans = (a + b) /2; } //Print the Median of arr[] cout < < "Median = " < < ans; } //Driver program to test above methods int main() { int arr[] = { 12, 3, 5, 7, 4, 19, 26 }; int n = sizeof (arr) /sizeof (arr[0]); findMedian(arr, n); return 0; }

Java

//JAVA program to find median of //an array class GFG { static int a, b; //Utility function to swapping of element static int [] swap( int [] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; return arr; } //Returns the correct position of //pivot element static int Partition( int arr[], int l, int r) { int lst = arr[r], i = l, j = l; while (j < r) { if (arr[j] < lst) { arr = swap(arr, i, j); i++; } j++; } arr = swap(arr, i, r); return i; } //Picks a random pivot element between //l and r and partitions arr[l..r] //around the randomly picked element //using partition() static int randomPartition( int arr[], int l, int r) { int n = r - l + 1 ; int pivot = ( int ) (Math.random() % n); arr = swap(arr, l + pivot, r); return Partition(arr, l, r); } //Utility function to find median static int MedianUtil( int arr[], int l, int r, int k) { //if l < r if (l < = r) { //Find the partition index int partitionIndex = randomPartition(arr, l, r); //If partion index = k, then //we found the median of odd //number element in arr[] if (partitionIndex == k) { b = arr[partitionIndex]; if (a != - 1 ) return Integer.MIN_VALUE; } //If index = k - 1, then we get //a & b as middle element of //arr[] else if (partitionIndex == k - 1 ) { a = arr[partitionIndex]; if (b != - 1 ) return Integer.MIN_VALUE; } //If partitionIndex> = k then //find the index in first half //of the arr[] if (partitionIndex> = k) return MedianUtil(arr, l, partitionIndex - 1 , k); //If partitionIndex < = k then //find the index in second half //of the arr[] else return MedianUtil(arr, partitionIndex + 1 , r, k); } return Integer.MIN_VALUE; } //Function to find Median static void findMedian( int arr[], int n) { int ans; a = - 1 ; b = - 1 ; //If n is odd if (n % 2 == 1 ) { MedianUtil(arr, 0 , n - 1 , n /2 ); ans = b; } //If n is even else { MedianUtil(arr, 0 , n - 1 , n /2 ); ans = (a + b) /2 ; } //Print the Median of arr[] System.out.print( "Median = " + ans); } //Driver code public static void main(String[] args) { int arr[] = { 12 , 3 , 5 , 7 , 4 , 19 , 26 }; int n = arr.length; findMedian(arr, n); } } //This code is contributed by 29AjayKumar

Python3

# Python3 program to find median of # an array import random a, b = None , None ; # Returns the correct position of # pivot element def Partition(arr, l, r) : lst = arr[r]; i = l; j = l; while (j < r) : if (arr[j] < lst) : arr[i], arr[j] = arr[j], arr[i]; i + = 1 ; j + = 1 ; arr[i], arr[r] = arr[r], arr[i]; return i; # Picks a random pivot element between # l and r and partitions arr[l..r] # around the randomly picked element # using partition() def randomPartition(arr, l, r) : n = r - l + 1 ; pivot = random.randrange( 1 , 100 ) % n; arr[l + pivot], arr[r] = arr[r], arr[l + pivot]; return Partition(arr, l, r); # Utility function to find median def MedianUtil(arr, l, r, k, a1, b1) : global a, b; # if l < r if (l < = r) :# Find the partition index partitionIndex = randomPartition(arr, l, r); # If partion index = k, then # we found the median of odd # number element in arr[] if (partitionIndex = = k) : b = arr[partitionIndex]; if (a1 ! = - 1 ) : return ; # If index = k - 1, then we get # a & b as middle element of # arr[] elif (partitionIndex = = k - 1 ) : a = arr[partitionIndex]; if (b1 ! = - 1 ) : return ; # If partitionIndex> = k then # find the index in first half # of the arr[] if (partitionIndex> = k) : return MedianUtil(arr, l, partitionIndex - 1 , k, a, b); # If partitionIndex < = k then # find the index in second half # of the arr[] else : return MedianUtil(arr, partitionIndex + 1 , r, k, a, b); return ; # Function to find Median def findMedian(arr, n) : global a; global b; a = - 1 ; b = - 1 ; # If n is odd if (n % 2 = = 1 ) : MedianUtil(arr, 0 , n - 1 , n //2 , a, b); ans = b; # If n is even else : MedianUtil(arr, 0 , n - 1 , n //2 , a, b); ans = (a + b) //2 ; # Print the Median of arr[] print ( "Median = " , ans); # Driver code arr = [ 12 , 3 , 5 , 7 , 4 , 19 , 26 ]; n = len (arr); findMedian(arr, n); # This code is contributed by AnkitRai01

//C# program to find median of //an array using System; class GFG { static int a, b; //Utility function to swapping of element static int [] swap( int [] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; return arr; } //Returns the correct position of //pivot element static int Partition( int []arr, int l, int r) { int lst = arr[r], i = l, j = l; while (j < r) { if (arr[j] < lst) { arr = swap(arr, i, j); i++; } j++; } arr = swap(arr, i, r); return i; } //Picks a random pivot element between //l and r and partitions arr[l..r] //around the randomly picked element //using partition() static int randomPartition( int []arr, int l, int r) { int n = r - l + 1; int pivot = ( int ) ( new Random().Next() % n); arr = swap(arr, l + pivot, r); return Partition(arr, l, r); } //Utility function to find median static int MedianUtil( int []arr, int l, int r, int k) { //if l < r if (l < = r) { //Find the partition index int partitionIndex = randomPartition(arr, l, r); //If partion index = k, then //we found the median of odd //number element in []arr if (partitionIndex == k) { b = arr[partitionIndex]; if (a != -1) return int .MinValue; } //If index = k - 1, then we get //a & b as middle element of //[]arr else if (partitionIndex == k - 1) { a = arr[partitionIndex]; if (b != -1) return int .MinValue; } //If partitionIndex> = k then //find the index in first half //of the []arr if (partitionIndex> = k) return MedianUtil(arr, l, partitionIndex - 1, k); //If partitionIndex < = k then //find the index in second half //of the []arr else return MedianUtil(arr, partitionIndex + 1, r, k); } return int .MinValue; } //Function to find Median static void findMedian( int []arr, int n) { int ans; a = -1; b = -1; //If n is odd if (n % 2 == 1) { MedianUtil(arr, 0, n - 1, n /2); ans = b; } //If n is even else { MedianUtil(arr, 0, n - 1, n /2); ans = (a + b) /2; } //Print the Median of []arr Console.Write( "Median = " + ans); } //Driver code public static void Main(String[] args) { int []arr = { 12, 3, 5, 7, 4, 19, 26 }; int n = arr.Length; findMedian(arr, n); } } //This code is contributed by PrinciRaj1992

输出如下：