------- android培训、java培训、期待与您交流! ----------
Java简单排序算法
最简单的排序方法:直接选择排序、冒泡排序。
选择排序(Selection Sort)的基本思想是:每一趟从待排序的记录中选出关键字最小的记录,顺序放在已排好序的子文件的最后,直到全部记录排序完毕。常用的选择排序方法有直接选择排序和堆排序。
直接选择排序:
(1)关键字比较次数
无论文件初始状态如何,在第i趟排序中选出最小关键字的记录,需做n-i次比较,因此,总的比较次数为:n(n-1)/2=0(n2)
(2)记录的移动次数
当初始文件为正序时,移动次数为0
文件初态为反序时,每趟排序均要执行交换操作,总的移动次数取最大值3(n-1)。
直接选择排序的平均时间复杂度为O(n2)。
class SelectionSort { public static void main(String[] args) { double[] arr = new double[10000]; for(int i=0;i<arr.length;i++) { arr[i]=(arr.length*Math.random()); } //排序前时间 long st1 = System.currentTimeMillis(); //排序 sort(arr); //排序后时间 long st2 = System.currentTimeMillis(); for(int i=0;i<arr.length;i++) { System.out.print(arr[i]+" "); } System.out.println(""); System.out.println("共花费"+(st2-st1)+"毫秒"); } public static void sort(double[] a) { int sortedLen= a.length; for(int i=0;i<sortedLen-1;i++) { for(int j=i+1;j<sortedLen;j++) { if(a[i]>a[j]) { swap(a,i,j); } } } } public static void swap(double[] arr,int a,int b){ double temp = arr[a]; arr[a] = arr[b]; arr[b] = temp; } }
交换排序的基本思想是:两两比较待排序记录的关键字,发现两个记录的次序相反时即进行交换,直到没有反序的记录为止。应用交换排序基本思想的主要排序方法有:冒泡排序和快速排序。
冒泡排序:
(1)算法的最好时间复杂度
若文件的初始状态是正序的,一趟扫描即可完成排序。所需的关键字比较次数C和记录移动次数M均达到最小值:
Cmin=n-1
Mmin=0。
冒泡排序最好的时间复杂度为O(n)。
(2)算法的最坏时间复杂度
若初始文件是反序的,需要进行n-1趟排序。每趟排序要进行n-i次关键字的比较(1≤i≤n-1),且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下,比较和移动次数均达到最大值:
Cmax=n(n-1)/2=O(n2)
Mmax=3n(n-1)/2=O(n2)
冒泡排序的最坏时间复杂度为O(n2)。
(3)算法的平均时间复杂度为O(n2)
虽然冒泡排序不一定要进行n-1趟,但由于它的记录移动次数较多,故平均时间性能比直接插入排序要差得多。
class BubbleSort { public static void main(String[] args) { double[] arr = new double[10000]; for (int i = 0; i < arr.length; i++) { arr[i] = (arr.length * Math.random()); } // 排序前时间 long st1 = System.currentTimeMillis(); // 排序 sort(arr); // 排序后时间 long st2 = System.currentTimeMillis(); for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } System.out.println(""); System.out.println("共花费" + (st2 - st1) + "毫秒"); } public static void sort(double[] a) { int sortedLen = a.length; for (int i = 0; i < sortedLen - 1; i++) { for (int j = 0; j < sortedLen - i - 1; j++) { if (a[j] > a[j + 1]) { swap(a, j, j + 1); } } } } public static void swap(double[] arr, int a, int b) { double temp = arr[a]; arr[a] = arr[b]; arr[b] = temp; }
相关推荐
### 黑马程序员入学Java精华总结 #### 一、Java概述与基础知识 1. **何为编程?** - 编程是指通过编写计算机能够理解的指令来解决问题或完成特定任务的过程。这些指令通常被组织成算法,并使用某种编程语言实现。...
《黑马程序员Java面试宝典》是一本专门为Java开发者准备的面试指南,包含了广泛而深入的Java技术知识,以及面试过程中可能会遇到的各种问题。这本书的完整版PDF提供了丰富的学习材料,帮助求职者提升自己的技术水平...
10. **算法与数据结构**:虽然不是Java专有,但面试中也会涉及到排序算法(冒泡、快速、归并)、查找算法(二分查找)、树(二叉树、红黑树)等,它们是解决复杂问题的基础工具。 以上这些知识点构成了Java面试的...
10. **算法与数据结构**:虽然Java面试更注重实践,但基础的排序算法(如冒泡、快速、归并)、查找算法、树结构(二叉树、红黑树)、图算法等也是面试官喜欢询问的内容。 11. **框架与技术**:MyBatis、Hibernate等...
本资料包是黑马程序员提供的详细教程,涵盖了Java集合的例题、源码以及配套的PPT教学文档,旨在帮助学习者深入理解和掌握Java集合的使用。 首先,我们来探讨Java集合框架的基本概念。Java集合框架包括接口和实现类...
【标题】:“黑马程序员入学测试题”是一份用于评估编程基础和理解能力的测试集,主要针对准备加入黑马程序员培训课程的学生。这份测试题旨在帮助新手程序员检验自己的知识水平,以便更好地适应学习环境。 【描述】...
"黑马程序员_Java基础辅导班教程课件[第01期]第11天"是一个专门为初学者设计的培训课程,旨在帮助学员深入理解和掌握Java的核心概念。这个课程可能是通过视频形式进行的,结合了理论讲解和实际操作,以便让学习者能...
### 黑马程序员入学Java知识 #### Java概述与基础知识 1. **何为编程?** - 编程是通过特定的计算机语言来编写指令,让计算机能够执行一系列任务的过程。 2. **Java语言概述,历史、特点** - Java是一种广泛...
这个名为“黑马程序员_毕向东_Java基础源码.rar”的压缩包文件,包含了丰富的Java基础源代码实例,对于初学者来说,是深入了解Java编程的良好资源。 一、Java基本语法 Java语言以其严格的类型检查和面向对象特性...
本教程源码由黑马程序员提供,旨在帮助学习者深入理解和掌握Java中的数据结构及其算法。以下是对这些关键知识点的详细阐述: 1. **数组**:Java中最基础的数据结构,用于存储相同类型元素的集合。数组提供了直接...
|--图片的LRU算法内存保存和读取 |--图片的缩放处理(防内存溢出) |--多媒体应用设计图 |--多线程下载 |--多线程下载及断点续传 |--多线程之AsyncTask的用法 |--多线程之线程池ExecutorService |--字体为粗体 |--安卓...
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
理解常见的数据结构(如栈、队列、链表、树、图)及其操作,掌握排序算法(如冒泡、插入、选择、快速、归并排序)和查找算法(如二分查找、哈希查找)。计算机基础包括操作系统原理、网络协议、内存管理、CPU调度等...
- 排序、搜索算法、链表、树等基础知识。 6. **操作系统**: - Linux基本命令、进程线程、网络、内存管理和系统调用。 7. **服务端**: - Node.js、PHP、Java等后端开发语言的基础知识。 8. **跨端开发**: -...
这本书由知名教育机构黑马程序员编撰,旨在帮助读者全面掌握Java核心技术,提高面试成功率。 【描述】:“黑马程序员官网第五版面试宝典”意味着这已是该系列的最新版本,内容经过多次更新和优化,以适应不断变化的...
- **算法与数据结构**:常见的排序算法(冒泡、选择、插入、快速、归并等),链表、树、图等数据结构的操作。 - **设计模式**:工厂模式、单例模式、观察者模式等23种设计模式的运用。 - **系统设计**:高并发、...
在Java中,常见的数据结构有数组、链表、栈、队列、哈希表、树等,而算法则涉及排序、搜索、图论等领域。熟练掌握这些数据结构和算法,能有效提高代码效率,优化解决方案。 再者,多线程是Java的一大特色,面试中...
复习资料可能涵盖了数组、链表、栈、队列、树、图、哈希表等基本数据结构,以及排序、搜索、递归、动态规划等核心算法。这些知识不仅在面试中常见,也是解决复杂问题的关键。 然后,软件工程和项目管理是实际工作中...