算法（二）

1.快速排序，它的原理网上都有，我就是举个例子简单的说一下

{8，4，5，2，4，6} 这样一个无序数组，先从第0个开始取，作为基准标号，让8和其余项作对比，如果比8 小的就放在8的左边，比8大的就放在8的右边，第一次完成之后是这样的4，5，2，4，6，8；然后再次对8左边的部分进行上面的操作，取4作为基准标号，比4大的放在4的左边，比4小的放在4的右边
上代码的话可能更好理解

- (void)viewDidLoad {
    [super viewDidLoad];
    NSTimeInterval beginTime = [[NSDate date]timeIntervalSince1970];
    int  arr[9] = {1,2,3,4,6,3,2,4,8};
    [self quickSort:arr left:0 right:8];
    for (int i = 0; i < 9; i ++) {
        NSLog(@"%d",arr[i]);
    }
    NSTimeInterval endTime = [[NSDate date]timeIntervalSince1970];
    NSLog(@"时间差 = %f",endTime - beginTime);
}
- (int)getBaseNumWithArray:(int[] )arr left:(int)left right:(int)right {
    //以最左边的数为基准
    int base = arr[left];
    while (left < right) {
        //从基准右端开始遍历,从右向左开始遍历,如果右侧的数大于base,就先不动,继续向左遍历直到找到比base小的数,将它放在最左边
        while (left < right && base <= arr[right]){
            right --;
        }
        //如果小于base,那么将arr[right]放在最左边
        arr[left] = arr[right];
        //从基准左端开始遍历,从左向右开始
        while (left < right && base >= arr[left]) {
            left ++;
        }
            //如果左边的数大于base,那么将arr[left]放在最右边
            arr[right] = arr[left];
    }
   
    return left;
}
//进行递归操作
- (void)quickSort:(int[])arr left:(int)left right:(int)right {
//注意:这里要判断left<right,不然当left>right,数组中是找不到的
    if (left < right) {
        int base = [self getBaseNumWithArray:arr left:left right:right];
        // 对“基准标号“左侧的一组数值进行递归的切割，以至于将这些数值完整的排序
        [self quickSort:arr left:left right:base - 1];
        // 对“基准标号“右侧的一组数值进行递归的切割，以至于将这些数值完整的排序
        [self quickSort:arr left:base + 1 right:right];
    }
}

2. 冒泡排序 基本思想是：依次比较相邻的两个数，将小数放在前面，大数放在后面。如此重复下去，直至最终完成排序
   代码如下：

- (void)viewDidLoad {
    [super viewDidLoad];
    int  arr[9] = {1,2,3,4,6,3,2,4,8};
    [self sortArr:arr];
}
- (void)sortArr:(int[])arr {
    NSTimeInterval begin = [[NSDate date]timeIntervalSince1970];
    int t;
    for (int i = 0; i < 9; i ++) {
        for (int p = 0; p < 9; p ++) {
            if (arr[p] > arr[p+1]) {
                t = arr[p];
                arr[p] = arr[p + 1];
                arr[p + 1] = t;
            }
        }
    }
    
    for (int a = 0; a < 9; a ++) {
        NSLog(@"%d",arr[a]);
    }
    NSTimeInterval end = [[NSDate date]timeIntervalSince1970];
    NSLog(@"冒泡时间差 = %f",end - begin);
}

比较：都是同样的数组，排序所用时间快速排序时间差 = 0.000691 冒泡时间差 = 0.001359很明显，快速排序所用时间要比冒泡排序所用时间短，但是快速排序是不稳定的，为什么这么说，下面分析一下。

例如这样一个整数数组：{2,4,3,4,5},在第一次排序后，就把第二个4放在了第一个4的前面，造成两个4调换了位置，非原序这就是“不稳定”，并不是排序之后会造成错乱的不稳定。快速排序是经过验证的，并不会出现排序错误的情况。