在讲解快速排序之前，先来说一说递归和栈。
递归
通俗地讲，一个函数调用自己本身，就是递归。每个递归函数都有两部分：基线条件(函数不再调用自己)和递归条件(函数调用自己)。
示例：
def countdown(i):
print i
#基线条件
if i <= 0:
return
#递归条件
else:
countdown(i-1)
栈
栈：仅允许在表的一端进行插入和删除运算的线性表。栈有两种操作：入栈和出栈。所有函数调用都进入调用栈，在使用递归函数时，可能使得调用栈很长，这将占用大量的内存。
快速排序
1.分而治之(divide and conquer)——一种著名的递归式问题解决方法，有兴趣的自行百度学习。
2.百度百科对快速排序的解释：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
3.步骤：
1.选择基准值
2.将数组分成两个子数组:小于基准值的元素组成的数组和大于基准值的元素组成的数组。
3.对子数组进行快速排序。
scala实现代码：
object KuaiSu{
def main(args: Array[String]) = {
var sortArray = Array(45, 26, 34, 2, 888, 54, 23, 45, 76, 2);
sort(sortArray,0,9);
for(i <- sortArray){
println(i);
}
}
def sort(array:Array[Int],low:Int,high:Int):Unit={
if(low < high){
var l:Int = low;
var h:Int = high;
var base:Int = array(low);
while(l<h){
while(l<h && array(h)>=base){
h = h - 1;
}
if(l < h){
array(l) = array(h);
l = l + 1;
}
while(l< h && array(l) < base){
l= l + 1;
}
if(l < h){
array(h) = array(l);
h = h - 1;
}
}
array(l) = base;
sort(array,low,l-1);
sort(array,l+1,high);
}
}
}
Java代码实现：
import java.util.Arrays;
public class MyClass {
public static void main(String[] args){
int[] sortArray = {45, 26, 34, 2, 888, 54, 23, 45, 76, 2};
sort(sortArray,0,9);
System.out.println(Arrays.toString(sortArray));
}
private static void sort(int arr[],int low,int high){
//当数组长度大于1
if(low < high){
int l = low;
int h = high;
int base = arr[low];
//循环结束将数组分成2部分
while (l<h){
//右-->左，查找小于base的数
while(l<h && arr[h]>=base){
h--;
}
if(l<h){
arr[l] = arr[h];
l++;
}
//左-->右，查找大于base的数
while (l<h && arr[l] < base){
l++;
}
if(l<h){
arr[h] = arr[l];
h--;
}
}
//填坑
arr[l] = base;
//递归
sort(arr,low,l-1);
sort(arr,l+1,high);
}
}
}
结果图：
SYJ.png
Python实现代码一：
def quickSort(L,low,high):
l = low
h = high
if l >= h:
return L
base = L[l]
while l < h:
while l<h and L[h]>=base:
h = h-1
if l<h:
L[l] = L[h]
l=l+1
while l<h and L[l] <= base:
l = l+1
if l<h:
L[h] = L[l]
h=h-1
L[l] = base
quickSort(L,low,l-1)
quickSort(L,h+1,high)
return L
x = [45, 26, 34, 2, 888, 54, 23, 45, 76, 2]
print(quickSort(x,0,9))
Python实现代码二：
def quickSort(array):
if len(array)<2:
return array
else:
base = array[0]
#小于等于基准值的元素组成的数组
less = [i for i in array[1:] if i<=base]
#大于基准值的元素组成的数组
greater = [i for i in array[1:] if i> base]
#将数组串起来
return quickSort(less)+[base]+quickSort(greater)
print(quickSort([45, 26, 34, 2, 888, 54, 23, 45, 76, 2]))
结果图：
SYJ.png
OC实现代码：
#import "ViewController.h"
@implementation ViewController
- (void)viewDidLoad {
[super viewDidLoad];
NSMutableArray *array = [[NSMutableArray alloc] initWithObjects:@45, @26, @34, @2, @888, @54, @23, @45, @76, @2, nil];
[self kuaisuArray:array andLow:0 andHigh:9];
NSLog(@"%@",array);
}
-(void)kuaisuArray:(NSMutableArray*)array andLow:(NSInteger)low andHigh:(NSInteger)high{
if(low < high){
NSInteger l = low;
NSInteger h = high;
int base = [array[low] intValue];
while(l<h){
//右-->左，查找小于base的数
while(l<h && [array[h] intValue]>=base){
h--;
}
if(l<h){
array[l] = array[h];
l++;
}
//左-->右，查找大于base的数
while (l<h && [array[l] intValue] < base){
l++;
}
if(l<h){
array[h] = array[l];
h--;
}
}
array[l] = [NSNumber numberWithInt:base];
[self kuaisuArray:array andLow:low andHigh:l-1];
[self kuaisuArray:array andLow:l+1 andHigh:high];
}
}
@end
结果图：
SYJ.png
