昨天双
11
,什么也没买。因为没有想到什么必需的用品,何况也没有钱。身为屌丝的我,只能敲敲代码,写一写总结,岂不美滋滋哉。今天看了《五亿探长雷洛》这部电影,非常喜欢刘德华饰演的雷洛,因此雷洛照片镇楼。
雷洛.jpg
3
种简单排序算法复杂度都是 O(N^2)
,不过插入排序在某种情况下会比冒泡排序,选择排序快的多。算法复杂度结果为10^8
的算法是秒级算法。O(N^2)
的算法,在数据项小于10000
时,运行才会是秒级。out
右边的所有数据项为有序。选择排序中不变性是下标小于或等于out
的数据都是有序的。插入排序中的不变性是下标比out
小的数据项是局部有序的。这里out
指的是循环中的变量。O(N^2)
排序算法中应用最多的。我们有时候需要比较对象中的关键字,来给一组对象进行排序。
Person
类。public class Person {
private String name;
private Integer age;
private Integer height;
public Person(String name, Integer age, Integer height) {
super();
this.name = name;
this.age = age;
this.height = height;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public Integer getAge() {
return age;
}
public void setAge(Integer age) {
this.age = age;
}
public Integer getHeight() {
return height;
}
public void setHeight(Integer height) {
this.height = height;
}
public void displayPerson() {
System.out.println("name:" + name + ", age:" + age + ", height:" + height);
}
}
ArrayInOb
数组类,我们是用以Person
类的name
属性为关键字去给Person类型的数组去排序,通过String
类中的compareTo()
方法按字典顺序去比较字符串,首先会比较出2
个字符串长度。ASCII
码之差,假如在第0
号位置上字符相等的话,那么就去比较第1
号位置上,以此类推。如果每个位置上字符的ASCII
码都相等的话,那么返回2
个字符串长度之差。public class ArrayInOb {
private Person[] a;
private int size;
public ArrayInOb(int max) {
a = new Person[max];
size = 0;
}
public void insert(String name, Integer age, Integer height) {
a[size] = new Person(name, age, height);
size++;
}
public void display() {
for (int j = 0; j < size; j++) {
a[j].displayPerson();
}
System.out.println("");
}
public void insertSort() {
for (int i = 0; i < size; i++) {
Person temp = a[i];
int j = i - 1;
while (j >= 0 && a[j].getName().compareTo(temp.getName()) > 0) {
a[j + 1] = a[j];
j--;
}
a[j + 1] = temp;
}
}
}
Demo
。public class ObjectSortDemo {
public static void main(String[] args) {
int maxSize = 100;
ArrayInOb arrayInOb = new ArrayInOb(maxSize);
arrayInOb.insert("garrett", 18, 173);
arrayInOb.insert("cmazxiaoma", 21, 170);
arrayInOb.insert("xiaodingding", 22, 165);
arrayInOb.insert("xiaoma", 23, 155);
System.out.println("befor sorting");
arrayInOb.display();
arrayInOb.insertSort();
System.out.println("After sorting");
arrayInOb.display();
String a = "xiaodingding";
String b = "xiaoma";
System.out.println(a.compareTo(b));
}
}
Person
对象是按name
属性去排序,从小到大。另外"xiaodingding"
和 "xiaoma"
这2
个字符串比较,在比较第0 - 3
个元素时,也就是"xiao"
这个4
字符时,它们都相等。可是比较到第4
个元素时,也就是"d"
和 "m"
时。“d”
的ASCII
码是100
,“m”
的ASCII
码是109
。它们ASCII
码之间差值是-9
,调用compareTo()
结果也就是-9
。所以”xiaodingding”
要排在”xiaoma”
的前面。image.png
题目是这样的。有一个有序的方法用来删除数组中相同的数据项,要求使用插入排序。
-1
)。0
的位置。从现在开始,算法可以忽略这个数据项,下一个相同的数据项将被移动到下标为1
的位置,以此类推。-1
)都在数组的开头部分,可以改变数组的容量并把需要的数据前移到数组下标为0
的位置。public class InsertSortDemo {
public static int a[] = new int[] { 11, 20, 5, 5, 1, 1, 2, 10, 20, 9 };
public static void main(String[] args) {
insertSortDeleteRepeatElement();
}
public static void insertSortDeleteRepeatElement() {
int count = a.length;
int repeatCount = 0;
for (int i = 0; i < count; i++) {
int temp = a[i];
int j = i - 1;
while (j >= 0 && a[j] >= temp && a[j] != -1) {
if (a[j] == temp) {
temp = -1;
repeatCount++;
}
a[j + 1] = a[j];
j--;
}
a[j + 1] = temp;
}
count -= repeatCount;
for (int k = 0; k < count; k++) {
a[k] = a[k + repeatCount];
}
for (int k = a.length - 1; k >= count; k--) {
a[k] = 0;
}
display(count);
}
public static void display(int count) {
for (int i = 0; i < count; i++) {
System.out.print(a[i] + " ");
}
System.out.println("");
}
}
-1
,while()
循环的时候过滤到-1
的数据项,把整个数组向前移动repeatCount
个单位长度并且缩小数组容量。
image.png
咸鱼也有出头天。