前沿:
如果您还没有了解基础的冒泡排序,可以点击这里
阅读。
介绍:
在介绍选择排序之前,回顾下冒泡排序。如果有N的数据项,冒泡排序需要比较的次数是N(N-1)/2的次数,而交换的次数也和N的平方成正比。因此大O表示法来表示亦即O(N*N)。选择排序改进了冒泡排序,将不必要的交换次数从O(N*N) 减少到O(N)。不幸的是比较次数依然是O(N*N)。
因此,选择排序相对于冒泡排序其实只是减少了交换的次数。
思路:
为了减少冒泡排序总俩俩比较并交换的缺点,选择排序偏向于较少的交换次数。其做法是:从数组最左端(下标为0位置)开始依次比较,找出数组中最小值并将此数据项记下,然后将找到的最小值与数组最左端(下标为0位置)的数据项进行交换。第一次比较完成之后,得到的结果便是数组中最小的数据项已经被移动到了数组最左端(下标为0)。以此类推,第二次找到数组中第二小的结果并与数组下标为1的位置的数据项进行交换。
核心代码:
public void selectSort() {
int innerLoop, outterLoop, min;
double temp;
for(outterLoop=0;outterLoop<elementCount-1;outterLoop++) {
min = outterLoop;
for(innerLoop=outterLoop+1;innerLoop<elementCount;innerLoop++) {
if(array[innerLoop] < array[min]) {
min = innerLoop;
}//end of if
}//end of for
//swap them
temp = array[min];
array[min] = array[outterLoop];
array[outterLoop] = temp;
}//end of for
}//end of method
核心代码说明:
内层for循环,实际上是找最值的过程。假设数组中下标为0位置的数据项是最小值,从下表为1位置开始于这个最小值相比较,如果找到比min更小的值,就将min更新,下次循环比较的过程将用新的最小值比较。内层for循环比较过之后,数组中最小值已经找到,此时,只需要讲这个找到的最小值与数组下标为0的位置交换即可。
外层for循环,实际控制着等待交换的位置,从0开始直到数组的最后一个位置结束。
完整代码:
package barry.sort.selectsort;
public class SelectSorter {
private double[] array;
private int elementCount;
public SelectSorter(int size) {
array = new double[size];
elementCount = 0;
}//end of constructor
public void insert(double value) {
array[elementCount] = value;
elementCount++;
}//end of method insert()
public void display() {
for(int i=0;i<elementCount;i++) {
System.out.print(array[i]+"\t");
}//end of for
}//end of method display()
public void selectSort() {
int innerLoop, outterLoop, min;
double temp;
for(outterLoop=0;outterLoop<elementCount-1;outterLoop++) {
min = outterLoop;
for(innerLoop=outterLoop+1;innerLoop<elementCount;innerLoop++) {
if(array[innerLoop] < array[min]) {
min = innerLoop;
}//end of if
}//end of for
//swap them
temp = array[min];
array[min] = array[outterLoop];
array[outterLoop] = temp;
}//end of for
}//end of method
}
package barry.sort.selectsort;
public class SelectSorterApp {
public static void main(String[] args) {
SelectSorter sorter = new SelectSorter(91);
sorter.insert(-10); sorter.insert(89);
sorter.insert(-980); sorter.insert(45);
sorter.insert(343); sorter.insert(32);
sorter.insert(5563); sorter.insert(9);
System.out.println("\nBefore Sort:");
sorter.display();
sorter.selectSort();
System.out.println("\nAfter Sort:");
sorter.display();
}
}
运行结果:
Before Sort:
-10.0 89.0 -980.0 45.0 343.0 32.0 5563.0 9.0
After Sort:
-980.0 -10.0 9.0 32.0 45.0 89.0 343.0 5563.0
总结:
不难发现,选择排序和冒泡排序的区别在于:冒泡排序每两个数据项比较之后就有可能需要交换,然而选择排序时从数组中“选出最小值”然后和特性位置的数据项交换。虽然其时间复杂度依旧和冒泡排序一样,但是交换的次数却明显减少。
因此,当交换数据项所需的时间比比较所需的时间大很多时,选择排序时相当快的。
分享到:
相关推荐
逻辑结构:描述数据元素之间的逻辑关系,如线性结构(如数组、链表)、树形结构(如二叉树、堆、B树...学习算法与数据结构不仅有助于理解程序的内部工作原理,更能帮助开发人员编写出高效、稳定和易于维护的软件系统。
《数据结构与算法设计》以基本...《数据结构与算法设计》内容丰富,观点新颖,理论联系实际,不仅可用做高等院校计算机科学与工程专业学生学习数据结构与算法的教材,而且也适合广大工程技术人员参考。本书由王晓东著。
数据结构-栈与队列,链表,递归,简单排序到高级排序的算法的详细笔记,本人根据视频学习进行的数据结构记录。适合入门算法学习初级篇
本书在简要回顾了基本的C++ 程序设计概念的基础上,全面系统地介绍了队列、堆栈、树、图等基本数据结构,以及贪婪算法、分而治之算法、分枝定界算法等多种算法设计方法,为数据结构与算法的继续学习和研究奠定了一...
这本书是用java讲数据结构和排序算法的,全书只有44页,但是讲的内容很不错,推荐学习或者复习数据结构的童鞋下在看看!
c语言版本的数据结构的快速排序算法,适用于新手学习
实现直接插入排序、折半插入、冒泡、快速、直接选择、堆、归并排序算法。比较各种 算法的运行速度和时间复杂度,是否为稳定排序。分析每一趟排序结果。
数据结构各排序算法比较-配套《高分笔记》,对于学习排序算法做了很好的总结
虽然讲师的表述并不完美,但却不失为一个好的学习资料
数据结构与算法之内部及外部排序算法的学习
算法与数据结构涵盖了以下主要内容: 数据结构(Data Structures): 逻辑结构:描述数据元素之间...学习算法与数据结构不仅有助于理解程序的内部工作原理,更能帮助开发人员编写出高效、稳定和易于维护的软件系统。
数据结构与算法内部排序分析PPT学习教案.pptx
虽然讲师的表述并不完美,但却不失为一个好的学习资料
介绍了计算机编程中使用的数据结构和算法,对于在计算机应用中如何操作和管理数据以取得最优性能提供了深入浅出的讲解。全书共分为15章,分别讲述了基本概念、数组、简单排序、堆和队列、链表、递归、进阶排序、...
排序的基本概念以及其算法的种类,介绍几种常见的排序算法的算法:冒泡排序、选择排序、插入排序、归并排序、快速排序、希尔排序的算法和分析它们各自的复杂度,然后以表格的形式,清晰直观的表现出它们的复杂度的...
Java数据结构与算法学习笔记之排序 冒泡排序,选择排序,插入排序,希尔排序, 归并排序, 快速排序.
本资源包含《数据结构》考研的九种内部排序算法考点的算法代码及排序过程图示,以表格、图文方式详细讲解每一种排序算法的排序过程。 包含的九种内部排序有:直接插入排序、折半排序、希尔排序、冒泡排序、快速排序...
- 涵盖常见的数据结构(如链表、栈、队列、树等)和算法(如排序、搜索等); - 适合学习和参考,助力深入理解计算机科学中的基础概念。 适用人群: - 数据结构与算法初学者; - 希望通过实践加深对算法理解的学习...
算法与数据结构它们分别涵盖了以下主要内容: 数据结构(Data Structures): ...学习算法与数据结构不仅有助于理解程序的内部工作原理,更能帮助开发人员编写出高效、稳定和易于维护的软件系统。