华为机试题—0交换排序

题目描述：

长度为n的数组乱序存放着0至n-1，现在只能进行0与其他数的交换，完成以下函数。

public class Solution {
    /**
     * 交换数组里n和0的位置
     * 
     * @param array
     *            数组
     * @param len
     *            数组长度
     * @param n
     *            和0交换的数
     */
    // 不要修改以下函数内容
    public void swapWithZero(int[] array, int len, int n) {
        Main.SwapWithZero(array, len, n);
    }
    // 不要修改以上函数内容


    /**
     * 通过调用swapWithZero方法来排
     * 
     * @param array
     *            存储有[0,n)的数组
     * @param len
     *            数组长度
     */
    public void sort(int[] array, int len) {
        // 完成这个函数
    }
}

思路：

循环交换。先将0与处于i位置的数字进行交换，即swapWithZero(array, len, array[i])；此时0处于i位置，然后交换0与数字i，即可让数字i归位到i位置。

代码：（只给出sort函数）

public void sort(int[] array, int len) {
    for(int i = len - 1; i > 0; i--) {
        if(array[i] == i) //判断是否处于正确位置
            continue;
        //对未处于正确位置的数字进行下面两步交换
        swapWithZero(array, len, array[i]);//交换0与i位置的数字
        swapWithZero(array, len, i);//交换0与数字i
    }
}