算法导论Java实现-冒泡排序(思考题2-2)

简介:

 
 
  1. package lhz.algorithm.chapter.two; 
  2. /** 
  3.  * “冒泡排序”,《算法导论》思考题2-2 
  4.  * 伪代码: 
  5.  * BUBBLESORT(A) 
  6.  * 1 for i ← 1 to length[A] 
  7.  * 2 do for j ← length[A] downto i + 1 
  8.  * 3 do if A[j] < A[j - 1] 
  9.  * 4 then exchange A[j] ↔ A[j - 1]  
  10.  * @author lihzh(苦逼coder) 
  11. * 本文地址:http://mushiqianmeng.blog.51cto.com/3970029/733277  
  12. */ 
  13. public class BubbleSort { 
  14.      
  15.     private static int[] input = new int[] { 21549867103 }; 
  16.  
  17.     public static void main(String[] args) { 
  18.         int endIndex = input.length - 1
  19.         for (int i = 0; i < endIndex; i++) {//复杂度:n 
  20.             for (int j = endIndex; j > i; j--) {//复杂度:1+2+...+(n-1)=Θ(n^2) 
  21.                 if (input[j] < input[j-1]) { 
  22.                     int temp = input[j]; 
  23.                     input[j] = input[j-1]; 
  24.                     input[j-1] = temp; 
  25.                 } 
  26.             } 
  27.         } 
  28.         /* 
  29.          * 复杂度分析: 
  30.          * 由上可见冒泡排序的复杂度为:Θ(n^2)。在最佳情况下,虽无需交换,但比较的次数仍为:Θ(n^2)。 
  31.          * 在最佳情况下,复杂度也为Θ(n^2),此时不如插入排序。 
  32.          * 冒泡排序的交换次数也大于插入排序。 
  33.          * 冒泡排序对n个项目需要O(n2)的比较次数,且可以原地排序。 
  34.          * 尽管这个算法是最简单了解和实作的排序算法之一,但它对于少数元素之外的数列排序是很没有效率的。 
  35.          * 冒泡排序是稳定的。 
  36.          */ 
  37.         //打印数组 
  38.         printArray(); 
  39.     } 
  40.      
  41.     private static void printArray() { 
  42.         for (int i : input) { 
  43.             System.out.print(i + " "); 
  44.         } 
  45.     } 

 




     本文转自mushiqianmeng 51CTO博客,原文链接:http://blog.51cto.com/mushiqianmeng/733277,如需转载请自行联系原作者


相关文章
|
3天前
|
存储 算法 Java
Java中,树与图的算法涉及二叉树的前序、中序、后序遍历以及DFS和BFS搜索。
【6月更文挑战第21天】Java中,树与图的算法涉及二叉树的前序、中序、后序遍历以及DFS和BFS搜索。二叉树遍历通过访问根、左、右子节点实现。DFS采用递归遍历图的节点,而BFS利用队列按层次访问。以下是简化的代码片段:[Java代码略]
13 4
|
3天前
|
算法 Java 机器人
Java数据结构与算法:并发数据结构ConcurrentHashMap
Java数据结构与算法:并发数据结构ConcurrentHashMap
14 3
|
3天前
|
算法 Java 机器人
Java数据结构与算法:AVL树
Java数据结构与算法:AVL树
17 6
|
3天前
|
算法 Java Linux
Java数据结构与算法:红黑树
Java数据结构与算法:红黑树
17 5
|
3天前
|
存储 人工智能 算法
Java数据结构与算法:邻接矩阵和邻接表
Java数据结构与算法:邻接矩阵和邻接表
20 5
|
3天前
|
算法 Java 机器人
Java数据结构与算法:最大堆
Java数据结构与算法:最大堆
19 4
|
3天前
|
算法 Java 机器人
Java数据结构与算法:最小堆
Java数据结构与算法:最小堆
12 3
|
3天前
|
搜索推荐 算法 Java
Java中的快速排序、归并排序和堆排序是常见的排序算法。
【6月更文挑战第21天】Java中的快速排序、归并排序和堆排序是常见的排序算法。快速排序采用分治,以基准元素划分数组并递归排序;归并排序同样分治,先分割再合并有序子数组;堆排序通过构建堆来排序,保持堆性质并交换堆顶元素。每种算法各有优劣:快排平均高效,最坏O(n²);归并稳定O(n log n)但需额外空间;堆排序O(n log n)且原地排序,但不稳定。
14 3
|
4天前
|
监控 算法 Java
Java虚拟机(JVM)使用多种垃圾回收算法来管理内存,以确保程序运行时不会因为内存不足而崩溃。
【6月更文挑战第20天】Java JVM运用多种GC算法,如标记-清除、复制、标记-压缩、分代收集、增量收集、并行收集和并发标记,以自动化内存管理,防止因内存耗尽导致的程序崩溃。这些算法各有优劣,适应不同的性能和资源需求。垃圾回收旨在避免手动内存管理,简化编程。当遇到内存泄漏,可以借助VisualVM、JConsole或MAT等工具监测内存、生成堆转储,分析引用链并定位泄漏源,从而解决问题。
15 4
|
3天前
|
机器学习/深度学习 算法 搜索推荐
数据结构算法--2 冒泡排序,选择排序,插入排序
**基础排序算法包括冒泡排序、选择排序和插入排序。冒泡排序通过相邻元素比较交换,逐步将最大值“冒”到末尾,平均时间复杂度为O(n^2)。选择排序每次找到剩余部分的最小值与未排序部分的第一个元素交换,同样具有O(n^2)的时间复杂度。插入排序则类似玩牌,将新元素插入到已排序部分的正确位置,也是O(n^2)复杂度。这些算法适用于小规模或部分有序的数据。**

热门文章

最新文章