快速排序算法是一种分治排序算法，它将数组划分为两部分，然后分别对这两部分进行排序。它将重排序数组，使之满足一下三个条件：
1，对于某个i，a[i]在最终的位置上
2，a[l]…a[i-1]中的元素都比a[i]小
3，a[i+1] …a[r]中的元素都比a[i]大
通过划分后完成本轮排序，然后递归地处理子文件。
如果数组中有一个或者0个元素，就什么都不做。否则，调用以下算法实现快速排序：
int partition(Itema[],int l,int r)
{
int i=l-1,j=r;
Item v=a[r];
for (;;)
{
while (less(a[++i],v))
{
;
}
while (less(v,a[--j]))
{
if (j==1)
{
break;
}
}
if (i>=j)
{
break;
}
exch(a[i],a[j]);
}
exch(a[i],a[r]);
return i;
}
变量v保存了划分元素a[r]，i和j分别是左扫描指针和右扫描指针。划分循环使得i增加j减小，while循环保持一个不变的性质---------i左侧没有元素比v大，j右侧没有元素比v小。一旦两个指针相遇，我们就交换啊a[i]和a[r]，，这样v左侧的元素都小于v，v右侧的元素都大于等于v，结束划分过程。
划分是一个不确定的过程，当两个指针相遇，就通过break语句结束。测试j==1用来防止划分元素是文件总的最小元素。
voidquichsort(Item a[],int l,int r)
{
int i;
if (r<=l)
{
return;
}
i=partition(a,l,r);
quichsort(a,l,i-1);
quichsort(a,i+1,r);
}
注：快速排序是一个递归划分过程，我们对一个文件进行划分，划分原则是将一些元素放在它最终的位置上，对数组进行排序使比划分元素小的元素都在划分元素的左边，比划分元素大的元素都在划分元素的右边，然后分别对左右两部分进行递归处理。然后，从数组的左端进行扫描，直到找到一个大于划分元素的元素，同时从数据的右端开始扫描，直到找到一个小于划分元素的元素。使扫描停止的这个两个元素，显然在最终的划分数组中的位置相反，于是交换二者。继续这一过程，我们就可以保证比划分元素小的元素都在划分元素的左边，比划分元素大的元素都在划分元素的右边。
性能特征：
快速排序最坏情况下使用N*N/2次比较
快速排序平均情况下使用2*N*㏒N次比较
快速排序算法是一种不稳定的算法。
算法示意图
A
S
0
R
T
I
N
G
E
X
A
M
P
L
E
A
A
E
E
O
S
R
A
A
E
最近在做一个互联网项目，不可避免和其他互联网项目一样，需要各种类似的功能。其中一个就是通过用户访问网站的IP地址显示当前用户所在地。在没有查阅资料之前，我第一个想到的是应该有这样的RESTFUL服务，可能会有免费的，也有可能会是收费的。后来查阅了相关资料和咨询了客服人员发现了一款相当不错的库：GEOIP。
中文官网：http://www.maxmind.com/zh/home?pkit_lang=zh
英文官网：http://www.maxmind.com/en/home
而且GeoIP也提供了如我之前猜测的功能：Web Services，具体可以看这里：http://dev.maxmind.com/geoip/legacy/web-services
这里我就把官方的实例搬过来吧，Web Services ：
首先来个Java 版本：
import java.net.MalformedURLException;
import java.net.URL;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class OmniReader {
public static void main(String[] args) throws Exception {
String license_key = "YOUR_LICENSE_KEY";
String ip_address = "24.24.24.24";
String url_str = "http://geoip.maxmind.com/e?l=" + license_key + "&i=" + ip_address;
URL url = new URL(/blog_article/url_str/index.html);
BufferedReader in = new BufferedReader(new InputStreamReader(url.openStream()));
String inLine;
while ((inLine = in.readLine()) != null) {
// Alternatively use a CSV parser here.
Pattern p = Pattern.compile("\"([^\"]*)\"|(?<=,|^)([^,]*)(?:,|$)");
Matcher m = p.matcher(inLine);
ArrayList fields = new ArrayList();
String f;
while (m.find()) {
f = m.group(1);
if (f!=null) {
fields.add(f);
}
else {
fields.add(m.group(2));
}
}
String countrycode = fields.get(0);
String countryname = fields.get(1);
String regioncode = fields.get(2);
String regionname = fields.get(3);
String city = fields.get(4);
String lat = fields.get(5);
String lon = fields.get(6);
String metrocode = fields.get(7);
String areacode = fields.get(8);
String timezone = fields.get(9);
String continent = fields.get(10);
String postalcode = fields.get(11);
String isp = fields.get(12);
String org = fields.get(13);
String domain = fields.get(14);
String asnum = fields.get(15);
String netspeed = fields.get(16);
String usertype = fields.get(17);
String accuracyradius = fields.get(18);
String countryconf = fields.get(19);
String cityconf = fields.get(20);
String regionconf = fields.get(21);
String postalconf = fields.get(22);
String error = fields.get(23);
}
in.close();
}
}C#版本：
private string GetMaxMindOmniData(string IP) {
System.Uri objUrl = new System.Uri("http://geoip.maxmind.com/e?l=YOUR_LICENSE_KEY&i=" + IP);
System.Net.WebRequest objWebReq;
System.Net.WebResponse objResp;
System.IO.StreamReader sReader;
string strReturn = string.Empty;
try
{
objWebReq = System.Net.WebRequest.Create(objUrl);
objResp = objWebReq.GetResponse();
sReader = new System.IO.StreamReader(objResp.GetResponseStream());
strReturn = sReader.ReadToEnd();
sReader.Close();
objResp.Close();
}
catch (Exception ex)
{
}
finally
{
objWebReq = null;
}
return strReturn;
}Ruby版本：
#!/usr/bin/env ruby
require 'csv'
require 'net/http'
require 'open-uri'
require 'optparse'
require 'uri'
fields = [:country_code,
:country_name,
:region_code,
:region_name,
:city_name,
:latitude,
:longitude,
:metro_code,
:area_code,
:time_zone,
:continent_code,
:postal_code,
:isp_name,
:organization_name,
:domain,
:as_number,
:netspeed,
:user_type,
:accuracy_radius,
:country_confidence,
:city_confidence,
:region_confidence,
:postal_confidence,
:error]
options = { :license => "YOUR_LICENSE_KEY", :ip => "24.24.24.24" }
OptionParser.new { |opts|
opts.banner = "Usage: omni-geoip-ws.rb [options]"
opts.on("-l", "--license LICENSE", "MaxMind license key") do |l|
options[:license] = l
end
opts.on("-i", "--ip IPADDRESS", "IP address to look up") do |i|
options[:ip] = i
end
}.parse!
uri = URI::HTTP.build(:scheme => 'http',
:host => 'geoip.maxmind.com',
:path => '/e',
:query => URI.encode_www_form(:l => options[:license],
:i => options[:ip]))
response = Net::HTTP.get_response(uri)
unless response.is_a?(Net::HTTPSuccess)
abort "Request failed with status #{response.code}"
end
omni = Hash[fields.zip(response.body.encode('utf-8', 'iso-8859-1').parse_csv)]
if omni[:error]
abort "MaxMind returned an error code for the request: #{omni[:error]}"
else
puts
puts "MaxMind Omni data for #{options[:ip]}";
puts
omni.each { |key, val| printf " %-20s %s\n", key, val }
puts
end最后再来个Perl版本吧：
#!/usr/bin/env perl
use strict;
use warnings;
use Encode qw( decode );
use Getopt::Long;
use LWP::UserAgent;
use Text::CSV_XS;
use URI;
use URI::QueryParam;
my @fields = qw(
country_code
country_name
region_code
region_name
city_name
latitude
longitude
metro_code
area_code
time_zone
continent_code
postal_code
isp_name
organization_name
domain
as_number
netspeed
user_type
accuracy_radius
country_confidence
city_confidence
region_confidence
postal_confidence
error
);
my $license_key = 'YOUR_LICENSE_KEY';
my $ip_address = '24.24.24.24';
GetOptions(
'license:s' => \$license_key,
'ip:s' => \$ip_address,
);
my $uri = URI->new('http://geoip.maxmind.com/e');
$uri->query_param( l => $license_key );
$uri->query_param( i => $ip_address );
my $ua = LWP::UserAgent->new( timeout => 5 );
my $response = $ua->get($uri);
die 'Request failed with status ' . $response->code()
unless $response->is_success();
my $csv = Text::CSV_XS->new( { binary => 1 } );
$csv->parse( decode( 'ISO-8859-1', $response->content() ) );
my %omni;
@omni{@fields} = $csv->fields();
binmode STDOUT, ':encoding(UTF-8)';
if ( defined $omni{error} && length $omni{error} ) {
die "MaxMind returned an error code for the request: $omni{error}\n";
}
else {
print "\nMaxMind Omni data for $ip_address\n\n";
for my $field (@fields) {
print sprintf( " %-20s %s\n", $field, $omni{$field} );
}
print "\n";
}以上都是基于Web Services的，这里我再写个使用本地库的实例，而项目中也使用的是本地库。
首先在项目中需要添加库文件：GeoLiteCity，然后就可以利用这个文件得到城市和国家信息了，Java代码：
public class GeoBusiness {
/**
* @param args
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
System.out.println(getLocationByIp("220.181.111.147").getCity());
System.out.println(getLocationByIp("220.181.111.147").getCountryName());
}
public static Location getLocationByIp(String ipaddr) throws IOException {
String sep = System.getProperty("file.separator");
String dir = Play.configuration.getProperty("geoip.datdir");
String dbfile = dir + sep + "GeoLiteCity.dat";
LookupService cl = new LookupService(dbfile,
LookupService.GEOIP_MEMORY_CACHE);
Location location = cl.getLocation(ipaddr);
cl.close();
return location;
}
}更详细的功能比如获取省，经纬度可以参考我最前面给出的网址。
优化系统的想法真不好简单地说的明白，这样吧，我爸在陕西西安，我妈在安徽的合肥，我弟弟在深圳，打算坐飞机到北京我这里玩。家人都比较节省，打算到了机场后互相等对方，然后一起坐车租车到我住的地方。然后让我给订机票，这可难住我了。
我查了qunar，一天从西安，合肥，深圳到北京有很多班飞机，怎么样让他们总的机票价格最少，并且在机场互相等待的时间降到最低，这里假设一个人等10分钟相当于1块钱，这样我们的目标就是schedulcost=(父亲机票钱+母亲hf-bj机票钱+弟弟机票钱+父亲等候分钟/10+母亲等候分钟/10+弟弟等候时间/10)最小，这里面有可能父亲，或者母亲或者弟弟的等候分钟是0。
先定义我的家人：
people = [('baba','XA'),
('mama','HF'),
('didi','sz')] 爸爸从西安出发，妈妈从合肥出发，弟弟从深圳出发；
再定义航班信息：
flights = [('XA','BJ') : [('06:30', '08:30', 600), ('07:45', '10:15', 500)....],
('HF','BJ') : [('06:45', '09:30', 900), ('07:25', '10:45', 800)....],
('SZ','BJ') : [('06:25', '10:30', 1200), ('08：05', '12:10', 1300)....],
]从西安到北京的航班有：6：30出发，8：30到达，机票600元；07：45出发，10：15到达，机票500元。。。
从合肥到北京的航班有：6：45出发，9：30到达，机票900元；07：25出发，10：45到达，机票800元。。。
从深圳到北京的航班有：6：25出发，10：30到达，机票1200元；08：05出发，12：10到达，机票1300元。。。
下面假设我定的航班是：
sol = [2,2,1]从西安到北京的第二班，从合肥到北京的第二班，从西安到北京的第一班
下面就可以算计我上面定的航班的花费了：其中
def schedulecost(sol):
totalprice=0
latestarrival=0
for d in range(len(sol)):
origin=people[d][1]
outbound=flights[(origin,'BJ')][int(sol[d])]
totalprice+=outbound[2]
if latestarrival<getminutes(outbound[1]): latestarrival=getminutes(outbound[1])
totalwait=0
for d in range(len(sol)):
origin=people[d][1]
outbound=flights[(origin,'BJ')][int(sol[d])]
totalwait+=latestarrival-getminutes(outbound[1])
return totalprice+totalwait/10很好懂，shedulecost计算了总的航班机票钱和总的等候时间，
计算总的等候时候先找出最晚到达的一班飞机的时间latestarrival。
我们的目标：找出某种组合的sol，让schedulecost最低；
因为一天内的航班有很多，并且我已经把问题简单到最低，所以在现实情况中很容易sol的各种组合数会上亿。
如果shedulecost稍微复杂的话，在各种sol中找到最优解是不现实的。下面看看几种可能的做法：
（一）随机搜索法
最简单的，随机计算其中的一部分结果，比如100条可能的解，最终的结果取这部分计算结果中的最小值，这种算法最简单，问题也最明显。
下面的实现，第一个参数是每种可能结果的范围，比如从西安到北京一天有100个航班，从合肥到北京一天有80个航班，从深圳到北京一天有150个航班，那么domain的定义就是domain=[(0,100),(0,80),(0,150)]；第二个参数就是上面定义的schedulecost函数；
def randomoptimize(domain,costf):
best=999999999
bestr=None
for i in range(0,1000):
# Create a random solution
r=[float(random.randint(domain[i][0],domain[i][1]))
for i in range(len(domain))]
# Get the cost
cost=costf(r)
# Compare it to the best one so far
if cost<best:
best=cost
bestr=r
return r一千次的尝试可能是总解总很说得好的一部分，但是在多试几次之后，也许会得到一个差不多的解；
随机搜索法的问题在于，随机搜索是跳跃性的，这次的计算和上次的计算之前没有任何关系，也就是最新一次计算并没能利用之前已发现的优解，下面看看几种改进的算法：
（二）模拟爬山法
爬山法从一个随机解开始，然后在其临近的解中寻找更好的题解。在本例中，亦即找到所有相对于最初的随机安排，能够让某个人乘坐的航班稍早或者稍晚一些的安排，沃恩对每一个相邻的时间安排都进行成本计算，具有最低成本的安排将成为新的题解。重复这一过程知道没有相邻安排能够改善成本为止：
def hillclimb(domain,costf):
# Create a random solution
sol=[random.randint(domain[i][0],domain[i][1])
for i in range(len(domain))]
# Main loop
while 1:
# Create list of neighboring solutions
neighbors=[]
for j in range(len(domain)):
# One away in each direction
if sol[j]>domain[j][0]:
neighbors.append(sol[0:j]+[sol[j]+1]+sol[j+1:])
if sol[j]<domain[j][1]:
neighbors.append(sol[0:j]+[sol[j]-1]+sol[j+1:])
# See what the best solution amongst the neighbors is
current=costf(sol)
best=current
for j in range(len(neighbors)):
cost=costf(neighbors[j])
if cost<best:
best=cost
sol=neighbors[j]
# If there's no improvement, then we've reached the top
if best==current:
break
return sol
之所以叫爬山法，就是我们沿着一条下坡路一直走到坡底，这个方法的速度很快，并且找到的结果一般会比随机搜索法好一些。但是也有个问题，这种算法的假设是最优解就在初始下坡位置的波谷处，第一次的随机解会影响最终的效果。所以这种算法可以求出局部最优解，而不是全局最优解。
（三）模拟退火法
退火指合金在加热后再慢慢冷却的过程。大量的原子因为受到激发而向周围跳跃，然后又逐渐稳定到一个低能阶的状态。
有时候在找到最优解前转向一个更差的解是有必要的。退火法一个随机解开始，用一个变量表示温度，温度在最开始会很高，尔后慢慢变低。每一次迭代周期，算法会随机选中题解中的某个数字，然后朝某个方向变化。这个算法和爬山法的区别是。爬山法每次的迭代都会朝成本最低的发展，而退火法不一定，有一定的比