C++面试题（只使用0与数组中其它数交换进行排序）

糖逗

题目描述：

一个长度为n的数组，乱序存放着[0, n-1]，现在只允许0与其它数交换，将数组从小到大排序

#include <iostream>

using namespace std;


void print(int *array,int len) {
        for (int i = 0; i < len; i++) {
                cout << array[i] << " ";
        }
        cout << endl;
}


void swap_with_zero(int* array, int len, int n){
        int pos0 = 0, posn = 0;
        int cnt = 0;
        for(int i = 0; i < len; i++){
                if(array[i] == 0){
                        pos0 = i;
                        cnt++;
                }
                if(array[i] == n){
                        posn = i;
                        cnt++; 
                }
                if(cnt == 2) break;
        }
        int temp = array[pos0];
        array[pos0] = array[posn];
        array[posn] = temp;
        return;
}


void sort(int* array, int len){
        if(array[0] != 0) swap_with_zero(array, len, array[0]);
        for(int i = 1; i < len; i++){
                if(array[i] != 0){
                        if(array[i] == i) continue;
                        else{
                                swap_with_zero(array, len, array[i]);
                                swap_with_zero(array, len, i);
                        }
                } 
        }
}



int main(){
        int array[] = {5, 3, 2, 4, 1, 6, 7, 0};
        int len = sizeof(array) /sizeof(int);
        sort(array, len);
        print(array, len);
        system("pause");
        return 0;
}

注意事项：
1.这里0更多像是一个复制的前置头。