直接选择排序和直接插入排序类似,都将数据分为有序区和无序区,所不同的是直接播放排序是将无序区的第一个元素直接插入到有序区以形成一个更大的有序区,而直接选择排序是从无序区选一个最小的元素直接放到有序区的最后。
设数组为a[0…n-1]。
1. 初始时,数组全为无序区为a[0..n-1]。令i=0
2. 在无序区a[i…n-1]中选取一个最小的元素,将其与a[i]交换。交换之后a[0…i]就形成了一个有序区。
3. i++并重复第二步直到i==n-1。排序完成。
直接选择排序无疑是最容易实现的,下面给出代码:
void Selectsort(int a[], int n)
{
int i, j, nMinIndex;
for (i = 0; i < n; i++)
{
nMinIndex = i; //找最小元素的位置
for (j = i + 1; j < n; j++)
if (a[j] < a[nMinIndex])
nMinIndex = j;
Swap(a[i], a[nMinIndex]); //将这个元素放到无序区的开头
}
}
在这里,要特别提醒各位注意下Swap()的实现,建议用:
inline void Swap(int &a, int &b)
{
int c = a;
a = b;
b = c;
}
笔试面试时考不用中间数据交换二个数,很多人给出了
inline void Swap1(int &a, int &b)
{
a ^= b;
b ^= a;
a ^= b;
}
在网上搜索下,也可以找到许多这样的写法。不过这样写存在一个隐患,如果a, b指向的是同一个数,那么调用Swap1()函数会使这个数为0。如:
int i = 6;
Swap1(i, i);
printf("%d\n", i);
当然谁都不会在程序中这样的写代码,但回到我们的Selectsort(),如果a[0]就是最小的数,那么在交换时,将会出现将a[0]置0的情况,这种错误相信调试起来也很难发现吧,因此建议大家将交换二数的函数写成:
inline void Swap(int &a, int &b)
{
int c = a;
a = b;
b = c;
}
或者在Swap1()中加个判断,如果二个数据相等就不用交换了:
inline void Swap1(int &a, int &b)
{
if (a != b)
{
a ^= b;
b ^= a;
a ^= b;
}
}
分享到:
相关推荐
在第一版的基础上新加了对冒泡排序,直接插入排序,直接选择排序,希尔排序,归并排序,快速排序和堆排序这七种常用的排序方法的总结篇,方便大家复习,合适作为笔试面试前的复习资料。
对冒泡排序,直接插入排序,直接选择排序,希尔排序,归并排序,快速排序和堆排序这七种常用的排序方法进行了详细的讲解
1.先从数列中取出一个数作为基准数 2.分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边 3.再对左右区间重复第二步,直到各区间只有一个
这是本人在研一上课时所整理的文档,包括冒泡排序,直接插入排序,直接选择排序,希尔排序,归并排序,快速排序和堆排序这七种常用的排序方法,这些文章不仅使我在考试中取了不错的成绩,也为后来顺利面过迅雷,腾讯...
在第一版的基础上新加了对冒泡排序,直接插入排序,直接选择排序,希尔排序,归并排序,快速排序和堆排序这七种常用的排序方法的总结篇,方便大家复习,合适作为笔试面试前的复习资料。
简单易懂,深入浅出了解七大排序算法,入门学习的好资料
包括冒泡排序,直接 插入排序,直接选择排序,希尔排序,归并排序,快速排序和堆 排序这七种常用的排序方法,
最全面的数据结构算法及重要的排序算法
直接选择排序 希尔排序 归并排序 快速排序 堆排序等经典算法之七大排序白话讲解第二版
冒泡排序,直接插入排序,直接选择排序,希尔排序,归并排序,快速排序和堆排序这七种常用的排序方法的总结,方便大家复习,合适作为笔试面试前的复习资料
* 实现归并排序、快速排序、插入排序、冒泡排序、选择排序* 编程实现O(n)时间复杂度内找到一组数据的第K大元素 ## 二分查找 * 实现一个有序数组的二分查找算法* 实现模糊二分查找算法(比如大于等于给定值的第一个...
白话数据结构7大排序算法详解。
问题:实现归并排序、快速排序、插入排序、冒泡排序、选择排序 问题:编程实现O(n)时间复杂度内找到一组数据的第K大元素 二分查找、散列表、字符串处理、二叉树、堆、图、回溯、分治、动态回归等。 资源中包括常用...
遗传算法将向你揭示:没有最好只有更好,每一天,每一天,一点点进步,就能不断接近完美,这就是生命得以不断延续的秘密。
机器学习实践案例,mnist数据集,KNN算法分类、决策树分类Iris数据集、朴素贝叶斯分类西瓜数据集、逻辑斯蒂回归,随机梯度 mnist数据集,KNN算法分类。 决策树分类Iris数据集(鸢尾花)。 朴素贝叶斯分类西瓜数据集...
使用adaboost,贝叶斯朴素法,决策树,knn,逻辑斯蒂,最大熵,svm,感知机算法实现了MNIST数据集学习并分类。一共八种算法的使用案例。 使用adaboost,贝叶斯朴素法,决策树,knn,逻辑斯蒂,最大熵,svm,感知机...