插入排序

插入排序,与冒泡比较相似，不同的是，插入排序是一个数插入一个有序数列中，比较适合一个有序数列与一个数值的插入排序，对于无序数列的排序，还是推荐冒泡。
插入排序的基本思想是：每步将一个待排序的纪录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。

有多种分类，直接插入排序，二分插入排序等，这里简单写下直接插入排序

 C语言版

//函数声明
void insertion_sort(int array[], int first, int last);

int array[11] = {23, 8, 90, 12, 7, -9, 54, 3, 36, 99, -17};
    
    //调用
    insertion_sort(array, 0, 10);
    
    printf("sort result:");
    for (int p = 0; p < 11; p++) {
        printf(" %d", array[p]);
    }
    printf("
");
    //sort result: -17 -9 3 7 8 12 23 36 54 90 99

void insertion_sort(int array[], int first, int last) {
    int i = 0, j = 0;
    int temp = 0;
    for(i = first + 1; i <= last; i++)
    {
        temp = array[i];
        j    = i - 1;
        
        //array[j]大于temp的数时，把大于temp的数向后移动一位到array[j+1],然后把temp放在array[j]处
        //与已排序的数逐一比较，大于temp时，该数移后
        while((j >= 0) && (array[j] > temp))
        {
            array[j+1] = array[j];
            j--;
        }
        
        //存在大于temp的数 把temp放在前面的位置
        if(j!=i-1) {
            array[j+1] = temp;
        }
    }
}

OC版

_dataArray = [NSMutableArray arrayWithObjects:@21, @3, @34, @(-28), @10, @(-33), @54, @9, @0, @(-2),  nil];

//调用
[self insertSort];
    
NSString *string = [self.dataArray componentsJoinedByString:@" "];
NSLog(@"sort result : %@", string);
//sort result : -33 -28 -2 0 3 9 10 21 34 54

- (void)insertSort {
    NSInteger i = 0, j = 0;
    NSInteger temp = 0;
    for (int k = 0; k < self.dataArray.count; k++) {
        NSNumber *number = [NSNumber numberWithInteger:[self.dataArray[k] integerValue]];
        self.dataArray[k] = number;
    }
    for (i = 1; i < self.dataArray.count; i++) {
        temp = [self.dataArray[i] integerValue];
        j    = i - 1;
        
        while ((j >= 0) && ([self.dataArray[j] integerValue] > temp)) {
            self.dataArray[j+1] = self.dataArray[j];
            j--;
        }
        
        if (j != i-1) {
            self.dataArray[j+1] = [NSNumber numberWithInteger:temp];
        }
    }
}

 swift版

var dataArray:NSMutableArray = [76, 1, 19, -4, 2, 4, 6, 8, 0, -19];

//调用
self.insertSort();
let string:NSString = dataArray.componentsJoinedByString(" ");
NSLog("sort result: %@", string);
//sort result: -19 -4 0 1 2 4 6 8 19 76

func insertSort() {
    var j:NSInteger = 0;
    var temp:NSInteger = 0;
    
    for k:NSInteger in 0 ..< dataArray.count {
        let currentNumber:NSNumber = NSNumber.init(integer: dataArray[k].integerValue);
        dataArray[k] = currentNumber;
    }
    
    for i:NSInteger in 1..<dataArray.count {
        temp = dataArray[i].integerValue;
        j    = i - 1;
        
        while ((j >= 0) && (dataArray[j].integerValue > temp)) {
            dataArray[j+1] = dataArray[j];
            j-=1;
        }
        
        if j != (i-1) {
            dataArray[j+1] = NSNumber.init(integer: temp);
        }
    }
}