Arrays.sort()
先来看看Arrays.sort();，一点进这个方法会看到是这样子的
publicstaticvoidsort(int[]a){
DualPivotQuicksort.sort(a,0,a.length-1,null,0,0);
}123
果然没这么简单，DualPivotQuicksort翻译过来就是双轴快速排序，关于双轴排序可以去这里http://www.cnblogs.com/nullzx/p/5880191.html看看。那再次点进去，可以发现有这么一段代码
if(right-left<QUICKSORT_THRESHOLD){
sort(a,left,right,true);
return;
}1234
可以发现如果数组的长度小于QUICKSORT_THRESHOLD的话就会使用这个双轴快速排序，而这个值是286。
那如果大于286呢，它就会坚持数组的连续升序和连续降序性好不好，如果好的话就用归并排序，不好的话就用快速排序，看下面这段注释就可以看出
*Thearrayisnothighlystructured,
*.
123
那现在再回到上面的决定用双轴快速排序的方法上，再点进去，发现又会多一条判断
//Useinsertionsortontinyarrays
if(length<INSERTION_SORT_THRESHOLD)
123
即如果数组长度小于INSERTION_SORT_THRESHOLD(值为47)的话，那么就会用插入排序了，不然再用双轴快速排序。
所以总结一下Arrays.sort()方法，如果数组长度大于等于286且连续性好的话，就用归并排序，如果大于等于286且连续性不好的话就用双轴快速排序。如果长度小于286且大于等于47的话就用双轴快速排序，如果长度小于47的话就用插入排序。真是有够绕的~
2. 用Javascript写排序算法的动画演示
1.让JavaScript暂停下来，慢下来。
JavaScript排序是很快的，要我们肉眼能看到它的实现过程，我首先想到的是让排序慢下来。 排序的每一个循环都让它停300ms然后再继续进行。 怎么样才能停下来呢。查了一下JavaScript貌似没有sleep()这样的函数。暂停做不到，但是可以想办法让实现跟暂停差不多的效果。比如在循环里做一些无关的事情 。
首先尝试了让while(true)来一直执行一个空操作。执行一段时间再回到排序逻辑。代码大致是这样：
for (var i = 0; i < 3; i++) {
document.writeln(i); //DOM操作
var now = new Date().getTime();
while(new Date().getTime() - now < 3000){}
}
慢是慢下来了。不过太耗资源，排序进行过程中dom并不会有任何改变，直到排序结束， DOM会变成排序好之后的样子。 但是如果设置断点一步步执行的时候 又可以看到一步步的排序变化。估计是因为这个操作太耗资源导致浏览器下达了一个DOM操作的命令但是一直腾不出资源来进行DOM操作。所以真正DOM操作的时候在js代码执行结束之后。
所以让JavaScript排序慢来来还是没有实现。
另一种让JavaScript暂停下来的思路：
写这个文章的时候又想到一种方法来让JavaScript停下来。 那就是AJAX的同步请求，以及超时操作。 也就是在要停下来的地方放一个AJAX请求，同步请求， 然后设置超时。超时的时间就是我们要暂停的时间。为了避免在到达超时请求之前服务 器就返回了我们的AJAX请求。可以在服务端运行类似 sleep()的程序 。从而保证AJAX不会返回。直接超时然后返回到我们的循环。不过这只是个设想。有兴趣的可以去尝试一下。
2.闭包和定时器。 这种思路不需要让排序过程慢下来。而是使用闭包缓存排序过程中数组的变化。然后使用setTimeout来确定展示每一个数组状态的顺序。在排序循环中放入类似下面的代码。
(function(){
var theArr = arr.slice();//当前数组状态的备份
setTimeout(function(){
bubbleSortDom(theArr);//排序的DOM操作。
},500*timeCount);
timeCount++;//定时器的顺序。
})();
不过后来发现这样子写的话代码量会比较大，逻辑有修改的话要修改的地方会有点多。局限性很多，比如要实现排序动画加快或减慢操作几乎是很困难的。所以还要另想办法。
3.缓存排序中的数组状态。
也就是在排序过程中。将数组的每一轮循环的状态保存到一个数组。然后再用这个数组依次将排序状态保存下来。 只需要在排序中加入一句就行。
this.pushHis(arr.slice(),i-1,j,k,temp);
这样就只需要一个setInterval()就可以了。并且可以很方便的实现动画的加快与减慢。逻辑也比较好理解 。
问题二：如何实现JavaScript排序动画的加快与减慢。
我们问题一使用的第三种方法。 得到一个保存了每一步排序状态的数组arr。 然后我们可以使用一个setInterval()定时器一步步展现排序状态。 如果要加快速度或减慢速度。就clearInterval()，修改定时器的执行间隔，重新setInterval()，从前一个定时器执行到数组中的位置开始执行。
问题三：对于使用递归实现的数组怎么办？ 不是在原数组上进行操作的怎么办？
使用递归实现的排序。 可能并没有在一个数组上进行操作，只是最后返回一个排序好的数组出来。那么我们要如何获得排序中的数组的完整状态呢。
比如快速排序。
最开始不考虑动画，我的实现是这样的：
function quickSort(arr){
var len = arr.length,leftArr=[],rightArr=[],tag;
if(len<2){
return arr;
}
tag = arr[0];
for(i=1;i<len;i++){
if(arr[i]<=tag){
leftArr.push(arr[i])
}else{
rightArr.push(arr[i]);
}
}
return quickSort(leftArr).concat(tag,quickSort(rightArr));
}
然后为了考虑动画，我改写了它的逻辑，让它在同一个数组上进行了实现。 其实是在递归的时候传入了当前的的子数组在原数组中的起始位置。从而在原数组上进行了操作。
用了两种方法来实现方式。在排序逻辑上略有不同。
第一种是先跟远处的对比。遇到比自己小的放到自己前面去。循环序号+1。比自己大的放到当前排序子数组的最后面去，循环序号不变。直到排列完成。
这种方法的缺点是即使是一个有序数组。它也会重新排。
第二种方法是 除了标记位，再设置一个对比位。 遇到比自己小的，放到前面去，标记位的位置+1，标记位与对比位之间所有的往后面移动一个位置。
遇到比自己大的。标记位不变，对比位+1。
这种方法的缺点是对数组进行的操作太多。优点是对有序数组不会再排。
方式一：
function quickSort(arr,a,b,qArr){
var len = arr.length,leftArr=[],rightArr=[],tag,i,k,len_l,len_r,lb,ra,temp;
if(a == undefined && b == undefined){
a = 0; b= arr.length-1;//初始化起始位置。
}
if(qArr == undefined){
qArr = arr.slice();
}
if((len == 2 && arr[0] == arr[1])||len<2){
return arr;
}
tag = qArr[a];
for (i = 1; i < len;) {
if(qArr[a+i]<=tag){
leftArr.push(qArr[a+i]);
qArr[a+i-1] = qArr[a+i];
qArr[a+i] = tag;
k = a+i;
i++;
}else{
if(leftArr.length+rightArr.length == len-1){
break;
}
temp = qArr[a+i];
qArr[a+i] = qArr[b-rightArr.length];
qArr[b-rightArr.length] = temp;
rightArr.push(temp);
k = a+i-1;
}
this.pushHis(qArr.slice(),a,b,k);
}
len_l = leftArr.length;
len_r = rightArr.length;
if(len_l== 0){
lb = a;
}else{
lb = a+len_l -1;
this.sort(leftArr,a,lb,qArr);
}
if(len_r == 0){
ra = b;
}else{
ra = b + 1 - len_r;
this.sort(rightArr,ra,b,qArr)
}
return qArr
}
方式二：
function quickSort2(arr,a,b,qArr){
var len = arr.length,leftArr=[],rightArr=[],tag,i,j,k,temp,len_l,len_r,lb,ra;
if(a == undefined && b == undefined){
a = 0; b= arr.length-1;//初始化起始位置。
}
if(qArr == undefined){
qArr = arr.slice();
}
if(len<2){
return arr;
}
if(len == 2 && arr[0] == arr[1]){
return arr;
}
tag = qArr[a];
for (i = 1,k = 0; i < len;) {
if(qArr[a+i]>=tag){
rightArr.push(qArr[a+i]);
i++;
}else{
temp = qArr[a+i];
for(j = a+i;j>a+k;j--){
qArr[j] = qArr[j-1];
// this.pushHis(qArr.slice(),a,b,a+k);
}
qArr[a+k] = temp;
leftArr.push(temp);
k++;
i++;
}
this.pushHis(qArr.slice(),a,b,a+k,i-1);
}
len_l = leftArr.length;
len_r = rightArr.length;
if(len_l== 0){
lb = a;
}else{
lb = a+len_l -1;
this.sort(leftArr,a,lb,qArr);
}
if(len_r == 0){
ra = b;
}else{
ra = b + 1 - len_r;
this.sort(rightArr,ra,b,qArr)
}
return qArr;
}
具体的不同下面会有动画演示。
问题四：动画的流畅。
排序动画的DOM操作是很多的很快的。这里我做的优化只是让每一个排序步骤只涉及一个DOM操作。 全部由JavaScript拼接好，一次替换。类似下面的代码。
效果图：
主要实现了：
冒泡排序JavaScript动画演示
插入排序JavaScript动画演示
选择排序JavaScript动画演示
快速排序JavaScript动画演示
归并排序JavaScript动画演示
希尔排序JavaScript动画演示
3. 排序算法的动态显示 c++
算法如下，采用责任链模式进行各类排序算法的串接，当前已经实现选择排序和插入排序。
代码已经在VC中运行验证，谢谢！
#include <iostream>
using namespace std;
//排序接口类，抽象类
class SortInterface
{
public:
virtual bool sort(int type, int array[], int len) = 0;
protected:
int m_Type;
virtual bool callNext(int type, int array[], int len)
{
return false;
};
};
//插入排序类
class InsertSort : public SortInterface
{
public:
bool sort(int type, int array[], int len)
{
if (type != m_Type)
{
return false;
}
insertSort(array, len);
return true;
}
InsertSort()
{
m_Type = 1;
}
private:
void insertSort(int array[], int len)
{
int i,j,k;
for(i = 1; i < len; i++)
{
for(j = 0; j < i; j++)
{
if (array[i] < array[j])
{
int temp = array[i];
for(k = i; k > j; k--)
array[k] = array[k - 1];
array[j] = temp;
}
}
}
}
};
//选择排序类
class SelectSort : public SortInterface
{
public:
bool sort(int type, int array[], int len)
{
bool breturn = false;
if (type != m_Type)
{
return callNext(type, array, len);
}
selectSort(array, len);
return true;
}
SelectSort()
{
m_Type = 0;
}
protected:
bool callNext(int type, int array[], int len)
{
bool breturn = false;
SortInterface *nextSort = new InsertSort();
breturn = nextSort->sort(type, array, len);
delete nextSort;
return breturn;
}
private:
void selectSort(int array[], int len)
{
int i,j,pos = 0;
for(i = len - 1; i > 0; i--)
{
pos = 0;
for(j = 1; j <= i; j++)
{
if(array[pos] < array[j])
pos = j;
}
if (pos != i)
{
array[pos] = array[pos] + array[i];
array[i] = array[pos] - array[i];
array[pos] = array[pos] - array[i];
}
}
}
};
//排序类，采用责任链模式串接所有的排序方法，这样仅需要新增当前最后一个
//排序算法的callNext方法和新排序算法类即可，需要注意type的递增
class Sort {
public:
bool sort(int type, int array[], int len)
{
bool breturn = false;
SortInterface *firstSort = new SelectSort();
breturn = firstSort->sort(type, array, len);
delete firstSort;
return breturn;
}
void print(int array[], int len)
{
for(int i= 0; i < len; i++)
cout<<array[i];
cout<<endl;
}
};
void main()
{
int num, type;
int *array;
Sort *sortFunction;
cout<<"Input the amount of numbers(>0): ";
cin>>num;
if (num <= 0)
return;
array = new int[num];
cout<<"Input the numbers: "<<endl;
for(int i = 0; i < num; i++)
cin>>array[i];
cout<<"Input the sort type(0 or 1): ";
cin>>type;
sortFunction = new Sort();
if(sortFunction->sort(type,array,num))
{
sortFunction->print(array,num);
}
else
{
cout<<"Sort failed, your sort type maybe not be found."<<endl;
}
delete sortFunction;
delete []array;
}
4. linux sort命令 算法
man sort中关于它的描述是
sort - sort lines of text files
所以，它默认是以文本排序的。
但是它又有其它参数
-b, --ignore-leading-blanks
ignore leading blanks
-d, --dictionary-order
consider only blanks and alphanumeric characters
-f, --ignore-case
fold lower case to upper case characters
-g, --general-numeric-sort
compare according to general numerical value
-i, --ignore-nonprinting
consider only printable characters
-M, --month-sort
compare (unknown) < ‘JAN’ < ... < ‘DEC’
-n, --numeric-sort
compare according to string numerical value
-r, --reverse
reverse the result of comparisons
可以忽略前置的空格、或指定顺序字典、或忽略大小写、或以正常的数字形式、或忽略不可打印字符、或以月份（包括英语的月份）、或以字符形式的数字、或以倒序形式排序。
5. sort如何排序自定义数据类型 - C / C++ -
比如你要排的数据类型是A,元素已放好在数组Array中，长为size
sort(Array,Array + size,cmp);
cmp是一个返回bool的函数，用于定义排序顺序
bool cmp(A& a1,A& a2){
return a1.member > a2.member; //按member的顺序从大到小排序
}
如果略去最后的cmp，sort算法默认从小到大排序，但自定义的数据类型一定要重载大于号，小于号等比较运算符
6. 冒泡排序法和快速排序比较的算法
打你屁股，这么简单的问题都不认真研究一下。
冒泡排序是最慢的排序，时间复杂度是 O(n^2)。
快速排序是最快的排序。关于快速排序，我推荐你看看《代码之美》第二章：我编写过的最漂亮的代码。作者所说的最漂亮，就是指效率最高的。
--------------------------------摘自《代码之美》---------------
当我撰写关于分治（divide-and-conquer）算法的论文时，我发现C.A.R. Hoare的Quicksort算法（“Quicksort”，Computer Journal 5）无疑是各种Quicksort算法的鼻祖。这是一种解决基本问题的漂亮算法，可以用优雅的代码实现。我很喜欢这个算法，但我总是无法弄明白算法中最内层的循环。我曾经花两天的时间来调试一个使用了这个循环的复杂程序，并且几年以来，当我需要完成类似的任务时，我会很小心地复制这段代码。虽然这段代码能够解决我所遇到的问题，但我却并没有真正地理解它。
我后来从Nico Lomuto那里学到了一种优雅的划分（partitioning）模式，并且最终编写出了我能够理解，甚至能够证明的Quicksort算法。William Strunk Jr.针对英语所提出的“良好的写作风格即为简练”这条经验同样适用于代码的编写，因此我遵循了他的建议，“省略不必要的字词”（来自《The Elements of Style》一书）。我最终将大约40行左右的代码缩减为十几行的代码。因此，如果要回答“你曾编写过的最漂亮代码是什么？”这个问题，那么我的答案就是：在我编写的《Programming Pearls, Second Edition》(Addison-Wesley)一书中给出的Quichsort算法。在示例2-1中给出了用C语言编写的Quicksort函数。我们在接下来的章节中将进一步地研究和改善这个函数。
【示例】 2-1 Quicksort函数
void quicksort(int l, int u)
{ int i, m;
if (l >= u) return; 10
swap(l, randint(l, u));
m = l;
for (i = l+1; i <= u; i++)
if (x[i] < x[l])
swap(++m, i);
swap(l, m);
quicksort(l, m-1);
quicksort(m+1, u);
}
如果函数的调用形式是quicksort(0, n-1)，那么这段代码将对一个全局数组x[n]进行排序。函数的两个参数分别是将要进行排序的子数组的下标：l是较低的下标，而u是较高的下标。函数调用swap(i,j)将会交换x[i]与x[j]这两个元素。第一次交换操作将会按照均匀分布的方式在l和u之间随机地选择一个划分元素。
在《Programming Pearls》一书中包含了对Quicksort算法的详细推导以及正确性证明。在本章的剩余内容中，我将假设读者熟悉在《Programming Pearls》中所给出的Quicksort算法以及在大多数初级算法教科书中所给出的Quicksort算法。
如果你把问题改为“在你编写那些广为应用的代码中，哪一段代码是最漂亮的？”我的答案还是Quicksort算法。在我和M. D. McIlroy一起编写的一篇文章（"Engineering a sort function," Software-Practice and Experience, Vol. 23, No. 11）中指出了在原来Unix qsort函数中的一个严重的性能问题。随后，我们开始用C语言编写一个新排序函数库，并且考虑了许多不同的算法，包括合并排序（Merge Sort）和堆排序（Heap Sort）等算法。在比较了Quicksort的几种实现方案后，我们着手创建自己的Quicksort算法。在这篇文章中描述了我们如何设计出一个比这个算法的其他实现要更为清晰，速度更快以及更为健壮的新函数——部分原因是由于这个函数的代码更为短小。Gordon Bell的名言被证明是正确的：“在计算机系统中，那些最廉价，速度最快以及最为可靠的组件是不存在的。”现在，这个函数已经被使用了10多年的时间，并且没有出现任何故障。
考虑到通过缩减代码量所得到的好处，我最后以第三种方式来问自己在本章之初提出的问题。“你没有编写过的最漂亮代码是什么？”。我如何使用非常少的代码来实现大量的功能？答案还是和Quicksort有关，特别是对这个算法的性能分析。我将在下一节给出详细介绍。
2.2 事倍功半
Quicksort是一种优雅的算法，这一点有助于对这个算法进行细致的分析。大约在1980年左右，我与Tony Hoare曾经讨论过Quicksort算法的历史。他告诉我，当他最初开发出Quicksort时，他认为这种算法太简单了，不值得发表，而且直到能够分析出这种算法的预期运行时间之后，他才写出了经典的“Quicksoft”论文。
我们很容易看出，在最坏的情况下，Quicksort可能需要n2的时间来对数组元素进行排序。而在最优的情况下，它将选择中值作为划分元素，因此只需nlgn次的比较就可以完成对数组的排序。那么，对于n个不同值的随机数组来说，这个算法平均将进行多少次比较？
Hoare对于这个问题的分析非常漂亮，但不幸的是，其中所使用的数学知识超出了大多数程序员的理解范围。当我为本科生讲授Quicksort算法时，许多学生即使在费了很大的努力之后，还是无法理解其中的证明过程，这令我非常沮丧。下面，我们将从Hoare的程序开
11
始讨论，并且最后将给出一个与他的证明很接近的分析。
我们的任务是对示例2-1中的Quicksort代码进行修改，以分析在对元素值均不相同的数组进行排序时平均需要进行多少次比较。我们还将努力通过最短的代码、最短运行时间以及最小存储空间来得到最深的理解。
为了确定平均比较的次数，我们首先对程序进行修改以统计次数。因此，在内部循环进行比较之前，我们将增加变量comps的值（参见示例2-2）。
【示例2-2】 修改Quicksort的内部循环以统计比较次数。
for (i = l+1; i <= u; i++) {
comps++;
if (x[i] < x[l])
swap(++m, i);
}
如果用一个值n来运行程序，我们将会看到在程序的运行过程中总共进行了多少次比较。如果重复用n来运行程序，并且用统计的方法来分析结果，我们将得到Quicksort在对n个元素进行排序时平均使用了1.4 nlgn次的比较。
在理解程序的行为上，这是一种不错的方法。通过十三行的代码和一些实验可以反应出许多问题。这里，我们引用作家Blaise Pascal和T. S. Eliot的话，“如果我有更多的时间，那么我给你写的信就会更短。”现在，我们有充足的时间，因此就让我们来对代码进行修改，并且努力编写出更短（同时更好）的程序。
我们要做的事情就是提高这个算法的速度，并且尽量增加统计的精确度以及对程序的理解。由于内部循环总是会执行u-l次比较，因此我们可以通过在循环外部增加一个简单的操作来统计比较次数，这就可以使程序运行得更快一些。在示例2-3的Quicksort算法中给出了这个修改。
【示例2-3】 Quicksort的内部循环，将递增操作移到循环的外部
comps += u-l;
for (i = l+1; i <= u; i++)
if (x[i] < x[l])
swap(++m, i);
这个程序会对一个数组进行排序，同时统计比较的次数。不过，如果我们的目标只是统计比较的次数，那么就不需要对数组进行实际地排序。在示例2-4中去掉了对元素进行排序的“实际操作”，而只是保留了程序中各种函数调用的“框架”。
【示例2-4】将Quicksort算法的框架缩减为只进行统计
void quickcount(int l, int u)
{ int m;
if (l >= u) return;
m = randint(l, u);
comps += u-l;
quickcount(l, m-1);
quickcount(m+1, u);
}
12
这个程序能够实现我们的需求，因为Quichsort在选择划分元素时采用的是“随机”方式，并且我们假设所有的元素都是不相等的。现在，这个新程序的运行时间与n成正比，并且相对于示例2-3需要的存储空间与n成正比来说，现在所需的存储空间缩减为递归堆栈的大小，即存储空间的平均大小与lgn成正比。
虽然在实际的程序中，数组的下标（l和u）是非常重要的，但在这个框架版本中并不重要。因此，我们可以用一个表示子数组大小的整数(n)来替代这两个下标（参见示例2-5）
【示例2-5】 在Quicksort代码框架中使用一个表示子数组大小的参数
void qc(int n)
{ int m;
if (n <= 1) return;
m = randint(1, n);
comps += n-1;
qc(m-1);
qc(n-m);
}
现在，我们可以很自然地把这个过程整理为一个统计比较次数的函数，这个函数将返回在随机Quicksort算法中的比较次数。在示例2-6中给出了这个函数。
【示例2-6】 将Quicksort框架实现为一个函数
int cc(int n)
{ int m;
if (n <= 1) return 0;
m = randint(1, n);
return n-1 + cc(m-1) + cc(n-m);
}
在示例2-4、示例2-5和示例2-6中解决的都是相同的基本问题，并且所需的都是相同的运行时间和存储空间。在后面的每个示例都对这些函数的形式进行了改进，从而比这些函数更为清晰和简洁。
在定义发明家的矛盾（inventor's paradox）(How To Solve It, Princeton University Press)时，George Póllya指出“计划越宏大，成功的可能性就越大。”现在，我们就来研究在分析Quicksort时的矛盾。到目前为止，我们遇到的问题是，“当Quicksort对大小为n的数组进行一次排序时，需要进行多少次比较？”我们现在将对这个问题进行扩展，“对于大小为n的随机数组来说，Quichsort算法平均需要进行多少次的比较？”我们通过对示例2-6进行扩展以引出示例2-7。
【示例2-7】 伪码：Quicksort的平均比较次数
float c(int n)
if (n <= 1) return 0
sum = 0
for (m = 1; m <= n; m++)
sum += n-1 + c(m-1) + c(n-m)
return sum/n
如果在输入的数组中最多只有一个元素，那么Quichsort将不会进行比较，如示例2-6
13
中所示。对于更大的n，这段代码将考虑每个划分值m（从第一个元素到最后一个，每个都是等可能的）并且确定在这个元素的位置上进行划分的运行开销。然后，这段代码将统计这些开销的总和（这样就递归地解决了一个大小为m-1的问题和一个大小为n-m的问题），然后将总和除以n得到平均值并返回这个结果。
如果我们能够计算这个数值，那么将使我们实验的功能更加强大。我们现在无需对一个n值运行多次来估计平均值，而只需一个简单的实验便可以得到真实的平均值。不幸的是，实现这个功能是要付出代价的：这个程序的运行时间正比于3n（如果是自行参考（self-referential）的，那么用本章中给出的技术来分析运行时间将是一个很有趣的练习）。
示例2-7中的代码需要一定的时间开销，因为它重复计算了中间结果。当在程序中出现这种情况时，我们通常会使用动态编程来存储中间结果，从而避免重复计算。因此，我们将定义一个表t[N+1]，其中在t[n]中存储c[n]，并且按照升序来计算它的值。我们将用N来表示n的最大值，也就是进行排序的数组的大小。在示例2-8中给出了修改后的代码。
【示例2-8】 在Quicksort中使用动态编程来计算
t[0] = 0
for (n = 1; n <= N; n++)
sum = 0
for (i = 1; i <= n; i++)
sum += n-1 + t[i-1] + t[n-i]
t[n] = sum/n
这个程序只对示例2-7进行了细微的修改，即用t[n]来替换c(n)。它的运行时间将正比于N2，并且所需的存储空间正比于N。这个程序的优点之一就是：在程序执行结束时，数组t中将包含数组中从元素0到元素N的真实平均值（而不是样本均值的估计）。我们可以对这些值进行分析，从而生成在Quichsort算法中统计比较次数的计算公式。
我们现在来对程序做进一步的简化。第一步就是把n-1移到循环的外面，如示例2-9所示。
【示例2-9】 在Quicksort中把代码移到循环外面来计算
t[0] = 0
for (n = 1; n <= N; n++)
sum = 0
for (i = 1; i <= n; i++)
sum += t[i-1] + t[n-i]
t[n] = n-1 + sum/n
现在将利用对称性来对循环做进一步的调整。例如，当n为4时，内部循环计算总和为：
t[0]+t[3] + t[1]+t[2] + t[2]+t[1] + t[3]+t[0]
在上面这些组对中，第一个元素增加而第二个元素减少。因此，我们可以把总和改写为：
2 * (t[0] + t[1] + t[2] + t[3])
我们可以利用这种对称性来得到示例2-10中的Quicksort。
【示例2-10】 在Quichsort中利用了对称性来计算
t[0] = 0
14
for (n = 1; n <= N; n++)
sum = 0
for (i = 0; i < n; i++)
sum += 2 * t[i]
t[n] = n-1 + sum/n
然而，在这段代码的运行时间中同样存在着浪费，因为它重复地计算了相同的总和。此时，我们不是把前面所有的元素加在一起，而是在循环外部初始化总和并且加上下一个元素，如示例2-11所示。
【示例2-11】 在Quicksort中删除了内部循环来计算
sum = 0; t[0] = 0
for (n = 1; n <= N; n++)
sum += 2*t[n-1]
t[n] = n-1 + sum/n
这个小程序确实很有用。程序的运行时间与N成正比，对于每个从1到N的整数，程序将生成一张Quicksort的估计运行时间表。
我们可以很容易地把示例2-11用表格来实现，其中的值可以立即用于进一步的分析。在2-1给出了最初的结果行。
表2-1 示例2-11中实现的表格输出
N Sum t[n]
0 0 0
1 0 0
2 0 1
3 2 2.667
4 7.333 4.833
5 17 7.4
6 31.8 10.3
7 52.4 13.486
8 79.371 16.921
这张表中的第一行数字是用代码中的三个常量来进行初始化的。下一行（输出的第三行）的数值是通过以下公式来计算的：
A3 = A2+1 B3 = B2 + 2*C2 C3 = A2-1 + B3/A3
把这些（相应的）公式记录下来就使得这张表格变得完整了。这张表格是“我曾经编写的最漂亮代码”的很好的证据，即使用少量的代码完成大量的工作。
但是，如果我们不需要所有的值，那么情况将会是什么样？如果我们更希望通过这种来方式分析一部分数值（例如，在20到232之间所有2的指数值）呢？虽然在示例2-11中构建了完整的表格t，但它只需要使用表格中的最新值。因此，我们可以用变量t的定长空间来替代table t[]的线性空间，如示例2-12所示。
【示例2-12】 Quicksoft 计算——最终版本
sum = 0; t = 0
15
for (n = 1; n <= N; n++)
sum += 2*t
t = n-1 + sum/n
然后，我们可以插入一行代码来测试n的适应性，并且在必要时输出这些结果。
这个程序是我们漫长学习旅途的终点。通过本章所采用的方式，我们可以证明Alan Perlis的经验是正确的：“简单性并不是在复杂性之前，而是在复杂性之后” ("Epigrams on Programming," Sigplan Notices, Vol. 17, Issue 9)。
7. 题目：设计和实现描述任意一个排序算法（快速排序、冒泡排序、选择排序等）的动画。
动画？
8. 集合类的sort方法采用的什么排序算法
诸如List<T>等泛型集合类，直接提供了sort（）方法用于将集合中的元素进行排序。
但是，其前提是集合中存放的是可直接排序的基本类型，如List<int>, List<double>，如果
我们定义了一个自定义类型 Class MyClass,并创建一个自定义类型的集合如List<MyClass>，
那么无参的sort（）方法就不可用了，因为不知道如何排序了。这时就需要借助：
IComparer 和 IComparable
首先，我们来看一下c#泛型List提供的Sort方法：
泛型List类的Sort方法有四种形式，分别是
1，不带有任何参数的Sort方法----Sort()；
2，带有比较器参数的Sort方法 ----Sort(IComparer<T>)
3，带有比较代理方法参数的Sort方法----Sort(Comparison<(Of <(T>)>))
4，带有比较器参数，可以指定排序范围的Sort方法----Sort(Int32, Int32 IComparer(T))
【解析：】第一种方法
使用这种方法不是对List中的任何元素对象都可以进行排序，List中的元素对象必须继承IComparable接口，并且要实现IComparable接口中的CompareTo()方法，在CompareTo()方法中要自己实现对象的比较规则。
例如，Int32和Double都是实现了IComparable接口并重载了CompareTo方法的结构。（注：int和double都是Int32和Double的别名（alias））
【解析：】第二种方法
2，带有比较器参数的Sort方法 ----Sort(IComparer<T>)，
1）创建一个额外的比较器类：其实就相当于将排序功能中的比较操作，留个使用者来完成。这个比较操作必须在实现了IComparer接口的自定义比较类中完成；如：
class myComparer:IComparer<MyClass>
2）制定比较规则实现比较方法：因为接口中有一个用于比较的重载函数Compare，所在在比较器类中我们必须实现它，完成自己希望的比较。所谓自己希望的比较就是说自己实现自定义对象的比较规则，例如你知道自定义类MyClass中哪个属性适合用来排序，那么就选择这个属性作为整个自定义类对象的排序属性，如该类中有年龄，学号，入学日期等属性，你可以选择年龄属性作为排序属性。如：
public class myComparer:IComparer<MyClass>
{
//实现按年龄升序排列
public int Compare(MyClass x, MyClass y)
{
return (x.age.CompareTo(y.age)); //age代表年龄属性是整型，即其已支持CompareTo方法
}
}
3）使用比较器的排序方法调用：然后，在自定义类型的集合如List<MyClass> myList，上就可以进行sort排序了，如
myList.Sort(new myComparer());
【解析：】第三种方法
3，带有比较代理方法参数的Sort方法----Sort(Comparison<(Of <(T>)>))
Comparison<(Of
<(T>)>是一种泛型委托。所以，需要编写一个对象排序比较的方法，对List中的元素对象没有特殊的要求，但在比较方法中需要实现
对象比较规则，这个方法实现后，就可以把这方名字作为参数委托给List的Sort方法，Sort方法在排序时会执行这个方法对List中的对象进行比较
需要编写一个对象排序比较的方法，对List中的元素对象没有特殊的要求，但在比较方法中需要实现对象比较规则，这个方法实现后，就可以把这方名字作为参
数委托给List的Sort方法，Sort方法在排序时会执行这个方法对List中的对象进行比较
【解析：】第四种方法
4，带有比较器参数，可以指定排序范围的Sort方法----Sort(Int32, Int32 IComparer(T))
对于第四排序方法，实际是第二种比较器排序的一个扩展，在指定排序比较器的同时，指定排序范围，即List中准备排序的开始元素索引和结束元素索引