本帖最后由 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一起进行,就是预测出我们可能需要运用的变量,比如是数值呢还是下标呢,写在一张纸上,让思路更加的清晰。
搜索
复制
|