A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

本帖最后由 talent123 于 2015-6-1 23:43 编辑
  1. 我贴一篇自己的博客算不算违规呢?如果违规...我编辑一下就是了
复制代码

下面分别介绍下今天的“三位嘉宾”。



冒泡排序法


英文名字叫:Bubble Sort. 是一种最简单也最基础的排序方法。
它为何叫冒泡呢?
名字来源于算法的原理,在这个方法中,不断的重复遍历要排序的数列,一次比较两个元素。
如果他们的顺序错误(比如前大后小),就把大的放在后面,小的放在前面,也就是交换过来。
1跟2比较,2跟3比较,3跟4比……n-1和n,这时候整个数列最大的数就被我们放置在数列的尾部n了。
再次,1跟2比较,2跟3比较,3跟4比较……n-2和n-1比较,此时的n-1就是未排序数列中最大的。
重复n-1次之后,我们整个数列就按照从小到大排列起来了。


//创建函数的时候传入2个变量,一个是数组指针,一个是数组的大小
void bubble_sort(int a[], int n){
        int i, j, temp;
        //使用i计数,表示我们的冒泡过程需要重复n-1次
        for (i = 0; i < n; i++){
        //使用j来表示数列中相邻的两个数
                for (j = 0; j < n - 1 - i; j++){
                        //常用的第三方置换方法
                        if (a[j] > a[j + 1]){
                                temp = a[j];
                                a[j] = a[j + 1];
                                a[j + 1] = temp;
                        }
                }
        }
}



选择排序法


英文名字:Select Sort . 是一种直观的排序方法。第一次遍历整个数组之后,找出最小值,也就是a[min]。
这一步很容易。拿出a[0]当最最小,之后不断的与数列内的单元比较。
下面到了方法的重点,将这个最小值与数组的a[0]互换位置。此时,可以预想到我们需要设定一组记录数组下标的变量帮助我实现互换。
然后重复上面的步骤,也就是说用a[1]与后续的所有数字进行比较,找出a[min],再将a[min]与a[1]互换。
直到数组的最后一位,它自己就是a[min],放在原地就好了。
知道了方法,我们看一下代码。


int select_sort(int a[],int n){
        int i, j, min,t;
        for (i = 0; i < n-1; i++){
                min = i;
                for (j = i+1; j < n; j++){
                        if (a[min] > a[j]){
                                min = j;
                        }
                }
                if (min != i){
                        t = a;
                        a = a[min];
                        a[min] = t;
                }
        }
}
再来介绍第三位嘉宾



插入排序法


这个算法是我认为比较繁琐的一个算法,它的原理是:将一个数据插入到已经排好序的有序数据中,从而得到一个新的,个数加一的有序数据。听起来像不像是我们在玩扑克牌时,将新抓到的牌放在我们已有的牌序中。具体执行的时候,我们先从第一个元素a[0]开始,默认它是已经被排序的,因为只有它自己嘛~然后,取出下一个元素,即a[1],在已经排序的序列中从后向前进行比较。如果a[1]小于a[0],那么把a[0]向后移动一位,注意下标的变化。把[a1]放在a[0]的位置上,此时是a[1]和a[0]的位置互换。之后,把a[2]和当前a[1]重复上述比较,如果a[2]小于a[1],在比较a[2]和a[0],直到找到已排序的元素小于或者等于新元素的位置,将新元素插入到下一位置中。这就是算法的基本描述。
我们来看一下代码。


void insert_sort(int *arr, int n){
        int i, j, temp;
        for (i = 1; i < n; i++){
                temp = *(arr + i);
                j = i;
                while ( j > 0 && temp < *(arr + j - 1)){
                        *(arr + j ) = *(arr + j - 1);
                        j--;
                }
                *(arr + j) = temp;
        }
}
这段呢是使用的指针,我自己又通过原理写了一个下标的方法。

void sort(int arr[], int first, int last){
        int i, j;
        int temp;
        for (i = first + 1; i < last; i++){
                temp = arr;
                j = i - 1;
                while (j >= 0 && arr[j] > temp){
                        arr[j + 1] = arr[j];
                        j --;
                }
                if ( j != i - 1){
                        arr[j + 1] = temp;
                }
        }
}
其中的原理是相同的,只不过,在定义函数的时候,多使用了一个变量first,其实可以默认我们的first是0啦。

跟上一段代码没有本质上的不同。
不过上述代码有一些限定条件(我用红色标出),是很值得注意的。在写其他函数的时候,也应该考虑到。那就是边界。
在运行的时候,如果给出的数列a[1]<a[0],按照我们的代码,会用a[1]与a[0]“前面”的一位进行比较。
我们都知道a[0]前面什么都没有了!j--可能会使j变成-1,这时候就会使排序失败!


总结


在学习的时候,我们可能会遇到各种各样的算法,光排序常用的七八种。光记住算法的原理是不够的。
不求创新出新的算法,至少我们应该在应用算法思想的时候,有自己的一套思路,总不能背下来,每次用的时候就默写一遍先?!这是不可取的。
仅就今天数组方面,我自己的总结就是:
1.要知道我们的算法需要重复多少次,这是很重要的前提条件,什么时候循环终止,避免越界。写for循环的时候心里也有底嘛!
2.一般的算法都是嵌套的,2层以上的循环,那么在编写代码的时候,可以从内而外的思考,先想一想我们的一次循环是怎样做的。
3.在思考某一次循环的时候,从普通到特殊,也可以理解为,从数组的中部开始,最后考虑首尾的特殊情况,避免越界!
4.其实可以跟3一起进行,就是预测出我们可能需要运用的变量,比如是数值呢还是下标呢,写在一张纸上,让思路更加的清晰。




搜索
复制

13 个回复

倒序浏览
最好再来点注释啊.不过也学到了,谢谢
回复 使用道具 举报
七尺阳光 发表于 2015-6-1 22:44
最好再来点注释啊.不过也学到了,谢谢

我也觉得你说的对
我把自己的解析也写出来了
回复 使用道具 举报
涨姿势了!
回复 使用道具 举报
解释的很清楚,赞
回复 使用道具 举报
学习了啊
回复 使用道具 举报
学习了  比我强
回复 使用道具 举报
认真看了一下,看的比较费劲。但是学习到了,谢谢
回复 使用道具 举报
常见而又经典的算法   总结的不错
回复 使用道具 举报
楼主总结的不错
回复 使用道具 举报
这个要先收藏了,再慢慢看,哈哈
回复 使用道具 举报
hi虚无缥缈 来自手机 中级黑马 2015-6-4 20:26:24
12#
三个例题挺经典的,回来再敲一下代码。总结的好。
回复 使用道具 举报
tabor 中级黑马 2015-6-10 13:41:48
13#
看了下,感觉有点难,不保证下次能用~~~~~

    temp = arr;
最后的程序中,这一句是不是要加个[i]
回复 使用道具 举报
学习啦,不错不错哦
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马