#include<stdlib.h>
void BubbleSort(int a[], const int first, const int last)//冒泡排序
void InsertSort(int a[], const int first, const int last)//插入排序
void SelectSort(int a[], const int first, const int last)//选择排序
void MergeSort(int a[], const int p, const int r)//合并排序
void QuickSort(int a[],const int p,const int r)//快速排序
void ShellSort(int a[],const int p,const int r,const int dlta[],const int t)//希尔排序
void HeapSort(int a[],const int p, int r)//堆排序
void StoogeSort(int a[],const int p,const int r)//Stooge排序(不用)算法复杂度没算清楚
void main()
{
//插入排序算法
int a[11] = {6,4,5,3,2,1}
int dlta[]={9,5,3,2,1}
//BubbleSort(a,0,5)
//InsertSort(a,0,5)
//SelectSort(a,0,5)
//MergeSort(a,0,5)
//QuickSort(a,0,5)
//ShellSort(a,0,5,dlta,5)
HeapSort(a,0,5)
//StoogeSort(a,0,5)
for(int i=0i<=5i++)
{
printf("%d ",a[i])
}
}
/************************冒泡排序***********************/
void BubbleSort(int a[], int first, int last)
{
//实现对数组a[]中a[first]到a[last]升序的“冒泡”排序
int i,j,temp
for(i=firsti<=lasti++)
{
for(j=firstj<last-ij++)
{
if(a[j] >a[j+1])
{
temp = a[j]
a[j] = a[j+1]
a[j+1] = temp
}
}
}
}
/************************插入排序***********************/
void InsertSort(int a[], int first, int last)
{
//实现对数组a[]中a[first]到a[last]升序的“插入”排序
//最坏情况为n的平方，，多用于小数组
int i,j,temp
for(i=first+1i<=lasti++)
{
temp = a[i]
j = i - 1
while((j >= 0) &&(a[j] >temp))
{
a[j+1] = a[j]
j--
}
a[j+1] = temp
}
}
/************************选择排序***********************/
void SelectSort(int a[], int first, int last)
{
//实现对数组a[]中a[first]到a[last]升序的“选择”排序
int i, j, temp, num
for(i=firsti<lasti++)
{
num = i
for(j=i+1j<=lastj++)
{
if(a[j] <a[num])
{
num = j
}
}
if(i != num)
{
temp = a[num]
a[num] = a[i]
a[i] = temp
}
}
}
/************************合并排序***********************/
void Merge(int a[],const int p,const int q,const int r)
{
//合并排序算法中的实现合并的子程序
int iLLength,iRLength
int *L, *R, i, j, k
iLLength = q - p + 1
iRLength = r - q
L = (int *)malloc(iLLength*sizeof(int))//或者 C++中 new int[iLLength]
R = (int *)malloc(iRLength*sizeof(int))//或者 C++中 new int[iRLength]
if(L == 0 || R== 0)
{
printf("内存分配失败！！！")
return
}
for(i=0i<iLLengthi++)
{
L[i] = a[p+i]
}
for(j=0j<iRLengthj++)
{
R[j] = a[q+j+1]
}
i = 0
j = 0
for(k=pk<=rk++)
{
if((i<iLLength) &&(j<iRLength) &&(L[i]<=R[j]) || (j == iRLength))
{
a[k] = L[i]
i++
}
else if(j<iRLength)
{
a[k] = R[j]
j++
}
}
free(R)free(L)
}
void MergeSort(int a[],const int p,const int r)
{
//合并排序算法-主程序
//n*lg(n),系数较小
int q
if(p<r)
{
q = (p+r)/2
MergeSort(a,p,q)
MergeSort(a,q+1,r)
Merge(a,p,q,r)
}
}
/************************Stooge排序***********************/
void StoogeSort(int a[],const int p,const int r)
{
//Stooge算法
int temp, k
if(a[p]>a[r])
{
temp= a[p]
a[p]= a[r]
a[r]= temp
}
if((p+1) >= r)
{
return
}
k = (r-p+1)/3
StoogeSort(a,p,r-k)
StoogeSort(a,p+k,r)
StoogeSort(a,p,r-k)
}
/************************快速排序*********************/
int QuickPartition(int a[],const int p,const int r)
{
//快速排序的(关键)分治过程
int temp, x, i, j
x = a[r]
i = p - 1
for(j=pj<rj++)
{
if(a[j] <= x)
{
i = i + 1
temp = a[i]
a[i] = a[j]
a[j] = temp
}
}
temp = a[i+1]
a[i+1] = a[r]
a[r] = temp
return (i+1)
}
/*
void QuickSort(int a[],const int p,const int r)
{
//快速排序算法-主程序
//与下面的“尾递归实现方法”比较，缺点：右边数组的递归不是必须的，增加了运行堆栈深度和调用开销
int q
if(p <r)
{
q = QuickPartition(a, p, r)
QuickSort(a, p, q-1)
QuickSort(a, q+1, r)
}
}
*/
void QuickSort(int a[],int p,const int r)
{
//快速排序算法-主程序
//“尾递归实现方法”是对上面的快速排序主程序实现的一种优化
//系数较小,常用大数组
int q
while(p <r)
{
q = QuickPartition(a, p, r)
QuickSort(a, p, q-1)
p = q + 1
}
}
/************************希尔排序**********************/
void ShellInsert(int a[],const int p,const int r, int dk)
{
//希尔排序算法的关键子程序-插入排序子程序
int i, j, temp
for(i=p+dki<=ri++)
{
if(a[i] <a[i-dk])
{
temp = a[i]
for(j=i-dk((j>=0) &&(temp <a[j]))j -= dk)
{
a[j+dk] = a[j]
}
a[j+dk] = temp
}
}
}
void ShellSort(int a[],const int p,const int r,const int dlta[],const int t)
{
//希尔排序算法-主程序
//按增量序列dlta[]中的前t个增量，实现对数组a[]中a[p]到a[r]的排序
//dlta[]可能取值如：1,2,3,5,9dala[k]=2^(t-k+1)-1 其中0<=k<=t<=ld(b-1)
//增量序列的最后一个值必须是1
//增量序列中的值没有除1以外的因子， 其精确时间复杂度：数学上尚未解决的难题
int k
for(k=0k<tk++)
{
ShellInsert(a,p,r,dlta[k])
}
}
/************************堆排序***********************/
//堆排序，不如快速排序
//但是可用其来实现“优先级队列”
int Parent(int i)
{
return ((i+1)/2-1)
}
int Right(int i)
{
return (2*(i+1)-1)
}
int Left(int i)
{
return (2*(i+1))
}
void Max_Heapify(int a[],const int hplast,const int i)
{
int l, r,largest,temp
l = Left(i)
r = Right(i)
largest = ((l<=hplast) &&(a[l]>a[i])) ? l:i
if((r<=hplast) &&(a[r]>a[largest]))
{
largest = r
}
if(largest != i)
{
temp = a[i]
a[i] = a[largest]
a[largest] = temp
Max_Heapify(a,hplast,largest)
}
}
void Build_Max_Heap(int a[],const int p, const int r)
{
int i
for(i = (p+r)/2i>=pi--)
{
Max_Heapify(a,r,i)
}
}
void HeapSort(int a[],const int p, int r)
{
int i,temp
Build_Max_Heap(a,p,r)
for(i = ri >pi--)
{
temp = a[p]
a[p] = a[i]
a[i] = temp
r -= 1
Max_Heapify(a,r,0)
}
}
为什么要设计一门新语言？原因无非就两个，要么旧的语言实在是让人受不了，要么是针对领域设计的专用语言。后一种我就不讲了，因为如果没有具体的领域知识的话，这种东西永远都做不好（譬如SQL永远不可能出自一个数据库很烂的人手里），基本上这不是什么语言设计的问题。所以这个系列只会针对前一种情况——也就是设计一门通用的语言。通用的语言其实也有自己的“领域”，只是太多了，所以被淡化了。纵观历史，你让一个只做过少量的领域的人去设计一门语言，如果他没有受过程序设计语言理论的系统教育，那只能做出屎。譬如说go就是其中一个——虽然他爹很牛逼，但反正不包含“设计语言”这个事情。因此，在21世纪你还要做一门语言，无非就是对所有的通用语言都不满意，所以你想自己做一个。不满意体现在什么方面？譬如说C#的原因可能就是他爹不够帅啦，譬如说C++的原因可能就是自己智商太低hold不住啦，譬如说Haskell的原因可能就是用的人太少招不到人啦，譬如说C的原因可能就是实在是无法完成人和抽象所以没有linus的水平的人都会把C语言写成屎但是你又招不到linus啦，总之有各种各样的原因。不过排除使用者的智商因素来讲，其实有几个语言我还是很欣赏的——C++、C#、Haskell、Rust和Ruby。如果要我给全世界的语言排名，前五名反正是这五个，虽然他们之间可能很难决出胜负。不过就算如此，其实这些语言也有一些让我不爽的地方，让我一直很想做一个新的语言（来给自己用（？）），证据就是——“看我的博客”。
那么。一个好的语言的好，体现在什么方面呢？一直以来，人们都觉得，只有库好用，语言才会好用。其实这完全是颠倒了因果关系，如果没有好用的语法，怎么能写出好用的库呢？要找例子也很简单，只要比较一下Java和C#就够了。C#的库之所以好用，跟他语言的表达能力强是分不开的，譬如说linq（，to xml，to sql，to parser，etc），譬如说WCF（仅考虑易用性部分），譬如说WPF。Java能写得出来这些库吗？硬要写还是可以写的，但是你会发现你无论如何都没办法把他们做到用起来很顺手的样子，其实这都是因为Java的语法垃圾造成的。这个时候可以抬头看一看我上面列出来的五种语言，他们的特点都是——因为语法的原因，库用起来特别爽。
当然，这并不要求所有的人都应该把语言学习到可以去写库。程序员的分布也是跟金字塔的结构一样的，库让少数人去写就好了，大多数人尽管用，也不用学那么多，除非你们想成为写库的那些。不过最近有一个很不好的风气，就是有些人觉得一个语言难到自己无法【轻松】成为写库的人，就开始说他这里不好那里不好了，具体都是谁我就不点名了，大家都知道，呵呵呵。
好的语言，除了库写起来又容易又好用以外，还有两个重要的特点：容易学，容易分析。关于容易学这一点，其实不是说，你随便看一看就能学会，而是说，只要你掌握了门道，很多未知的特性你都可以猜中。这就有一个语法的一致性问题在里面了。语法的一致性问题，是一个很容易让人忽略的问题，因为所有因为语法的一致性不好而引发的错误，原因都特别的隐晦，很难一眼看出来。这里我为了让大家可以建立起这个概念，我来举几个例子。
第一个例子是我们喜闻乐见的C语言的指针变量定义啦：
int a, *b, **c
相信很多人都被这种东西坑过，所以很多教科书都告诉我们，当定义一个变量的时候，类型最后的那些星号都要写在变量前面，避免让人误解。所以很多人都会想，为什么要设计成这样呢，这明显就是挖个坑让人往下跳嘛。但是在实际上，这是一个语法的一致性好的例子，至于为什么他是个坑，问题在别的地方。
我们都知道，当一个变量b是一个指向int的指针的时候，*b的结果就是一个int。定义一个变量int a也等于在说“定义a是一个int”。那我们来看上面那个变量声明：int *b。这究竟是在说什么呢？其实真正的意思是“定义*b是一个int”。这种“定义和使用相一致”的方法其实正是我们要推崇的。C语言的函数定义参数用逗号分隔，调用的时候也用逗号分隔，这是好的。Pascal语言的函数定义参数用分号分隔，调用的时候用逗号分隔，这个一致性就少了一点。
看到这里你可能会说，你怎么知道C语言他爹就是这么想的呢？我自己觉得如果他不是这么想的估计也不会差到哪里去，因为还有下面一个例子：
int F(int a, int b)
int (*f)(int a, int b)
这也是一个“定义和使用相一致”的例子。就第一行代码来说，我们要如何看待“int F(int a, int b)”这个写法呢？其实跟上面一样，他说的是“定义F(a, b)的结果为int”。至于a和b是什么，他也告诉你：定义a为int，b也为int。所以等价的，下面这一行也是“定义(*f)(a, b)的结果为int”。函数类型其实也是可以不写参数名的，不过我们还是鼓励把参数名写进去，这样Visual Studio的intellisense会让你在敲“(”的时候把参数名给你列出来，你看到了提示，有时候就不需要回去翻源代码了。
关于C语言的“定义和使用相一致”还有最后一个例子，这个例子也是很美妙的：
int a
typedef int a
int (*f)(int a, int b)
typedef int (*f)(int a, int b)
typedef是这样的一个关键字：他把一个符号从变量给修改成了类型。所以每当你需要给一个类型名一个名字的时候，就先想一想，怎么定义一个这个类型的变量，写出来之后往前面加个typedef，事情就完成了。
不过说实话，就一致性来讲，C语言也就到此为止了。至于说为什么，因为上面这几条看起来很美好的“定义和使用相一致”的规则是不能组合的，譬如说看下面这一行代码：
typedef int(__stdcall*f[10])(int(*a)(int, int))
这究竟是个什么东西呢，谁看得清楚呀！而且这也没办法用上面的方法来解释了。究其原因，就是C语言采用的这种“定义和使用相一致”的手法刚好是一种解方程的手法。譬如说int *b定义了“*b是int”，那b是什么呢，我们看到了之后，都得想一想。人类的直觉是有话直说开门见山，所以如果我们知道int*是int的指针，那么int* b也就很清楚了——“b是int的指针”。
因为C语言的这种做法违反了人类的直觉，所以这条本来很好的原则，采用了错误的方法来实现，结果就导致了“坑”的出现。因为大家都习惯“int* a”，然后C语言告诉大家其实正确的做法是“int *a”，那么当你接连的出现两三个变量的时候，问题就来了，你就掉坑里去了。
这个时候我们再回头看一看上面那一段长长的函数指针数组变量的声明，会发现其实在这种时候，C语言还是希望你把它看成“int* b”的这种形式的：f是一个数组，数组返回了一个函数指针，函数返回int，函数的参数是int(*a)(int, int)所以他还是一个函数指针。
我们为什么会觉得C语言在这一个知识点上特别的难学，就是因为他同时混用了两种原则来设计语法。那你说好的设计是什么呢？让我们来看看一些其它的语言的作法：
C++:
function<int __stdcall(function<int(int, int)>)>f[10]
C#:
Func<Func<int, int, int>, int>[] f
Haskell:
f :: [(int->int->int)->int]
Pascal:
var f : array[0..9] of function(a : function(x : integery : integer):integer):integer
这些语言的做法，虽然并没有遵守“定义和使用相一致”的原则，但是他们比C语言好的地方在于，他们只采用一种原则——这就比好的和坏的混在一起要强多了（这一点go也是，做得比C语言更糟糕）。
当然，上面这个说法对Haskell来说其实并不公平。Haskell是一种带有完全类型推导的语言，他不认为类型声明是声明的一部分，他把类型声明当成是“提示”的一部分。所以实际上当你真的需要一个这种复杂结构的函数的时候，实际上你并不会真的去把它的类型写出来，而是通过写一个正确的函数体，然后让Haskell编译器帮你推导出正确的类型。我来举个例子：
superApply fs x = (foldr id (.) fs) x
关于foldr有一个很好的理解方法，譬如说foldr 0 (+) [1,2,3,4]说的就是1 + (2 + (3 + (4 + 0)))。而(.)其实是一个把两个函数合并成一个的函数：f (.) g = \x->f(g( x ))。所以上述代码的意思就是，如果我有下面的三个函数：
add1 x = x + 1
mul2 x = x * 2
sqr x = x * x
那么当我写下下面的代码的时候：
superApply [sqr, mul2, add1] 1
的时候，他做的其实是sqr(mul2(add1(1)) = ((1+1)*2) * ((1+1)*2) = 16。当然，Haskell还可以写得更直白：
superApply [(\x->x*x), (*2), (+1)] 1
Haskell代码的简洁程度真是丧心病狂啊，因为如果我们要用C++来写出对应的东西的话（C语言的参数无法是一个带长度的数组类型所以其实是写不出等价的东西的），会变成下面这个样子：
template<typename T>
T SuperApply(const vector<function<T(T)>>&fs, const T&x)
{
T result = x
for(int i=fs.size()-1i>=0i--)
{
result = fs[i](result)
}
return result
}
C++不仅要把每一个步骤写得很清楚，而且还要把类型描述出来，整个代码就变得特别的混乱。除此之外，C++还没办法跟Haskell一样吧三个函数直接搞成一个vector然后送进这个SuperApply里面直接调用。当然有人会说，这还不是因为Haskell里面有foldr嘛。那让我们来看看同样有foldr（reverse + aggregate = foldr）的C#会怎么写：
T SuperApply<T>(Func<T, T>[] fs, T x)
{
return (fs
.Reverse()
.Aggregate(x=>x, (a, b)=>y=>b(a(y)))
)(x)
}
C#基本上已经达到跟Haskell一样的描述过程了，而且也可以写出下面的代码了，就是无论声明和使用的语法的噪音稍微有点大……
SuperApply(new Func<T, T>[]{
x=>x*x,
x=>x*2,
x=>x+1
}, 1)
为什么要在讨论语法的一致性的时候说这些问题呢，在这里我想向大家展示Haskell的另一种“定义和使用相一致”的做法。Haskell整个语言都要用pattern matching去理解，所以上面的这段代码
superApply fs x = (foldr id (.) fs) x
说的是，凡是你出现类似superApply a b的这种“pattern”，你都可以把它当成(foldr id (.) a) b来看。譬如说
superApply [(\x->x*x), (*2), (+1)] 1
其实就是
(foldr id (.) [(\x->x*x), (*2), (+1)]) 1
只要superApply指的是这个函数，那无论在什么上下文里面，你都可以放心的做这种替换而程序的意思绝对不会有变化——这就是haskell的带有一致性的原则。那让我们来看看Haskell是如何执行他这个一致性的。在这里我们需要知道一个东西，就是如果我们有一个操作符+，那我们要把+当成函数来看，我们就要写(+)。如果我们有一个函数f，如果我们要把它当成操作符来看，那就要写成`f`（这是按键！左边的那个符号）。因此Haskell其实允许我们做下面的声明：
(Point x y) + (Point z w) = Point (x+z) (y+w)
(+) (Point x y) (Point z w) = Point (x+z) (y+w)
(Point x y) `Add` (Point z w) = Point (x+z) (y+w)
Add (Point x y) (Point z w) = Point (x+z) (y+w)
斐波那契数列的简单形式甚至还可以这么写：
f 1 = 1
f 2 = 1
f (n+2) = f(n+1) + f(n)
甚至连递归都可以写成：
GetListLength [] = 0
GetListLength (x:xs) = 1 + GetListLength xs
Haskell到处都贯彻了“函数和操作符的替换关系”和“pattern matching”两个原则来做“定义和实现相一致”的基础，从而实现了一个比C语言那个做了一半的混乱的原则要好得多的原则。
有些人可能会说，Haskell写递归这么容易，那会不会因为鼓励人们写递归，而整个程序充满了递归，很容易stack overflow或者降低运行效率呢？在这里你可以往上翻，在这篇文章的前面有一句话“好的语言，除了库写起来又容易又好用以外，还有两个重要的特点：容易学，容易分析。”，这在Haskell里面体现得淋漓尽致。
我们知道循环就是尾递归，所以如果我们把代码写成尾递归，那Haskell的编译器就会识别出来，从而在生成x86代码的时候把它处理成循环。一个尾递归递归函数的退出点，要么是一个不包含自身函数调用的表达式，要么就是用自身函数来和其它参数来调用。听起来比较拗口，不过说白了其实就是：
GetListLength_ [] c = c
GetListLength_ (x:xs) c = GetListLength_ xs (c+1)
GetListLength xs = GetListLength_ xs 0
当你写出这样的代码的时候，Haskell把你的代码编译了之后，就会真的输出一个循环，从而上面的担心都一扫而空。
实际上，有很多性能测试都表明，在大多数平台上，Haskell的速度也不会被C/C++慢超过一倍的同时，要远比go的性能高出许多。在Windows上，函数式语言最快的是F#。Linux上则是Scala。Haskell一直都是第二名，但是只比第一名慢一点点。
为了不让文章太长，好分成若干次发布，每次间隔都较短，所以今天的坑我只想多讲一个——C++的指针的坑。剩下的坑留到下一篇文章里面。下面要讲的这个坑，如果不是在粉丝群里面被问了，我还不知道有人会这么做：
class Base
{
...
}
class Derived : public Base
{
...
}
Base* bs = new Derived[10]
delete[] bs
我想说，这完全是C++兼容C语言，然后让C语言给坑了。其实这个问题在C语言里面是不会出现的，因为C语言的指针其实说白了只有一种：char*。很多C语言的函数都接受char*，void*还是后来才有的。C语言操作指针用的malloc和free，其实也是把他当char*在看。所以当你malloc了一个东西，然后cast成你需要的类型，最后free掉，这一步cast存在不存在对于free能否正确执行来说是没有区别的。
但是事情到了C++就不一样了。C++有继承，有了继承就有指针的隐式类型转换。于是看上面的代码，我们new[]了一个指针是Derived*类型的，然后隐式转换到了Base*。最后我们拿他delete[]，因为delete[]需要调用析构函数，但是Base*类型的指针式不能正确计算出Derived数组的10个析构函数需要的this指针的位置的，所以在这个时候，代码就完蛋了（如果没完蛋，那只是巧合）。
为了兼容C语言，“new[]的指针需要delete[]”和“子类指针可以转父类指针”的两条规则成功的冲突到了一起。实际上，如果需要解决这种问题，那类型应该怎么改呢？其实我们可以跟C#一样引入Derived[]的这种指针类型。这还是new[]出来的东西，C++里面也可以要求delete[]，但是区别是他再也不能转成Base[]了。只可惜，T[]这种类型被C语言占用了，在函数参数类型里面当T*用。C语言浪费语法罪该万死呀……
.all?这是一个ruby方法，他的返回结果只有两个，true或者false，判断的是数组中每一个元素都是true的就返回true，只要有一个不是true就返回false，如[nil,22].all?返回的就是false。还有就是判断数组遍历运算过程中，每一个结果是不是true，如[1,2,3].all?{|w| w >1}这个的结果就是false。你的例子中，作为判断对象的是一个空数组，不执行后面的代码，也没有一个元素是false的，所以返回的是true，这是我的见解
