------- 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常用排序算法&程序员必须掌握的8大排序算法+二分法查找 Java常用排序算法&程序员必须掌握的8大排序算法+二分法查找
图 -Floyed算法 -Dijkstra算法 -拓扑排序算法
Java常用排序算法程序员必须掌握的8大排序算法Java开发Java经验技巧共16页.pdf.zip
该资源提供了Java中实现插入排序的全面指南。文档中涵盖了插入排序的基本概念,包括如何对数组进行排序以及如何在Java中实现插入排序。...我们相信,该资源将成为想提高算法设计技能的Java程序员的宝贵参考资料。
该资源提供了Java中实现堆排序的全面指南。文档中涵盖了堆排序的基本概念,包括如何对数组进行排序以及如何在Java中实现堆排序。...我们相信,该资源将成为想提高算法设计技能的Java程序员的宝贵参考资料。
用C语言实现的算法,各种算法,写的很详细,黑马程序员内部资料
旅行商问题-A算法-java
面试笔试必用-必须掌握的Java排序算法
java代码-使用java解决java排序之-快速排序的问题的源代码 ——学习参考资料:仅用于个人学习使用!
K-Means聚类算法java实现.pdf K-Means聚类算法java实现.pdf K-Means聚类算法java实现.pdf K-Means聚类算法java实现.pdf K-Means聚类算法java实现.pdf K-Means聚类算法java实现.pdf K-Means聚类算法java实现.pdf K-...
Java代码-排序-直接插入排序、希尔排序、直接选择排序、冒泡排序、堆排序、快速排序、归并排序中部分排序以及算法-贪心法,大家可以将源码下载下来进行学习,附带着注释和解释,有不理解的可以找博主一起探讨,共同...
二维矩形装箱算法--二叉树--java实现.rar
VC++多线程实现三种排序算法比较----冒泡排序、快速排序、归并排序,很有意思,可以下载看看!
排序算法 排序算法_基于Java实现的排序算法之BubbleSort实现
最快的排序算法 谁才是最强的排序算法:快速排序-归并排序-堆排序,排序算法数据结构
经典的排序算法C#源码,包括: 经典排序算法 - 快速排序Quick sort 经典排序算法 - 桶排序Bucket sort 经典排序算法 - 插入排序Insertion sort 经典排序算法 - 基数排序Radix sort 经典排序算法 - 鸽巢排序...
排序算法 排序算法_基于Java实现的排序算法之BozoSort实现
排序算法 排序算法_基于Java实现的排序算法之BitonicSort实现
排序算法 排序算法_基于Java实现的排序算法之BogoSort实现
银行家算法--进程调度算法--内存分配算法java实现