烧脑体操之基本算法设计

作者: _onePiece | 来源:发表于2017-04-17 21:39 被阅读10次

本文排序全部基于升序,为了方便阅读全部基于C,代码将全部部署到github上。(为方便各位看官调试，代码中的打印数组PrintArr的部分我就没有去掉)
算法一途，须亲力亲为，实践出真知，真正到写代码的时候你知道，你以为你知道的其实不知道。文中有些代码我是在百度百科copy过来的（求轻虐），但是我确确实实的自己过了一遍，本文中有些代码着实精辟。
还是原来的配方，还是原来的味道。文章还没有完成（好吧，原谅我不要脸，就开始发表），确实要写篇文章要花些精力，也只有空闲的时间才能写写，求赞求赞求赞，重要的事说三遍。。。。。
另外，我将会在本文完成后找一些题目，以供练习，当然也欢迎各位同学投稿，也希望有大神可能的话能够抽出一点珍贵的时间不吝赐教，灰常感谢，灰常感谢，灰常感谢。

一、蛮力法

蛮力法（brute force method，也称穷举法或枚举法）的设计思想：蛮力法是一种简单直接地解决问题的方法，常常直接基于问题的描述，所以，蛮力法也是最容易应用的方法。蛮力法所依赖的基本技术是遍历（traversal，也称扫描），即采用一定的策略依次处理带求解问题的所有元素，从而找出问题的解。

1.1冒泡排序（bubble sort）

【思想】两两比较相邻的记录，如果反序则交换，直到没有反序为止。
如下给了一个冒泡排序的例子，具体的排序过程如下：
（1）将整个待排序的记录序列划分为有序区和无序区，初始时有序区为空，无序区包括所有待排序的记录。
（2）对无序区依次比较相邻的记录，若反序则交换，从而使较小的记录向前移，较大的记录向后移。
（3）重复（2）直到没有反序记录。

【排序过程】
表格中的加粗部分为有序区

序列	排序结果
第 0 次排序	38--48--65--97--76--13--27--49
第 1 次排序	38--48--65--76--13--27--49--97
第 2 次排序	38--48--65--13--27--49--76--97
第 3 次排序	38--48--13--27--49--65--76--97
第 4 次排序	38--13--27--48--49--65--76--97
第 5 次排序	13--27--38--48--49--65--76--97
第 6 次排序	13--27--38--48--49--65--76--97
第 7 次排序	13--27--38--48--49--65--76--97

【算法实现】

/**
 冒泡排序

 @param arr 数组
 @param len 数组长度
 */
void BubbleSort(int *arr, int len) {
    int i, j, max;
    printf("*****冒泡排序*****\n");
    for (i = 0; i < len - 1; i++) {
        for (j = 0; j < len - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                max = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = max;
            }
        }
        printf("第%d次内部循环结果为", i + 1);
        PrintArr(arr, len);
        printf("\n");
    }
}


/**
 优化的冒泡排序

 @param arr 数组
 @param len 数组长度
 */
void OptimizeBubbleSort(int *arr, int len) {
    //设置标志位，检查在一次遍历的过程中是否有交换，如果没有说明数组为有序
    int exchange = len - 1;
    int max;
    while (exchange != 0) {
        exchange = 0;
        printf("*****优化的冒泡排序*****\n");
        for (int j = 0; j < len - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                max = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = max;
                exchange = j;
            }
            printf("第%d次内部循环结果为", j + 1);
            PrintArr(arr, len);
            printf("\n");
        }
    }
}

【算法分析】

1.2选择排序

【思想】
第i趟排序在无序序列人R(i)~R(n)中找到最小的记录，并和第i个记录交换作为有序序列的第i个记录。如下给了一个选择排序的例子，具体的排序过程如下：
（1）将整个待排序的记录序列划分为有序区和无序区，初始时有序区为空，无序区包括所有待排序的记录。
（2）在无序区查找最小的记录，将它与无序区的第一个记录交换，使得有序区扩大一个记录，无序区较少一个记录。
（3）重复（2）直到无序区只有一个记录为止。

【过程】
表格中的加粗部分为有序区

序列	排序结果
第 0 次排序	38--48--65--97--76--13--27--49
第 1 次排序	13--38--65--97--76--48--27--49
第 2 次排序	13--27--65--97--76--48--38--49
第 3 次排序	13--27--38--97--76--48--65--49
第 4 次排序	13--27--38--48--76--97--65--49
第 5 次排序	13--27--38--48--49--97--65--76
第 6 次排序	13--27--38--48--49--65--97--76
第 7 次排序	13--27--38--48--49--65--76--97

【算法实现】

/**
 选择排序

 @param arr 数组
 @param len 数组长度
 */
void SelectSort(int *arr, int len) {
    int i, j, minOfIndex;
    printf("*****选择排序*****\n");
    for (i = 0; i < len - 1; i++) {
        minOfIndex = i;
        //在无序区查找最小记录
        for (j = i + 1; j < len; j++) {
            if (arr[j] < arr[minOfIndex]) {
                minOfIndex = j;
            }
        }
        //交换记录
        if (minOfIndex != i) {
            int temp = arr[i];
            arr[i] = arr[minOfIndex];
            arr[minOfIndex] = temp;
        }
        printf("第%d次内部循环结果为", i + 1);
        PrintArr(arr, len);
        printf("\n");
    }
}

【算法分析】
选择排序是在冒泡排序的基础上进行优化的一种蛮力法排序，不同的是选择排序只有在每一次的内部循环的过程中最多只有一次交换，而冒泡排序最多有n-i（i为第i次的循环）次交换，所以选择排序呢在空间复杂度上有由于冒泡排序。

二、分治法

分治法分而治之，分：将问题分解为规模更小的子问题；治：将这些规模更小的之问题逐个击破；合：将已解决的子问题合并，得出母问题的解。

2.1归并排序

【思想】
归并排序首先执行划分过程，将序列划分为两个子序列，如果子序列的长度为1，则划分结束，否则继续执行划分，结果将具有n个待排序的记录划分为n个长度为1的有序子序列；然后进行两两合并，得到floor(n/2）个长度为2的有序子序列，在进行合并，......直到得到长度为n的有序序列。

【排序过程】

【算法实现】

/**
 归并排序

 @param sourceArr 待排序数组
 @param tempArr 临时数组
 @param startIndex 起始索引
 @param midIndex 中间索引
 @param endIndex 末尾索引
 */
void Merge(int sourceArr[],int tempArr[], int startIndex, int midIndex, int endIndex) {
    int i = startIndex, j=midIndex+1, k = startIndex;
    //将左右两边的数中最小的数依次加入临时数组
    while(i!=midIndex+1 && j!=endIndex+1) {
        if(sourceArr[i] > sourceArr[j])
            tempArr[k++] = sourceArr[j++];
        else
            tempArr[k++] = sourceArr[i++];
    }
    //避免最后一个数没有加入到临时数组中
    while(i != midIndex+1)
        tempArr[k++] = sourceArr[i++];
    while(j != endIndex+1)
        tempArr[k++] = sourceArr[j++];
    for(i=startIndex; i<=endIndex; i++)
        sourceArr[i] = tempArr[i];
}

//内部使用递归
void MergeSort(int sourceArr[], int tempArr[], int startIndex, int endIndex) {
    int midIndex;
    if(startIndex < endIndex) {
        midIndex = (startIndex + endIndex) / 2;
        MergeSort(sourceArr, tempArr, startIndex, midIndex);
        MergeSort(sourceArr, tempArr, midIndex+1, endIndex);
        Merge(sourceArr, tempArr, startIndex, midIndex, endIndex);
    }
}

【算法分析】

2.2快速排序

【思想】
首先对待排序记录序列进行划分，划分的轴值应该遵循平衡子问题的原则，使划分后的两个子序列的长度尽量相等，这是决定快速排序算法时间的性能关键。轴值的选择有很多方法，例如可以随机选出一个记录作为轴值，从而期望划分是较平衡的

【排序过程】

【算法实现】

/**
 快速排序

 @param arr 数组
 @param left 数组左边left个元素
 @param right 数组右边right个元素
 */
void QuickSort(int *arr, int left, int right) {
    //如果左边索引大于或者等于右边的索引就代表已经整理完成一个组了
    if(left >= right){
        return ;
    }
    int i = left;
    int j = right;
    int key = arr[left];
    /*控制在当组内寻找一遍*/
    while(i < j){
        //而寻找结束的条件就是，
        //1，找到一个小于或者大于key的数（大于或小于取决于你想升序还是降序）
        //2，没有符合条件1的，并且i与j的大小没有反转
        while(i < j && key <= arr[j]){
            //向前寻找
            j--;
        }
        //找到一个这样的数后就把它赋给前面的被拿走的i的值（如果第一次循环且key是
        // a[left]，那么就是给key）
        arr[i] = arr[j];
        
        while(i < j && key >= arr[i]){
        //这是i在当组内向前寻找，同上，不过注意与key的大小关系停止循环和上面相反，
        //因为排序思想是把数往两边扔，所以左右两边的数大小与key的关系相反
            i++;
        }
        arr[j] = arr[i];
    }
    arr[i] = key;/*当在当组内找完一遍以后就把中间数key回归*/
    PrintArr(arr, 8);
    QuickSort(arr, left, i - 1);//最后用同样的方式对分出来的左边的小组进行同上的做法
    QuickSort(arr, i + 1, right);//用同样的方式对分出来的右边的小组进行同上的做法
    /*当然最后可能会出现很多分左右，直到每一组的i = j 为止*/
}

【算法分析】

三、减治法

减治法（reduce and conquer method）将原问题分解为若干个子问题，并且原问题的解和子问题的解之间存在某种确定的关系，这种关系通常表现为（1）原问题的姐只存在一个较小规模的子问题中；（2）原问题的解与其中一个较小规模的解之间存在某种对应关系。

3.1插入排序

【思想】
包括：直接插入排序，二分插入排序（又称折半插入排序），链表插入排序，希尔排序（又称缩小增量排序）。属于稳定排序的一种（通俗地讲，就是两个相等的数不会交换位置）。
直接插入排序是一种简单的插入排序法，其基本思想是：把待排序的纪录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的纪录插入完为止，得到一个新的有序序列。

【排序过程】粗体为将要插入的记录

序列	排序结果
第 0 次排序	38--48--65--97--76--13--27--49
第 1 次排序	38--48--65--97--76--13--27--49
第 2 次排序	38--48--65--97--76--13--27--49
第 3 次排序	38--48--65--97--76--13--27--49
第 4 次排序	38--48--65--76--97--13--27--49
第 5 次排序	13--38--48--65--76--97--27--49
第 6 次排序	13--27--38--48--65--76--97--49
第 7 次排序	13--27--38--48--49--65--76--97

【算法实现】

/**
 插入排序

 @param arr 数组
 @param n 数组长度
 */
void InsertSort(int*arr,unsigned int n) {
    int i,j,temp;
    for(i = 1; i < n; i++) {
        temp=*(arr+i);
        //j为要插入的位置
        for(j=i;j>0&&*(arr+j-1)>temp;j--){
            //同时将有序区j以后的数向后移一位
            *(arr+j)=*(arr+j-1);
        }
        //将找到的要插入的位置赋值
        *(arr+j)=temp;
        PrintArr(arr, n);
    }
}

【算法分析】

3.2堆排序

【思想】堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值，小根堆得要求是每个节点的值都不小于其父节点的值。

【想法】

【算法实现】

/**
 根据数组array构建大根堆

 @param array 待调整的堆数组
 @param i i是待调整的数组元素的位置
 @param len len是数组的长度
 */
void HeapAdjust(int array[],int i,int len){
    int nChild, nTemp;
    for(;2 * i + 1 < len; i = nChild) {
        //子结点的位置=2*（父结点位置）+1
        nChild = 2 * i + 1;
        //得到子结点中较大的结点
        if(nChild < len-1 && array[nChild+1] > array[nChild]) {
            ++nChild;
        }
        //如果较大的子结点大于父结点那么把较大的子结点往上移动，替换它的父结点
        if(array[i] < array[nChild]) {
            nTemp = array[i];
            array[i] = array[nChild];
            array[nChild] = nTemp;
        } else break; //否则退出循环
    }
}
//堆排序算法
void HeapSort(int *arr, int len){
    int i;
    //调整序列的前半部分元素，调整完之后第一个元素是序列的最大的元素
    //length/2-1是最后一个非叶节点，此处"/"为整除
    for(i = len / 2 - 1; i >= 0; --i) {
        HeapAdjust(arr,i,len);
    }
    //从最后一个元素开始对序列进行调整，不断的缩小调整的范围直到第一个元素
    for(i = len - 1; i > 0; --i) {
        //把第一个元素和当前的最后一个元素交换，
        //保证当前的最后一个位置的元素都是在现在的这个序列之中最大的
        arr[i] = arr[0]^arr[i];
        arr[0] = arr[0]^arr[i];
        arr[i] = arr[0]^arr[i];
        //不断缩小调整heap的范围，每一次调整完毕保证第一个元素是当前序列的最大值
        HeapAdjust(arr,0,i);
    }
}

【算法分析】

四、动态规划法

【思想】动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。

五、贪心法

【思想】贪心算法的基本思路是从问题的某一个初始解出发一步一步地进行，根据某个优化测度，每一步都要确保能获得局部最优解。每一步只考虑一个数据，他的选取应该满足局部优化的条件。若下一个数据和部分最优解连在一起不再是可行解时，就不把该数据添加到部分解中，直到把所有数据枚举完，或者不能再添加算法停止。过程如下：

建立数学模型来描述问题；
把求解的问题分成若干个子问题；
对每一子问题求解，得到子问题的局部最优解；
把子问题的解局部最优解合成原来解问题的一个解
（动态规划法和贪心法需要结合具体的问题作更详细的分析，将会在随后的文章中详述）
注：为了便于观察，代码中涉及到的打印数组函数如下

/**
 打印数组中的元素

 @param arr 数组
 */
void PrintArr(int *arr, int len) {
    int i = 0;
    while (i < len) {
        printf("%d--", arr[i]);
        i++;
    }
}

文中涉及到排序算法github代码

写作记录：###

(2017.04.12排序算法之冒泡排序)
(2017.04.13排序算法之选择排序)
(2017.04.14排序算法之归并排序)
(2017.04.15排序算法之快速排序)
(2017.04.16排序算法之插入排序)
(2017.04.17排序算法之堆排序)

烧脑体操之基本算法设计

一、蛮力法

1.1冒泡排序（bubble sort）

1.2选择排序

二、分治法

2.1归并排序

2.2快速排序

三、减治法

3.1插入排序

3.2堆排序

四、动态规划法

五、贪心法

写作记录：###

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

算法导论

烧脑体操之基本算法设计

一、蛮力法

1.1冒泡排序 （bubble sort）

1.2选择排序

二、分治法

2.1归并排序

2.2快速排序

三、减治法

3.1插入排序

3.2堆排序

四、动态规划法

五、贪心法

写作记录：###

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

算法导论

1.1冒泡排序（bubble sort）