算法

一. 排序算法

1.快速排序

快速排序是对冒泡排序的一种改进. 快速排序: 对于给定的一组数据, 选定其中的一个(一般选择第1个)作为key, 比key大的放右侧, 比key小的放左侧, 然后对其左侧, 右侧数据依次递归做这种操作, 直到每部分的数据个数为1为止.
Swift5.0的部分代码如下:

 func quickSort(array: NSMutableArray, left: Int, right: Int) {
        let a: NSMutableArray = array
        
        if left >= right {return}
        var i = left
        var j = right
        let key = array[left] as! Int
        while i < j {
            while (i < j && key <= a[j] as! Int) {j-=1}
            a[i] = a[j]
            while (i < j && key >= a[i] as! Int) {i+=1}
            a[j] = a[i]
        }
        
        a[i] = key

        quickSort(array: a, left: left, right: i - 1)
        quickSort(array: a, left: i + 1, right: right)
    }

经过上面的递归操作后, 数组里面的数据成为有序(从小到大)

下面给出一组示例 6, 2, 7, 3, 8, 9 的排序过程:

WechatIMG192.jpeg

二. 动态规划

1.最大字段和

给出一段序列，选出其中连续且非空的一段使得这段和最大.

- (void)maxSum{
    /**
     这是经典的一个线性动态规划的问题,当然也可以用其他算法求解
     在整个动态查询的过程中,主要理解f[i]的含义
     f[i] : 前i个数字中包含第i个数字的最大子段和
     那么这个问题就成了寻找前i个数字的最大子段和的最大值
     */
    int a[9] = {1, 2, -4, 4, 10, -3, 4, -5, 1}, f[9] = {0};
    int max = -999999;
    f[0] = a[0];
    for(int i = 1; i < 9; i++)
    {
        // 线性动规方程式
        f[i] = MAX(f[i-1] + a[i], a[i]);
        max = MAX(max, f[i]);
        
        printf("%d-----%d\n",i,max);
    }
    printf("%d",max);
}

代码下载地址: https://gitee.com/BookNo1/Algorithm