前言
昨天雙
11凉馆，什么也沒買。因為沒有想到什么必需的用品亡资，何況也沒有錢澜共。身為屌絲的我，只能敲敲代碼锥腻，寫一寫總結(jié)嗦董，豈不美滋滋哉。今天看了《五億探長雷洛》這部電影瘦黑，非常喜歡劉德華飾演的雷洛京革，因此雷洛照片鎮(zhèn)樓。
幾種簡單排序的比較
一般情況幾乎不太使用冒泡排序算法幸斥，它過于簡單了匹摇。當(dāng)數(shù)據(jù)量很小的時候，它會有些應(yīng)用價值甲葬。
選擇排序雖然把交換次數(shù)降到了最低廊勃，但比較的次數(shù)仍然很大。當(dāng)數(shù)據(jù)量很小经窖，并且交換次數(shù)相當(dāng)于比較數(shù)據(jù)更加耗時的情況下坡垫，可以應(yīng)用選擇排序。
但數(shù)據(jù)量比較小或基本上有序時画侣，插入排序算法是三種簡單排序算法中最好的選擇冰悠。
歸納
這幾種簡單排序算法中都假定了數(shù)據(jù)作為數(shù)據(jù)存儲結(jié)構(gòu)。
排序包括比較數(shù)組中數(shù)據(jù)項的關(guān)鍵字和移動相應(yīng)的數(shù)據(jù)項配乱，直到它們排好序為止溉卓。
這
3種簡單排序算法復(fù)雜度都是O(N^2),不過插入排序在某種情況下會比冒泡排序皮迟，選擇排序快的多。算法復(fù)雜度結(jié)果為10^8的算法是秒級算法的诵。O(N^2)的算法万栅，在數(shù)據(jù)項小于10000時佑钾，運行才會是秒級西疤。不變性是指算法運行時保持不變的條件。冒泡排序的不變性是
out右邊的所有數(shù)據(jù)項為有序休溶。選擇排序中不變性是下標小于或等于out的數(shù)據(jù)都是有序的代赁。插入排序中的不變性是下標比out小的數(shù)據(jù)項是局部有序的。這里out指的是循環(huán)中的變量兽掰。冒泡排序是效率最差的算法芭碍，但它是最簡單的。
插入排序算法是
O(N^2)排序算法中應(yīng)用最多的孽尽。如果具有相同關(guān)鍵字的數(shù)據(jù)項窖壕，經(jīng)過排序他們的順序保持不變，這樣的排序就是穩(wěn)定的杉女。
這幾種排序中瞻讽，除了需要初始數(shù)組之外，還需要一個臨時變量熏挎。
對象排序
我們有時候需要比較對象中的關(guān)鍵字速勇，來給一組對象進行排序。
- 先定義一個
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數(shù)組類烦磁，我們是用以Person類的name屬性為關(guān)鍵字去給Person類型的數(shù)組去排序，通過String類中的compareTo()方法按字典順序去比較字符串哼勇，首先會比較出2個字符串長度都伪。在較短的字符串長度之內(nèi)，去比較兩者每一個位置上的字符是否相等积担。如果不相等院溺，則直接返回該位置上字符的
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));
}
}
- 運行撮躁，輸出結(jié)果漱病。很明顯看到一組
Person對象是按name屬性去排序，從小到大。另外"xiaodingding"和"xiaoma"這2個字符串比較杨帽，在比較第0 - 3個元素時昔瞧，也就是"xiao"這個4字符時蜒犯，它們都相等。可是比較到第4個元素時枪向，也就是"d"和"m"時虚婿。“d”的ASCII碼是100屋剑，“m”的ASCII碼是109茵臭。它們ASCII碼之間差值是-9，調(diào)用compareTo()結(jié)果也就是-9胧砰。所以”xiaodingding”要排在”xiaoma”的前面鳍鸵。
關(guān)于插入排序的題目
題目是這樣的。有一個有序的方法用來刪除數(shù)組中相同的數(shù)據(jù)項尉间，要求使用插入排序偿乖。
解題思路
插入排序算法中用一個循環(huán)嵌套算法，將數(shù)組中的每一個數(shù)據(jù)項與其他數(shù)據(jù)項一一比較哲嘲。
當(dāng)找到一個重復(fù)數(shù)據(jù)項的時候贪薪，通常用一個小于任何值的關(guān)鍵字才改寫這個相同項(如果所有值都是正數(shù)，那么可以取
-1)撤蚊。一般的插入排序算法就會像處理其他數(shù)據(jù)項一樣古掏，來處理這個修改了關(guān)鍵值的數(shù)據(jù)項，把它移動下標為
0的位置侦啸。從現(xiàn)在開始槽唾，算法可以忽略這個數(shù)據(jù)項，下一個相同的數(shù)據(jù)項將被移動到下標為1的位置光涂，以此類推庞萍。排序完成之后，所有相同的數(shù)據(jù)項(關(guān)鍵字為
-1)都在數(shù)組的開頭部分忘闻，可以改變數(shù)組的容量并把需要的數(shù)據(jù)前移到數(shù)組下標為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("");
}
}
- 運行，輸出結(jié)果齐佳。這一題的關(guān)鍵就是找出重復(fù)的元素并且賦值為
-1私恬，while()循環(huán)的時候過濾到-1的數(shù)據(jù)項，把整個數(shù)組向前移動repeatCount個單位長度并且縮小數(shù)組容量炼吴。
image.png
尾言
咸魚也有出頭天本鸣。
