黑马程序员技术交流社区
标题: 三种常见的算法：冒泡、选择、插入 [打印本页]
作者: talent123 时间: 2015-6-1 22:31
标题: 三种常见的算法：冒泡、选择、插入
本帖最后由 talent123 于 2015-6-1 23:43 编辑
- 我贴一篇自己的博客算不算违规呢？如果违规...我编辑一下就是了
下面分别介绍下今天的“三位嘉宾”。
冒泡排序法
英文名字叫：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一起进行，就是预测出我们可能需要运用的变量，比如是数值呢还是下标呢，写在一张纸上，让思路更加的清晰。
搜索
复制
作者: 七尺阳光 时间: 2015-6-1 22:44
最好再来点注释啊.不过也学到了,谢谢
作者: talent123 时间: 2015-6-1 23:41
我也觉得你说的对
我把自己的解析也写出来了
作者: ⒈苆都s.兲憶 时间: 2015-6-1 23:43
涨姿势了！
作者: 蜡笔小炎 时间: 2015-6-2 01:55
解释的很清楚，赞
作者: Dariel 时间: 2015-6-2 08:25
学习了啊
作者: aofex 时间: 2015-6-2 17:03
学习了 比我强
作者: jx836202365 时间: 2015-6-2 19:52
认真看了一下，看的比较费劲。但是学习到了，谢谢
作者: 鬼崇祟 时间: 2015-6-3 22:00
常见而又经典的算法 总结的不错
作者: wangguanyang 时间: 2015-6-4 08:38
楼主总结的不错
作者: 小龙女的萝卜 时间: 2015-6-4 13:03
这个要先收藏了，再慢慢看，哈哈
作者: hi虚无缥缈 时间: 2015-6-4 20:26
三个例题挺经典的，回来再敲一下代码。总结的好。
作者: tabor 时间: 2015-6-10 13:41
看了下，感觉有点难，不保证下次能用~~~~~
temp = arr;
最后的程序中，这一句是不是要加个[i]
作者: 这是829 时间: 2015-6-11 21:56
学习啦，不错不错哦
| 欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) |
黑马程序员IT技术论坛 X3.2 |