hangscer

scala写算法-快排

2017/02/12

快排算法很经典,今天用scala的函数式思维来整理一下并实现:

1
2
3
4
5
def qsort(list: List[Int]):List[Int]=list match {
case Nil=>Nil
case ::(pivot,t)=>qsort(t.filter(_<=pivot)) ++ List(pivot) ++ qsort(t.filter(_>pivot))
}
println(qsort(List(1,32,4,5,2,3,5,6,7,33)))

ok
以下是C语言所写的快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void quickSort(int* array,int left,int right){
int i,j,t;
int pivot=0;
if(left>right) //边界条件
return;
pivot=array[left]; //选择基数
i=left; //i 哨兵
j=right; // j 哨兵
while(i!=j){
while(a[j]>=pivot && i<j) // 从右边向左找出比pivot小的数
j--;
while(a[i]<=pivot && i<j) //从左向右找出比pivot大的数
i++;
if(i<j){ //还没过中线 交换
t=a[i];
a[i]=a[j];
a[j]=t;
}
}
a[left]=a[i]; //把基数换到中间去
a[i]=pivot; //
quickSort(array,left,i-1);
quickSort(array,i+1,right);
}