选择排序和冒泡排序一样都是两两进行比较，如果大于或小于就交换两个值，时间的复杂度最坏的情况都是O(n*n),最好的情况是O(n)。每一次都要进行比较两个值。目前冒泡排序和选择排序都是数据量很小进行排序，如果数据很大，就不好了。
普通版的选择排序：
- (void)creatSelectSort{
int a[11],i,j,t;
for (i = 1; i <= 10; ++i) {
a[i] = rand()%20;
}
for (i = 1;i < 10; ++i) {
int flag = i;
for (j = i+1; j <= 10; ++j) {
if (a[flag] > a[j]) {
flag = j;
}
}
if (flag != i) {
t = a[flag];
a[flag] = a[i];
a[i] = t;
}
}
for (i = 1; i <= 10; ++i) {
NSLog(@"%d",a[i]);
}
}
选择排序的改进版本
- (void)creatImpoveOneSelectSort{
int a[10],i,j,t;
for (i = 0; i < 10; ++i) {
a[i] = rand()%20;
}
int min,max;
for (i = 0;i < 10/2; ++i) {
min = i;
max = i;
for (j = i+1;j < 10-i; ++j) {
if (a[min] >= a[j]) {
min = j;
}
if (a[j] >= a[max]) {
max = j;
}
}
if (min != i) {
t = a[min];
a[min] = a[i];
a[i] = t;
if (max == i) {
max = min;
}
}
if (max != i) {
t = a[max];
a[max] = a[10-i-1];
a[10-i-1] = t;
}
}
for (i = 0; i < 10; ++i) {
NSLog(@"%d",a[i]);
}
}
改进后的版本，只需要进行n/2趟，还有要注意的是：当min !=i 的时候，要进行特殊处理，就是在交换的时候，i的值已经发生变化了，此时的最大值指向要发生变化，即max = min，如果不加判断，max != i就无法进行交换了。这一点一定要注意的，不然在相等的值，会发生错误的。
网友评论