快速排序(oc/java/Python/scala)

在讲解快速排序之前，先来说一说递归和栈。

递归

通俗地讲，一个函数调用自己本身，就是递归。每个递归函数都有两部分：基线条件(函数不再调用自己)和递归条件(函数调用自己)。
示例：

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