有两个序列a,b，大小都为n,序列元素的值任意整形数，无序； 要求：通过交换a,b中的元素，使[序列a元素的和]与[序列b元素的和]之间的差最小。 算法 1.将两序列合并为一个序列，并排序，为序列Source 2.拿出最大元素Big，次大的元素Small 3.在余下的序列S[:-2]进行平分，得到序列max，min 4.将Small加到max序列，将Big加大min序列，重新计算新序列和，和大的为max，小的为min。 python实现代码
def mean( sorted_list ):if not sorted_list:return (([],[]))big = sorted_list[-1]small = sorted_list[-2]big_list, small_list = mean(sorted_list[:-2])big_list.append(small)small_list.append(big)big_list_sum = sum(big_list)small_list_sum = sum(small_list)if big_list_sum > small_list_sum:return ( (big_list, small_list))else:return (( small_list, big_list))tests = [ [1,2,3,4,5,6,700,800],[10001,10000,100,90,50,1],range(1, 11),[12312, 12311, 232, 210, 30, 29, 3, 2, 1, 1]]for l in tests:l.sort()PRintprint "Source List:/t", ll1,l2 = mean(l)print "Result List:/t", l1, l2print "Distance:/t", abs(sum(l1)-sum(l2))print '-*'*40输出结果：
Source List: [1, 2, 3, 4, 5, 6, 700, 800]Result List: [1, 4, 5, 800] [2, 3, 6, 700]Distance: 99-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*Source List: [1, 50, 90, 100, 10000, 10001]Result List: [50, 90, 10000] [1, 100, 10001]Distance: 38-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*Source List: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]Result List: [2, 3, 6, 7, 10] [1, 4, 5, 8, 9]Distance: 1-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*Source List: [1, 1, 2, 3, 29, 30, 210, 232, 12311, 12312]Result List: [1, 3, 29, 232, 12311] [1, 2, 30, 210, 12312]Distance: 21-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*怎样让python实现希尔排序算法
def shellSort(items):inc = len(items) / 2while inc:for i in xrange(len(items)):j = itemp = items[i]while j >= inc and items[j-inc] > temp:items[j] = items[j - inc]j -= incitems[j] = tempinc = inc/2 if inc/2 else (0 if inc==1 else 1)a = [35, -8, 11, 1, 68, 0, 3];shellSort(a)print a # [-8, 0, 1, 3, 11, 35, 68]新闻热点
疑难解答
