使用Python实现中位数选择算法中位数

好的。 我放弃了。 我一直在努力实现中位数算法的中位数,但我不断地给错误的结果。 我知道有很多代码下面,但我找不到我的错误,而且每个代码块具有相当的工艺设计。 快速排序是我用我从中间值选择支点的中间获得中位数排序。 应该是一个简单的快速排序的实现。 getMean简单地返回给定列表的平均值。

getPivot是我用它来选择轴。 它贯穿于列表,以5个整数的时间,发现这些整数的平均值,将意味着到一个列表C,然后找到C的中位数。 这是我使用的D选择算法的支点。

该算法D选择在理论上很简单。 当列表1项长期的基本情况返回的项目。 否则,很像在快速排序,我遍历列表。 如果我目前的数目,J,小于枢轴,我将其移动到列表中,i的左侧,并递增岛 如果是较大的,我把它移到列表的右侧,I + 1,而且不增加我。 在此之后遍历整个列表,我应该有枢轴在其适当的索引,打印报表表明,我做的。 在这一点上,我改乘向左或取决于支点是否比我试图找到位置,大于或小于的权利。

我不知道在这一点上检验一下其他打印报表,所以我转向专门的人足以采取这个代码刺伤。 我知道有相关的话题,我知道我可以做更多的打印语句,但是相信我,我试过。 什么应该是一个简单的算法中已经得到了我不少难倒。

def quickSort(m, left, right): if right - left <= 1: return m pivot = m[left] i = left + 1 j = left + 1 for j in range(j, right): if m[j] < pivot: m[j], m[i] = m[i], m[j] i += 1 elif m[j] == pivot: m[j], m[i] = m[i], m[j] print mm[left], m[i-1] = m[i-1], m[left] m = quickSort(m, left, i-1) m = quickSort(m, i, right) print m return m def getMedian(list): length = len(list) if length <= 1: return list[0] elif length % 2 == 0: i = length/2 return list[i] else: i = (length + 1)/2 return list[i] def getPivot(m): c = [] i = 0 while i <= len(m) - 1: tempList = [] j = 0 while j < 5 and i <= len(m) - 1: tempList.append(m[i]) i = i + 1 j = j + 1 tempList = quickSort(tempList, 0, len(tempList) - 1) c.append(getMedian(tempList)) c = quickSort(c, 0, len(c) - 1) medianOfMedians = getMedian(c) return medianOfMedians def dSelect(m, position): pivot = getPivot(m) i = 0 j = 0 if len(m) <= 1: return m[0] for j in range(0, len(m)): if m[j] < pivot: m[j], m[i] = m[i], m[j] i += 1 elif m[j] == pivot: m[j], m[i] = m[i], m[j] print "i: " + str(i) print "j: " + str(j) print "index of pivot: " + str(m.index(pivot)) print "pivot: " + str(pivot) + " list: " + str(m) if m.index(pivot) == position: return pivot elif m.index(pivot) > position: return dSelect(m[0:i], position) else: return dSelect(m[i:], position - i)

--------------解决方案-------------

最大的问题是这条线的位置:

i = (length + 1)/2

如果列表= [1,2,3,4,5,6,7]答案应该是4,它是表[3]。 您的版本如下所示:

i = (7 + 1) / 2

所以我等于4,而不是3.与偶数长度列表部分类似的问题,虽然这不应该是大问题的。

分类:蟒蛇 时间:2015-03-15 人气:0
本文关键词: 算法,蟒蛇,排序
分享到:

相关文章

Copyright (C) 55228885.com, All Rights Reserved.

55228885 版权所有 京ICP备15002868号

processed in 0.178 (s). 10 q(s)