插入排序
插入排序法（Inser Sort）是將一個數(shù)據(jù)插入到已經(jīng)排好序的有序數(shù)據(jù)中昌妹，從而得到一個新的捶枢、個數(shù)加一的有序數(shù)據(jù)握截，算法適用于少量數(shù)據(jù)的排序。
算法思想
從第一個元素開始烂叔，認為該元素已經(jīng)是排好序的谨胞。
取下一個元素，在已經(jīng)排好序的元素序列中從后向前掃描蒜鸡。
如果已經(jīng)排好序的序列中元素大于新元素畜眨，則將該元素往右移動一個位置。
重復上一步驟术瓮，直到已排好序的元素小于或等于新元素康聂。
在當前位置插入新元素。
重復"取下一個元素胞四，在已經(jīng)排好序的元素序列中從后向前掃描"過程恬汁。
范例代碼
/**
插入排序
@param array 需要排序的Array
*/
+ (void)inserSort:(NSMutableArray *)array{
//插入排序的原理：始終定義第一個元素為有序的，將元素逐個插入到有序排列之中辜伟，其特點是要不斷的
//移動數(shù)據(jù)氓侧，空出一個適當?shù)奈恢茫汛迦氲脑胤诺嚼锩嫒ァ? for (int i = 0; i < array.count; i++) {
NSNumber *temp = array[i];
//temp 為待排元素 i為其位置 j為已排元素最后一個元素的位置（即取下一個元素导狡，在已經(jīng)排好序的元素序列中從后向前掃描）
int j = i-1;
//當j < 0 時约巷， i 為第一個元素 該元素認為已經(jīng)是排好序的 所以不進入while循環(huán)
// [array[j] compare:temp] == NSOrderedDescending與[array[j] intValue] > [temp intValue] 作用相同
while (j >= 0 && [array[j] compare:temp] == NSOrderedDescending) {
//如果已經(jīng)排好序的序列中元素大于新元素，則將該元素往右移動一個位置
[array replaceObjectAtIndex:j+1 withObject:array[j]];
j--;
}
//跳出while循環(huán)時旱捧，j的元素小于或等于i的元素(待排元素)独郎。插入新元素 i= j+1
[array replaceObjectAtIndex:j+1 withObject:temp];
NSLog(@"插入排序排序中:%@",array);
}
}
算法分析
-
直接插入排序的算法性能
-
時間復雜度
當元素的初始序列為正序時，僅外循環(huán)要進行n-1趟排序且每一趟只進行一次比較枚赡，沒有進入if語句不存在元素之間的交換(移動)氓癌。此時比較次數(shù)(Cmin)和移動次數(shù)(Mmin)達到最小值。 此時時間復雜度為O(n)贫橙。
Cmin = n-1; Mmin = 0;當元素的初始序列為反序時贪婉，每趟排序中待插入的元素都要和[0,i-1]中的i個元素進行比較且要將這i個元素后移(arr[j+1] = arr[j])，i個元素后移移動次數(shù)當然也就為i了卢肃，再加上temp = arr[i]與arr[j+1] = temp的兩次移動疲迂，每趟移動的次數(shù)為i+2,此時比較次數(shù)(Cmin)和移動次數(shù)(Mmin)達到最小值。 此時時間復雜度為O(n2)莫湘。
Cmax = 1+2+...+(n-1) = n*(n-1)/2 = O(n2) Mmax = (1+2)+(2+2)+...+(n-1+2) = (n-1)*(n+4)/2 = O(n2) (i取值范圍1~n-1)數(shù)據(jù)越接近正序尤蒿，直接插入排序的算法性能越好。
-
空間復雜度
由直接插入排序算法可知逊脯，我們在排序過程中优质，需要一個臨時變量存儲要插入的值竣贪，所以空間復雜度為 O(1) 军洼。
-
算法穩(wěn)定性
直接插入排序的過程中巩螃，不需要改變相等數(shù)值元素的位置，所以它是穩(wěn)定的算法匕争。
插入排序和選擇排序的區(qū)別
插入排序和選擇排序都有兩層循環(huán)避乏，外循環(huán)遍歷整個數(shù)組，內(nèi)循環(huán)稍有區(qū)別：
選擇排序的內(nèi)循環(huán)是遍歷一組未排過序的數(shù)組甘桑。
插入排序的內(nèi)循環(huán)是遍歷一組已排過序的數(shù)組拍皮。
