插入排序

插入排序的核心思路

• 首先我们将数组中的数据分为两个分区:已排序区间和未排序区间。初始已排序区间只有一个元素。就是数组中的第一个元素。插入排序的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序，重复这个过程，知道未排序区间中的元素为空，则排序结束

插入排序的操作流程

• 假设要对一个数组a[6]进行排序。首先确定数组的第一个元素属于已排序区间。剩下的元素为未排序区间。在未排序区间中取第一个元素，即a[1]，与已排序区间中的元素从后向前依次比较。假如a[1]<a[0],则将a[0]向后移动一位。如果a[1]>a[0],则a[1]插入在a[0]后面。
• 上一步操作已经将数组中a[0]和a[1]排好序了。此时取到a[2]，用a[2]和a[1]进行比较，如果a[1]>a[2]，则a[1]向后移动一位，继续比较a[2]和a[0],如果a[0]<a[2]，则将a[2]插入到a[1]的位置。这样就排好了数组的前三个元素。
• 重复以上操作，直到未排序区间的元素为空则排序结束。

插入排序的相关

• 插入排序是原地排序算法，是稳定排序算法。
• 插入排序的平均时间复杂度为O(n²)。

简单的代码实现

- (void)insertionSort
{
    NSMutableArray *numberArray = [NSMutableArray arrayWithArray:@[@5,@1,@6,@2,@4,@3]];
    
    NSLog(@"排序之前的结果:%@",numberArray);
    
    for (int i = 1; i < numberArray.count; i++) {
        
        NSNumber *value = numberArray[i];
        
        int j = i-1;
        
        for (; j>= 0; j--) {
            
            if ([numberArray[j] intValue] > [value intValue]) {
                
                numberArray[j+1] = numberArray[j];
            }else {
                
                break;
            }
            
        }
        
        numberArray[j+1] = value;
        
    }
    
    NSLog(@"排序之后的结果:%@",numberArray);
}