![](https://csdnimg.cn/release/download_crawler_static/67629793/bg8.jpg)
参考文档
算法导论第九章:中位数和顺序统计学
寻找数组中第 k 小元素:http://blog.csdn.net/incstrive/article/details/8158081
查找数组中第 k 个最小元素—对快排的改动
http://hi.baidu.com/chareles2012/item/47cd21122d71c0731109b570
STL 源 码 分 析 --nth_element() 使 用 与 源 码 分 析
http://www.tuicool.com/articles/2uM3mqR
STL 源 码 解 析 - nth_element :
http://blog.csdn.net/lifesider/article/details/6580240
带权中位数:
算法导论_中位数与带权中位数:
http://www.cnblogs.com/sleeper-qp/archive/2011/11/03/2234482.html
单机和多机最优服务次序
一.单机最优服务次序
1.问题描述 设有 个顾客同时等待一项服务。顾客 需要的服务时间为 ,
。应如何安排 个顾客的服务次序才能使平均等待时间达到最小 ? 平
均等待时间是 个顾客等待服务时间的总和除以 。
2.问题分析 采用贪心算法,第一个被服务的顾客所需的等待时间为 0,由于只
有一个服务机,因此第二个顾客的等待时间取决于第一个顾客,令 表示第 个顾
客的等待服务时间, 表示当前队列长度为 时候的总服务时间,即 ,
。
根据上公式有 ,因此若要第二个顾客的等待时间小,则第一个顾客的
服务时间是最短的,那么我们首先将 , 按照升序进行排序,该顺序即
为服务次序,由于在这个例子中贪心算法的局部最优即使它的全局最优,因此它
的最优服务次序即 的升序序列。其时间复杂度主要取决于排序算法的时间复杂
度,我采用的是冒泡排序,时间复杂度为 。
3.问题求解
1. N 个顾客,每个顾客服务时间为 t
i.
2. 将所有顾客的服务时间存在数组 data[]中
3. 将 data[]内所有数据从小到大进行排序
4. 用数组 sequence[]存储排序队列
5. 采用贪心算法依次选取 data[]中的元素放入 sequence[]中
6. 最终 sequence[]的内容即为最优服务次序
代码如下:
读取文件类:ReadFile
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;