首页 > 代码库 > iOS 面试题之冒泡排序

iOS 面试题之冒泡排序

每次笔试,80%的笔试上总会提到冒泡排序。

先写一个教科版本的:

    // [冒泡排序] 细节:内层循环注意!!!
    int array[] = {3, 2, 5, 9, 7, 6};
    int length = sizeof(array) / sizeof(array[0]);
    for (int i = 0 ; i < length - 1; i ++) {
        for ( int j = 0; j < length - 1 - i ; j ++) {
            if (array[j] > array[j + 1]) {
                int temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }
    for ( int i = 0; i < length; i ++) {
        printf("%d", array[i]);
    }

之后在面试官看完之后,他说了这么一句话,假如是个有序数组,那这样的效率是不是降低了?

我就又改了改

    for (int i = 0 ; i < length - 1; i ++) {
        int flag = 0;
        for (int j = 0 ; j < length - 1 - i; j ++) {
            if (array[j] > array[j + 1]) {
                swap(array + j, array + j + 1);
                flag ++;
            }
        }
        printf("%d\n", flag);
        if (flag == 0) {
            break;
        }
    }

看完之后,他说,还能更简单点。。。这就折磨我了。。。想半天没想到,他最后给我看的是这样一串代码,觉得受益匪浅就记下了。

    int flag = 1;
    for (int i = 0 ; i < length - 1 && 1 == flag; i ++) {
        flag = 0;
        for (int j = 0; j < length - 1 - i;  j ++) {
            if (array[j] > array[j + 1]) {
                swap(array + j, array + j + 1);
                flag = 1;
            }
        }
    }


iOS 面试题之冒泡排序