快速排序算法实现汇总
我先来贴个Erlang的实现，顺便比较不同语言的简洁程度：qsort() ->
qsort()
++ ++
qsort();
qsort([]) -> [].
楼下继续补充。
Python
def qsort(x):
def p(n):return )==n]
return len(x)>1 and qsort(p(-1)) + qsort(p(0)) + qsort(p(1)) or x
目测Erlang好简洁哦~@145-我会告诉你我是来围观的么 C语言实现：
void qsort(double list[], int beg, int end) {
int i = beg, j = end;
double pivot = list;
if (beg >= end) {
return;
}
while (i < j) {
while (i < j && list > pivot) j--;
if (i < j) list = list;
while (i < j && list < pivot) i++;
if (i < j) list = list;
}
list = pivot;
if (1 < i - 1) {
qsort(list, 1, i - 1);
}
if (i + 1 < end) {
qsort(list, i + 1, end);
}
} C++ 的code
int part(int a[],int left,int right,int index)
{int pivot=a;
swap(a,a);
int newindex=left;
for (int i=left;i<right;i++)
{if (a<pivot)
{swap(a,a);
newindex++;
}
}
swap(a,a);
return newindex;
}
void quick(int a[],int left,int right)
{ if (right>left)
{int index=rand()%(right-left+1)+left;
int nexindex=part(a,left,right,index);
quick(a,left,nexindex-1);
quick(a,nexindex+1,right);
}
} CoffeeScript实现，为了代码清晰，写的有些长：
qsort = (arr) ->
if arr.length is 0
return []
pivot = arr
le = (x for x in arr when x < pivot)
gt = (x for x in arr when x > pivot)
eq = (x for x in arr when x is pivot)
console.log le, eq, gt
qsort(le).concat eq, qsort(gt) 本帖最后由 轻舟过 于 2012-11-27 18:07 编辑
Haskell，和Erlang差不多
quicksort :: (Ord a) => ->
quicksort [] = []
quicksort (x:xs) = (quicksort ) ++ ++ (quicksort )
chenzhekl 发表于 2012-11-26 21:41 static/image/common/back.gif
C语言实现：
void qsort(double list[], int beg, int end) {
int i = beg, j = end; ...
我可不可以把你的复制一下然后说是JAVA？ 南面之君 发表于 2012-11-28 10:54 static/image/common/back.gif
我可不可以把你的复制一下然后说是JAVA？
#32！基本可以……两者太像了。不过还是希望能够使用每个语言的高级特性，尽量写出最精简的代码。 本帖最后由 南面之君 于 2012-11-28 14:23 编辑
chenzhekl 发表于 2012-11-28 11:42 static/image/common/back.gif
基本可以……两者太像了。不过还是希望能够使用每个语言的高级特性，尽量写出最精简的代码。 ...粘上一个别人写好的·
/*
* 快速排序：
* 不需要大量辅助空间，并且是通用排序算法中最快的排序算法，是基于划分的思想。
* 快速排序算法本质上是通过把一个数组递归的划分为两个子数组。
* 递归的基本步骤：
* 1. 把数组划分成以一个元素为枢纽的左右两个子数组。
* 2. 调用自身的左边和右边以步骤1递归。
* 快速排序法的核心就是递归调用划分算法，直到基值的情况，这时数组就为有序的。
* 快速排序的复杂度为：
* O(N*logN)
*
* 影响效率的最大障碍：
* 对枢纽数据的选择是影响排序的效率。例如本例子选择枢纽数据为数组的最后一个元素，
* 这么选择只是为方便，然而却造成了特殊情况时效率极度下降,降到O(n2)。这种特情况就是当数据为逆序的时候。
* 如果改变特殊情况给快速排序带来的致命影响呢，这将在下一专题中详细介绍。
*/
/**
* 定义一个数组类，封装了对自身数据的排序。
*/
class ArrayIns {
private long[] theArray;//定义数组
private int nElems;//数组中的元素个数
/**
* 初始化
* @param max
*/
public ArrayIns(int max) {
theArray = new long;
nElems = 0;
}
/**
* 为数组赋值
* @param value
*/
public void insert(long value) {
theArray = value;
nElems++;
}
/**
* 显示数组元素
*/
public void display() {
System.out.print("A=");
for (int j = 0; j < nElems; j++) {
System.out.print(theArray + " ");
}
System.out.println("");
}
/**
* 快速排序主方法
*/
public void quickSort(){
recQuickSort(0, nElems-1);
}
/**
* 快速排序需递归调用的方法
* @param left
* @param right
*/
public void recQuickSort(int left, int right) {
if (right - left <= 0) {
return;
} else {
long pivot = theArray;
int partition = partitionIt(left, right, pivot);
recQuickSort(left, partition - 1);
recQuickSort(partition + 1, right);
}
}
/**
* 快速排序划分的核心方法
* @param left
* @param right
* @param pivot
* @return
*/
public int partitionIt(int left, int right, long pivot) {
int leftPtr = left-1;
int rightPtr = right;
while (true) {
while (theArray[++leftPtr] < pivot)
;
while (rightPtr > 0 && theArray[--rightPtr] > pivot)
;
if (leftPtr >= rightPtr) {
break;
} else {
swap(leftPtr, rightPtr);
}
}
swap(leftPtr,right);
return leftPtr;
}
/**
* 交换数据中两个位置的数据
* @param dex1
* @param dex2
*/
public void swap(int dex1, int dex2) {
long temp = theArray;
theArray = theArray;
theArray = temp;
}
}
/**
* 执行算法的主类
*/
public class QuickSort1 {
public static void main(String[] args) {
int maxSize = 16;
ArrayIns arr = new ArrayIns(maxSize);
for (int j = 0; j < maxSize; j++) {
long n = (int) (java.lang.Math.random()*99);
arr.insert(n);
}
System.out.println("显示排序前数据");
arr.display();
arr.quickSort();
System.out.println("显示排序后数据");
arr.display();
}
}
/**
*
* 显示排序前数据：
* A=9 14 33 27 66 89 53 32 72 14 46 33 13 79 28 26
* 显示排序后数据：
* A=9 13 14 14 26 27 28 32 33 33 46 53 66 72 79 89
*/
/**
* 总结：
* 快速排序是常用排序中效率最高的一种排序方式。
* 但在应用中的一此特殊情况影响他的效率，这不是算法本身的问题，而是如果实现的问题。
* 已经有很好的实现方式改变一些特殊情况性能下降的问题。
*/
页:
[1]