无序数组求中位数的方法
2018-03-18 本文已影响0人
倦飞知还
前言
数组的主要操作包括查找和排序，排序最常用的算法有冒泡排序、选择排序、选择排序、插入排序、堆排序、合并排序。排序算法不仅仅只能用于排序，其稍加改变便可以产生一些意想不到的效果。例如，利用堆排序算法的变体可以快速在无序队列中查找到前某几位或者后某几位元素，利用快速排序算法的变体可以在无序数组中求中位数。
中位数
中位数是指将一个无序数组排成有序之后，位置为(n+1)/2的元素。
快速排序
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
实现原理
利用快速排序求无序数组的中位数的步骤如下：
- 步骤一、选出一个元素作为无序数组的分割元素，并将这个元素与首元素交换位置。
- 步骤二、向后遍历这个数组，比较元素与分割元素的大小，如果元素比分割元素小，则先将元素与分割元素的前一位调换位置，再将其与分割元素调换位置。
- 步骤三、完成遍历后，数组以分割元素的界限，分成两个无序数组，前面的数组比后面的数组都要小。
- 步骤四、如果分割元素的位置比（n+1）/2要大，则以前面的无序数组重新按照步骤一执行，如果小于，则以后面的元素按照步骤一执行。一直到所选择的分割元素的位置为（n+1）/2为止，此分割元素即为中位数。
算法
开始执行搜索算法：
int[] arrays = Utils.getArrays(1000000);
long start = System.currentTimeMillis();
int i = getMiddle(arrays, 0, arrays.length - 1);
long cost = (System.currentTimeMillis() - start);
System.out.println("time:" + cost);
// System.out.println("arrays:"+Utils.getArrayString(arrays));
System.out.println("result middle " + i + "result:" + arrays[i]);
System.out.println("time:" + times);
搜索算法的执行过程：
private int getMiddle(int[] arrays, int i, int j) {
// System.out.println("arrays:"+Utils.getArrayString(arrays));
if (i == arrays.length / 2 || i == (arrays.length + 1) / 2) {
return i;
}
if (j == arrays.length / 2 || j == (arrays.length + 1) / 2) {
return j;
}
// System.out.println("swapTemp "+ swapTemp);
int middle = i;
int temp = arrays[i];
for (int k = i + 1; k <= j; k++) {
times++;
if (arrays[k] < temp) {
if (k == middle + 1) {
arrays[middle] = arrays[k];
arrays[middle + 1] = temp;
middle++;
continue;
}
arrays[middle] = arrays[k];
arrays[k] = arrays[middle + 1];
arrays[middle + 1] = temp;
middle++;
continue;
}
}
System.out.println("middle " + middle + "value:" + arrays[middle]);
if (middle == (arrays.length - 1) / 2 || middle == arrays.length / 2) {
return middle;
}
if (middle > (arrays.length + 1) / 2) {
return getMiddle(arrays, i, middle - 1);
} else {
return getMiddle(arrays, middle + 1, j);
}
}
算法优化
整个算法时间复杂度为O(n)。通过上述的搜索代码，去查找有一百万元素的无序数组，发现其平均遍历次数为三百五十万次，并且比较不稳定。经过研究发现不稳定的原因为：分割元素的选择。我们每次选择分割元素是随机选择的，分割元素与中位数总是有一定的距离误差，如果误差比较大时，下一次需要遍历的数组就大。因此，需要对分割点的选择做优化。
优化方案一
方案
- 如果无序数组个数大于100，先随机选择30个元素。
- 求出这三十个元素的平均值。
- 求出最接近平均值的元素。
- 将这个元素作为分割点。
代码
private int getMiddle(int[] arrays, int i, int j) {
// System.out.println("arrays:"+Utils.getArrayString(arrays));
if (i == arrays.length / 2 || i == (arrays.length + 1) / 2) {
return i;
}
if (j == arrays.length / 2 || j == (arrays.length + 1) / 2) {
return j;
}
int start = getRawMiddle(arrays, i, j);
int swapTemp = arrays[start];
arrays[start] = arrays[i];
arrays[i] = swapTemp;
// System.out.println("swapTemp "+ swapTemp);
int middle = i;
int temp = arrays[i];
for (int k = i + 1; k <= j; k++) {
times++;
if (arrays[k] < temp) {
if (k == middle + 1) {
arrays[middle] = arrays[k];
arrays[middle + 1] = temp;
middle++;
continue;
}
arrays[middle] = arrays[k];
arrays[k] = arrays[middle + 1];
arrays[middle + 1] = temp;
middle++;
continue;
}
}
System.out.println("middle " + middle + "value:" + arrays[middle]);
if (middle == (arrays.length - 1) / 2 || middle == arrays.length / 2) {
return middle;
}
if (middle > (arrays.length + 1) / 2) {
return getMiddle(arrays, i, middle - 1);
} else {
return getMiddle(arrays, middle + 1, j);
}
}
求分割点代码
private int getRawMiddle(int[] arrays, int i, int j) {
if (j - i < 100) {
return j;
}
long sum = 0;
int min = Integer.MAX_VALUE;
int max = 0;
int[] index = new int[30];
for (int k = 0; k < 30; k++) {
times++;
int currentIndex = (int) (Math.random() * (j - i) + i);
sum = sum + arrays[currentIndex];
int currentValue = arrays[currentIndex];
if (min > currentValue) {
min = currentValue;
} else if (max < currentIndex) {
max = currentValue;
}
index[k] = currentIndex;
}
int average = (int) sum / 30;
int minIndex = 0;
int minDistance = Integer.MAX_VALUE;
for (int m = 0; m < 30; m++) {
int currentDistance = Math.abs(arrays[index[m]] - average);
if (currentDistance < minDistance) {
minDistance = currentDistance;
minIndex = m;
}
}
return index[minIndex];
}
优化方案二
方案
- 如果无序数组个数大于100，先随机选择30个元素。
- 将这30个元素进行排序。
- 找出位置最接近中位数的元素。
- 将这个元素作为分割点。
代码
private int getRawMiddle(int[] arrays, int i, int j) {
if (j - i < 100) {
return j;
}
TreeMap<Integer, Integer> treeMap = new TreeMap();
int currentIndex = 0;
for (int k = 0; k < 60; k++) {
currentIndex = (int) (Math.random() * (j - i) + i);
treeMap.put(arrays[currentIndex], currentIndex);
}
int index = (int) (arrays.length / 2 - i) * 60 / (j - i);
if (i + j > arrays.length - 1) {
index = index + 1;
} else if (i + j < arrays.length - 1) {
index = index - 1;
}
if (index < 0) {
index = 0;
} else if (index > 59) {
index = 59;
}
Iterator<Entry<Integer, Integer>> iterator = treeMap.entrySet().iterator();
int match = 0;
System.out.println("index:" + index);
while (iterator.hasNext()) {
Entry<Integer, Integer> next = iterator.next();
match++;
if (match == index) {
int value = next.getValue();
System.out.println("value:" + value);
return value;
}
}
System.out.println("value:" + currentIndex);
return currentIndex;
}
优化方案之间的比较
经过多次测试，发现同样查找一百万元素的中位数，第一种优化方案的执行平均遍历次数为两百五十万左右，执行次数比较稳定。第二种优化方案的执行次数在一百八十万左右，执行次数没有第一种优化方案稳定，但是比未优化前稳定。
联系
邮箱：sysuzhuminh@gmail.com
微信：zhminh
github地址：https://github.com/huolizhuminh/AndroidSkills/blob/master/JavaSkillDemo/src/minhui/demo/arithmatic/ArithMatic3.java
