插入排序和冒泡排序都比較簡(jiǎn)單，但是時(shí)間復(fù)雜度有點(diǎn)高衡楞。
首先是冒泡排序吱雏，是通過相鄰的兩個(gè)數(shù)字進(jìn)行比較，每一趟之后瘾境，待排序的部分的最大值將會(huì)到后面去歧杏，這樣就可以每一趟確定一個(gè)數(shù)字，在n-1趟之后迷守，就完成了排序工作犬绒。
如：2 ? ? 32 ? 43 ? 5 ? ? 21
第一趟：2 32 43 5 21 ? ? 2 32 43 5 21 ? ? ?2 32 5 43 21 ? ? ?2 32 5 21 43
第二趟：2 32 5 21 43 ? ? 2 ?5 32 21 43 ? ?2 5 21 32 43?
第三趟：2 5 21 32 43 ? ?2 5 21 32 43 ?
第四趟：2 5 21 32 43?
可以看到其實(shí)每一趟是待排序列或子序列下沉的過程。
時(shí)間復(fù)雜度是T(N)=N-1+N-2+......+1=o(N^2)
java實(shí)現(xiàn)
public static void bubble_sort(int [] arr){
int tem=0;
for(int i=0;i<arr.length-1;i++){
for(int j=0;j<arr.length-i-1,j++){
? ? if(arr[j]>arr[j+1]){
tem=arr[j];
arr[j]=arr[j+1];
arr[j+1]=tem;
}
}
}
}
插入排序兑凿，插入排序的每一趟的結(jié)果是將一個(gè)待排的數(shù)正確的插入到已經(jīng)排序好的序列中凯力。例如，待排序列：8 ?6 ?3 ?9 ?2
第一趟 ? ? ? ? ? 6 ?8
第二趟 ? ? ? ? ?3 6 8
第三趟 ? ? ? ? ?3 6 8 9
第四趟 ? ? ? ? 2 3 6 8 9
所以礼华，這種插入排序的需要進(jìn)行N-1次的遍歷咐鹤，時(shí)間復(fù)雜度是T（N）=1+2+.......+N-1=o(N^2)
在實(shí)現(xiàn)的過程中，為了減少空間的占用圣絮，整個(gè)排序只在一個(gè)數(shù)組內(nèi)完成祈惶，數(shù)據(jù)的第一個(gè)數(shù)默認(rèn)為是有序的，然后從數(shù)組的第二個(gè)數(shù)開始扮匠，和前面的已經(jīng)排序好的數(shù)字進(jìn)行比較捧请，在每一次比較的過程中，如果發(fā)現(xiàn)待排的數(shù)字與比較的數(shù)字比更小棒搜，說明這個(gè)待排數(shù)字的正確位置是在這個(gè)比較數(shù)字的前面疹蛉，然后將這個(gè)數(shù)右移一位，然后待排數(shù)再和前面一個(gè)數(shù)比較力麸，如果發(fā)現(xiàn)更小可款，繼續(xù)將這個(gè)右移。這樣等于是將已經(jīng)比較過的這些數(shù)整體右移的一個(gè)位置末盔，而由于待排的數(shù)字剛好是在已經(jīng)排序好的序列的后面，所以這樣做是有位置的座慰，同時(shí)如果在比較的過程中發(fā)現(xiàn)了待排數(shù)字和比較數(shù)字相比更大陨舱，說明這個(gè)待排數(shù)字是在這個(gè)已派數(shù)字的后面，而與之前的已排數(shù)字相比版仔，這個(gè)又比前一個(gè)已經(jīng)右移一位的已排數(shù)字的位置更杏蚊ぁ（不然也不會(huì)繼續(xù)比較前面的一個(gè)）误墓，所以這個(gè)待排數(shù)字的正確位置就確定下來了，就是之前這個(gè)右移一位所空下來的位置的數(shù)原先所在數(shù)的位置益缎。
java實(shí)現(xiàn)
public static void insert_sort(int [] arr){
for(int i=1;i<=arr.length-1;i++){
int j;
int tem=arr[i];//保存待排的一個(gè)備份谜慌，因?yàn)橛乙频臅r(shí)候原來的值會(huì)被前面的值覆蓋
for(j=i-1;j>=0&&arr[j]>=tem;j--){
arr[j+1]=arr[j];
}
arr[j+1]=tem;
}
}
這種也稱為直接的插入排序，但是這種方法每一次待排的數(shù)字在找到其正確位置時(shí)莺奔，需要一個(gè)一個(gè)順序的和原來的序列的值從頭到尾或者從尾到頭進(jìn)行比較欣范，還有一種優(yōu)化的插入排序是，在尋找待排數(shù)字在已經(jīng)排好的序列正確位置的時(shí)候令哟，為了減少比較次數(shù)恼琼，采用二分查找的方式，選擇已派序列中間的數(shù)和待排數(shù)字進(jìn)行比較屏富，如果待排數(shù)字更大晴竞，則其應(yīng)該位于這個(gè)中間數(shù)字到尾部的區(qū)域，繼續(xù)二分狠半，直到可以確定位置以后噩死，將序列整體右移1位，插入神年。
public static void(int [] arr){
for(int i=1;i<=arr.length-1;i++){
?int left=0;
int temp=arr[i];
int right=i-1;
int mid;
while(left<=right){ ? ? ? ? ?//二分查找位置已维，
mid=(left+right)/2;
if(arr[mid]>=arr[i])
right=mid-1;
else
left=mid+1;
} ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? //退出循環(huán)的條件的前一次是，left和right指向一個(gè)元素瘤袖，然后比較它和待排元素的大小衣摩，如果待排更大，則left會(huì)變得更 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 大捂敌，待排應(yīng)該插在其右邊艾扮，如果待排更小占婉，則right會(huì)變得更小泡嘴，待排應(yīng)該插到其左邊。不管如何逆济，都是查到最終left的左 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 邊
for(int j=i-1;j>=left;j--){
arr[j+1]=arr[j];
}
arr[left]=temp;
}
}
