简介
简单排序
在程序中,排序是常见的一种需求,提供一些数据元素,把这些数据元素按照一定的规则排序.
在java的开发工具包jdk中，已经给我们提供了很多数据结构与算法的实现，比如List，Set，Map，Math等等，都 是以API的方式提供，这种方式的好处在于一次编写，多处使用。我们借鉴jdk的方式，也把算法封装到某个类中， 那如果是这样，在我们写java代码之前，就需要先进行API的设计，设计好之后，再对这些API进行实现。
例如:
| 类名 | Arraylist |
|---|---|
| 构造方法 | Arraylist():创建ArrayList对象 |
| 成员方法 | 1.boolean add(E e):向集合中添加元素 2.E remove(int index):从集合中删除指定的元素 |
然后再使用java代码去实现它.
Comparable接口介绍
java提供的Comparable接口就是用来定义排序规则的
需求:
1.定义一个学生类Student，具有年龄age和姓名username两个属性，并通过Comparable接口提供比较规则；
2.定义测试类Test，在测试类Test中定义测试方法Comparable getMax(Comparable c1,Comparable c2)完成测试
Student类
package ComparablePort;import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.NoArgsConstructor;@Data
@AllArgsConstructor
@NoArgsConstructor
public class Student implements Comparable<Student> {private String name;private int age;@Overridepublic String toString() {return "Student{" +"name='" + name + '\'' +", age=" + age +'}';}//排序比较规则public int compareTo(Student o){return this.getAge()-o.getAge();}
}
GetMax类
package ComparablePort;public class GetMax {//测试方法，获取两个元素中的较大值public static Comparable getmax(Comparable c1, Comparable c2) {int imp = c1.compareTo(c2);if (imp >= 0) {return c1;} else {return c2;}}
}
Test类
package ComparablePort;public class Test {public static void main(String[] args) {Student stu1 = new Student();stu1.setName("sanm");stu1.setAge(20);Student stu2 = new Student();stu2.setName("Gainly");stu2.setAge(18);Comparable max = GetMax.getmax(stu1, stu2);System.out.println(max);}
}
冒泡排序
冒泡排序是一种计算机领域的较为简单的排序算法.
排序原理
- 比较相邻的元素。如果前一个元素比后一个元素大，就交换这两个元素的位置。
- 对每一对相邻元素做同样的工作，从开始第一对元素到结尾的最后一对元素。最终最后位置的元素就是最大 值。
冒泡排序API设计:
| 类名 | Bubble |
|---|---|
| 构造方法 | bubble():创建Bubble对象 |
| 成员方法 | 1.public static void sort(Comparable[] a):对数组内的元素进行排序 2.private static boolean greater(Comparaable v,Comparable w):判断v是否大于w 3.private static void exch(Comparable[] a,int i,int j):交换a数组中,索引i和索引j处的值 |
冒泡排序代码实现
需求:
排序前{4,5,6,2,3,8,9};
排序后{2,3,4,5,6,8,9};
Bubble类
package BubbleSort;public class Bubble {public static boolean greater(Comparable v,Comparable w){return v.compareTo(w) > 0;}public static void exch(Comparable[] a,int i,int j){Comparable comp;comp = a[i];a[i] = a[j];a[j] = comp;}public static void sort(Comparable[] a){for (int i = 1; i < a.length; i++) {for (int j = 0; j < i; j++) {if (greater(a[j], a[j+1])) {exch(a,j,j+1);}}}}
}
Test类
package BubbleSort;import java.util.Arrays;public class Test {public static void main(String[] args) {Integer[] a = {4,5,6,2,3,8,9};Bubble.sort(a);System.out.println(Arrays.toString(a));}
}
**冒泡排序时间复杂度分析分析:**使用了双层嵌套for循环,内循环体为真正完成排序的代码,分析时间复杂度主要分析内层循环体即可.
在最坏情况下要循环:(N2/2-N/2)+(N2/2-N/2)=N^2-N;
用大O推到法则最终冒泡排序的时间复杂度为O(N^2).