排序 --- 选择排序

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。

`排序算法稳定性`  假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

选择排序.gif

算法实现-C

void select_sort(int*a,int n)  {
    register int i,j,min,t;
    for(i=0;i<n-1;i++)  {
        min=i;//查找最小值
        for(j=i+1;j<n;j++) {
            if(a[min]>a[j]) {
                min=j;//交换
            }
         }

        if(min!=i) {
            t=a[min];
            a[min]=a[I];
            a[i]=t;
        }
    }
}

算法实现-OC

- (void)k_xuanzePaiXu {
    
    NSMutableArray *originalArr = [NSMutableArray arrayWithArray:@[@"5",@"4",@"9",@"8",@"1"]];
    NSInteger minValue;
    
    for (int i = 0; i < originalArr.count-1; i++) {
        minValue = I ;
        for (int j = i+1; j<originalArr.count; j++) {
            if ([originalArr[minValue] integerValue]> [originalArr[j] integerValue]) {
                minValue = j;
            }
        }
        
        if (minValue != i) {
            NSString *temp = originalArr[minValue];
            originalArr[minValue] = originalArr[i];
            originalArr[i] = temp;
        }
    }
    
    NSLog(@"++++ %@",originalArr);
}

输出结果：(
    1,
    4,
    5,
    8,
    9
)

时间复杂度分析

从选择排序的过程来看，它最大的特点就是交换移动数据次数相对少，这样也就节约了相应的时间。分析它的时间复杂度发现，无论最好最差的情况，其比较次数都是一样的多，第i趟排序需要 n-i 次关键字的比较，此时需要 3.png

而对于交换次数而言，当最好的时候，交换为0次；最差的时候，也就是降序时， 交换次数为n-1 次，基于最终的排序时间是 比较与交换的次数总和, 因此，时间复杂度为O(n²)

参考文章