快速求数组的中值（不是中间序号的值）
/* 电脑上食用更佳哦! */
之前需要做3*3的中值滤波，将图片的数据取出来之后要找出3*3窗口中的中值，并替换掉中间序号的值，所以快速找到中值很重要，这对程序运行时间影响很大
一般要处理数组的元素个数都是奇数，这里用3*3，9个元素的数组举例
如何快速找出一个数组中的中值
a、初级
数组排序后找出中间序号的值，就是其中值，随便一个排序方式都可以做到
//让一位数组pixel[9]进行降序排列
do
{
flag=0;//循环结束的标志
for(m=0;m<9;m++)
{
if(pixel[m] { temp = pixel[m]; pixel[m] = pixel[m+1]; pixel[m+1] = temp; flag=1; }//if }//for } while (flag==1); mid=pixel[4]; b、中级 这种方法比方法a快，但也不是很快，解释起来也不方便，想了解的话参考下面这篇文章 (4条消息) C语言实现数组快速排序算法_一尺丈量的博客-CSDN博客_c语言数组快速排序 void swap(unsigned short arr[], int index_i, int index_j)//数字交换 { int k = arr[index_i]; arr[index_i] = arr[index_j]; arr[index_j] = k; } int partition_Rowe(unsigned short arr[], int low, int high) { int pivot = arr[low];//选取基准数 int low_index = low; for (int i = low + 1; i <= high; i++) { if (arr[i] < pivot) { //在序列中找到一个比pivot小的，就递增low_index low_index++; if (i!=low_index)//如果i和low_index相等，则在i之前都不存在需要交换的比pivot大的数 { swap(arr, i, low_index); } } } //low_index的位置就是pivot应处在的位置，low_index指向的总是比pivot小的数 arr[low] = arr[low_index]; arr[low_index] = pivot; return low_index; } void quick_sort(unsigned short arr[], int low, int high) { if (high > low)//如果需要排序的序列的元素个数大于1 { int pivot_pos = partition_Rowe(arr, low, high); quick_sort(arr, low, pivot_pos - 1);//左序列 quick_sort(arr, pivot_pos + 1, high);//右序列 } } //测试代码 int main() { int arr[] = {5,8,7,6,4,3,9}; for (int i = 0; i < 7; i++) { printf("%d,", arr[i]); } printf("\n"); quick_sort(arr, 0, 6); for (int i = 0; i < 7; i++) { printf("%d,",arr[i]); } return 0; } c、高级 这个方法真的是目前我用过最快的，必须亲自解释一下，比较长，希望耐心看完。 对于一个数组，如pixel[9] = { 3, 22, 16, 46, 8, 74, 24, 34, 26} 把它分成三组，每组三个，分别是 第一组：pixel[0] = 3, pixel[1] = 22, pixel[2] = 16 第二组：pixel[3] = 46, pixel[4] = 8, pixel[5] = 74 第三组：pixel[6] = 24, pixel[7] = 34, pixel[8] = 26 1）将这三组数的最小值，中值，最大值找出来 第一组的最大值用Max1，中值用Med1，最小值用Min1来表示 第二组的最大值用Max2，中值用Med2，最小值用Min2来表示 第三组的最大值用Max3，中值用Med3，最小值用Min3来表示 则可以得到其值： Max1 = pixel[1] = 22 Med1 = pixel[2] = 16 Min1 = pixel[0] = 3 Max2 = pixel[5] = 74 Med2 = pixel[3] = 46 Min2 = pixel[4] = 8 Max3 = pixel[7] = 34 Med3 = pixel[8] = 26 Min3 = pixel[6] = 24 2）找出三个最大值中的最小值，三个中值中的中值，三个最小值中的最大值 即Max1，Max2，Max3中的最小值，用Min_of_max表示，则Min_of_max = 22 Med1，Med2，Med3中的中值，用Med_of_med表示，则Med_of_med = 26 Min1， Min2，Min3中的最大值，用Max_of_min表示，则Max_of_min = 24 你可能要问找这些有什么用？不要急，往下看 3）得到三个值，Min_of_max = 22， Med_of_med = 26， Max_of_min = 24，接下来要干什么？要找这三个值中的中值，因为是9个数，所以用Med_of_nine表示， 显然 Med_of_nine = 24，则这个24就是这九个数中的中值，不信？排序看一下 3， 8， 16， 22， 24，26， 34，46，74 但是为啥这样呢？ 解释： 第一步：将数组分成三组并得到三组数中的最大，中值，最小值 这一步没什么好解释的 第二步：找出三个最大值中的最小值，三个中值中的中值，三个最小值中的最大值 关键就在这儿，那为什么要这样找？ 1、Max_of_Max = 74，即三个最大值中的最大值，也是所有元素的最大值，一定不是中值 Min_of_Min = 3，即三个最小值中的最小值，也是所有元素的最小值，一定不是中值 pass两个 Max1 = pixel[1] = 22 Med1 = pixel[2] = 16 Min1 = pixel[0] = 3 Max2 = pixel[5] = 74 Med2 = pixel[3] = 46 Min2 = pixel[4] = 8 Max3 = pixel[7] = 34 Med3 = pixel[8] = 26 Min3 = pixel[6] = 24 2、Max_of_med = 46，即三个中值中的最大值，它一定大于5个元素，分别是三个中值中的另外两个16和26，所有的最小值2，8，24。想一想，一个含有9个元素的数组，Max_of_med已经大于了5个，那他最少排第六位，甚至更靠后，肯定不是中值。中值是排在第五的 3， 8， 16， 22， 24，26， 34，46，74 同理Min_of_med = 16，三个中值中的中值，它一定小于5个元素，分别是，三个中值中的另外两个26，46，所有的最大值，22，34，74。想一想，一个含有9个元素的数组，Min_of_med已经小于了5个，那他最少排第四位，甚至更靠前，肯定不是中值。中值是排在第五的 又pass两个 Max1 = pixel[1] = 22 Med1 = pixel[2] = 16 Min1 = pixel[0] = 3 Max2 = pixel[5] = 74 Med2 = pixel[3] = 46 Min2 = pixel[4] = 8 Max3 = pixel[7] = 34 Med3 = pixel[8] = 26 Min3 = pixel[6] = 24 3、Med_of_max，最大值的中值，也最少大于5个元素，分别是同组的其余两个26，24,和第一组的所有22，16，3，pass Med_of_min，也是一样的道理，它最少小于了五个元素，我就不说了，你自己想一想，即使没有下面的数据，也应该知道至少小于哪几个 又pass两个 Max1 = pixel[1] = 22 Med1 = pixel[2] = 16 Min1 = pixel[0] = 3 Max2 = pixel[5] = 74 Med2 = pixel[3] = 46 Min2 = pixel[4] = 8 Max3 = pixel[7] = 34 Med3 = pixel[8] = 26 Min3 = pixel[6] = 24 至此，只剩下三个数，哪个是中值？当然是这三个数中的中值了。中值就找到了 这下知道为什么要选它们三个：Min_of_max = 22， Med_of_med = 26， Max_of_min = 24 做比较了吧！ 那它为什么那么快呢？ 答：它只做了13次Max，Min，Med运算能不快嘛，这三个函数又那么简单。 第一个排序，其中i = 1,2...n，n就是元素个数减一，要做1到n的和，肯定大于13很多了 第二个咱也不清楚...... 反正大概就是这么个意思 int max(int a, int b, int c) { int max = 0; if (a >= b) { max = a; } else max = b; if (max < c) return c; else return max; } int min(int a, int b, int c) { int min = 0; if (a > b) { min = b; } else min = a; if (min < c) { return min; } else return c; } #if 0 int med(int a,int b,int c){ int max = a > b ? a : b; max = max > c ? max : c; int min = a < b ? a: b; min = min < c ? min : c; int second = a + b + c - max - min; return second; } #endif /* 下面这个求中值更快，有时候不需要判断else中的内容就找到中值了 */ int med (int a, int b, int c) { if(a>=b) { if (b >= c) return b; else if (a >= c) return c; else return a; } else { if (a >= c) return a ; else if (b >= c) return c ; else return b ; } } //使用方法 int max1 = max(pixel[0],pixel[1],pixel[2]); int med1 = med(pixel[0],pixel[1],pixel[2]); int min1 = min(pixel[0],pixel[1],pixel[2]); int max2 = max(pixel[3],pixel[4],pixel[5]); int med2 = med(pixel[3],pixel[4],pixel[5]); int min2 = min(pixel[3],pixel[4],pixel[5]); int max3 = max(pixel[6],pixel[7],pixel[8]); int med3 = med(pixel[6],pixel[7],pixel[8]); int min3 = min(pixel[6],pixel[7],pixel[8]); int Min_of_Max = min(max1,max2,max3); int Max_of_min = max(min1,min2,min3); int Med_of_Med = med(med1,med2,med3); int med_of_nine = med(Min_of_Max,Max_of_min,Med_of_Med); 关于5*5的快速找中值，参考这篇，3*3的我也是参考这篇，但我觉得我解释的更详细，嘿嘿 对于之前的文章中raw滤波，其余操作都一样，只更改了找中值的方法，平均运算时间从40ms-->29ms-->14ms。图片大小是38k，如果图片更大的话能省多的时间，看着这十几毫秒很短，实际工作中，要求要我缩减到10ms及以内，鄙人不才，缩不动了。
