冒泡排序算法原理及JAVA实现代码_java

冒泡排序法:关键字较小的记录好比气泡逐趟上浮,关键字较大的记录好比石块下沉,每趟有一块最大的石块沉底。

算法本质:(最大值是关键点,肯定放到最后了,如此循环)每次都从第一位向后滚动比较,使最大值沉底,最小值上升一次,最后一位向前推进(即最后一位刚确定的最大值不再参加比较,比较次数减1)

复杂度: 时间复杂度 O(n2) ,空间复杂度O(1)

JAVA源代码(成功运行,需要Date类)

复制代码 代码如下:

 public static void bubbleSort(Date[] days) {
  int len = days.length;
  Date temp;
  for (int i = len - 1; i >= 1; i--) {
   for (int j = 0; j < i; j++) {
    if (days[j].compare(days[j + 1]) > 0) {
     temp = days[j + 1];
     days[j + 1] = days[j];
     days[j] = temp;
    }
   }
  }
 }
class Date {
 int year, month, day;

 Date(int y, int m, int d) {
  year = y;
  month = m;
  day = d;
 }

 public int compare(Date date) {
  return year > date.year ? 1 : year < date.year ? -1
    : month > date.month ? 1 : month < date.month ? -1
      : day > date.day ? 1 : day < date.day ? -1 : 0;
 }

 public void print() {
  System.out.println(year + " " + month + " " + day);
 }
}

复制代码 代码如下:

package testSortAlgorithm;

public class BubbleSort {
 public static void main(String[] args) {
  int array[] = { 5, 6, 8, 4, 2, 4, 9, 0 };
  bubbleSort(array);
  for (int i = 0; i < array.length; i++) {
   System.out.println(array[i]);
  }
 }

 public static void bubbleSort(int array[]) {
  int temp;
  for (int i = array.length - 1; i > 0; i--) {
   for (int j = 0; j < i; j++) {
    if (array[j] > array[j + 1]) {
     temp = array[j];
     array[j] = array[j + 1];
     array[j + 1] = temp;
    }
   }
  }
 }
}

时间: 2024-11-01 07:13:24

冒泡排序算法原理及JAVA实现代码_java的相关文章

快速排序算法原理及java递归实现_java

快速排序 对冒泡排序的一种改进,若初始记录序列按关键字有序或基本有序,蜕化为冒泡排序.使用的是递归原理,在所有同数量级O(n longn) 的排序方法中,其平均性能最好.就平均时间而言,是目前被认为最好的一种内部排序方法 基本思想是:通过一躺排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列. 三个指针: 第一个指针称为pivotkey指针(枢轴),第二个指

冒泡排序的原理及java代码实现_java

概述 冒泡排序是一种简单的排序算法.它重复地走访要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来.走访数列的工作是重复地进行直到数列已经排序完成.这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的开始. 简单点说,就是: 冒泡排序是將比較大的數字沉在数组的后面(可以理解为下面),较小的浮在前面(上面). 直观释义图: 步骤 比较相邻的元素.如果第一个比第二个大,就交换他们两个. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对.在这一点,最后的元

详解堆排序算法原理及Java版的代码实现_java

概述堆排序是一种树形选择排序,是对直接选择排序的有效改进. 堆的定义如下:具有n个元素的序列(k1,k2,...,kn), 当且仅当满足: 时称之为堆.由堆的定义可以看出,堆顶元素(即第一个元素)必为最小项(小顶堆)或最大项(大顶堆). 若以一维数组存储一个堆,则堆对应一棵完全二叉树,且所有非叶结点(有子女的结点)的值均不大于(或不小于)其子女的值,根结点(堆顶元素)的值是最小(或最大)的. (a)大顶堆序列:(96, 83, 27, 38, 11, 09) (b)小顶堆序列:(12, 36,

HTTP基本认证(Basic Authentication)的JAVA实例代码_java

大家在登录网站的时候,大部分时候是通过一个表单提交登录信息. 但是有时候浏览器会弹出一个登录验证的对话框,如下图,这就是使用HTTP基本认证. 下面来看看一看这个认证的工作过程: 第一步: 客户端发送http request 给服务器,服务器验证该用户是否已经登录验证过了,如果没有的话, 服务器会返回一个401 Unauthozied给客户端,并且在Response 的 header "WWW-Authenticate" 中添加信息. 如下图. 第三步: 服务器将Authorizati

Java 队列实现原理及简单实现代码_java

Java 队列实现原理 "队列"这个单词是英国人说的"排".在英国"排队"的意思就是站到一排当中去.计算机科学中,队列是一种数据结构,有点类似栈,只是在队列中第一个插入的数据项也会最先被移除,而在栈中,最后插入的数据项最先移除.队列的作用就像电影院前的人们站成的排一样:第一个进入附属的人将最先到达队头买票.最后排队的人最后才能买到票. 队列和栈一样也被用作程序员的工具.它也可以用于模拟真实世界的环境,例如模拟人们在银行里排队等待,飞机等待起飞,或

完整B树算法Java实现代码_java

定义 在计算机科学中,B树(英语:B-tree)是一种自平衡的树,能够保持数据有序.这种数据结构能够让查找数据.顺序访问.插入数据及删除的动作,都在对数时间内完成. 为什么要引入B树? 首先,包括前面我们介绍的红黑树是将输入存入内存的一种内部查找树. 而B树是前面平衡树算法的扩展,它支持保存在磁盘或者网络上的符号表进行外部查找,这些文件可能比我们以前考虑的输入要大的多(难以存入内存). 既然内容保存在磁盘中,那么自然会因为树的深度过大而造成磁盘I/O读写过于频繁(磁盘读写速率是有限制的),进而导

java 数据结构 冒泡排序实现代码_java

冒泡(Bubble Sort)排序的基本思想是:将待排序的数组看作从上倒下排列,把关键字较小的记录看作较轻的,关键字较大的看作较重的,较小的关键字的值看作是水中的气泡向上浮,较大的关键字如水中的石块向下沉,当气泡都浮到相应的位置的时候排序结束. 算法性能分析                         (1)      时间复杂素.总的一定此次数为3/2(n-1)*n                         (2)      空间复杂度.仅用了一个辅助单元空间复杂度为O(1)    

Java实现冒泡排序与双向冒泡排序算法的代码示例_java

冒泡排序:就是按索引逐次比较相邻的两个元素,如果大于/小于(取决于需要升序排还是降序排),则置换,否则不做改变 这样一轮下来,比较了n-1次,n等于元素的个数:n-2, n-3 ... 一直到最后一轮,比较了1次 所以比较次数为递减:从n-1 到 1 那么总的比较次数为:1+2+3+...+(n-1),  以等差公式计算:(1+n-1)/2*(n-1) ==> n/2*(n-1) ==> (n^2-n) * 0.5 用大O表示算法的时间复杂度:O(n^2) ,  忽略了系数0.5和常数-n p

Java实现冒泡排序算法及对其的简单优化示例_java

原理 冒泡排序大概是所有程序员都会用的算法,也是最熟悉的算法之一. 它的思路并不复杂: 设现在要给数组arr[]排序,它有n个元素. 1.如果n=1:显然不用排了.(实际上这个讨论似乎没什么必要) 2.如果n>1: (1)我们从第一个元素开始,把每两个相邻元素进行比较,如果前面的元素比后面的大,那么在最后的结果里面前者肯定排在后面.所以,我们把这两个元素交换.然后进行下两个相邻的元素的比较.如此直到最后一对元素比较完毕,则第一轮排序完成.可以肯定,最后一个元素一定是数组中最大的(因为每次都把相对