按照特定的某种方式对一个数组里面的数值排序

发表于

Question

  • 有一个数组，例如是{1，3，2，4，6，7，5，9}，排序后数组为{9，7，4，3，1，2，6，5}，请找出该数组的排序规律并用代码实现排序！

Answer

  • 首先说说基本思路

    首先看两组数据的变换规律，它是以第一个数字为中心变换，找到数组的长度len，将第一个数字设置在下标为len/2的位置，然后，用两个变量，left = len/2 - 1，right = len/2 + 1; 按照原有数组的顺序，依次赋值给num[left]并left–，num[right]并right–，直至原有数组所有的数字都被操作完。。。结果正确了，但是你会发现，空间复杂度是真的高。。。所以我们需要想想，怎么优化。

  • 再升级一下思路

    那怎么优化呢，看来主要是空间复杂度上面进行优化了，对，还记得插入排序的思路没？对，就是按照那个思路，首先找到第一个数字要放置的位置len/2，设置一个变量tmp, 再用for循环遍历，从第二个值即num[1]开始，依次遍历，如果是编号i为奇数的，那么从0到编号i，tmp = num[i], 从0到i-1每个位置依次后移一个位置，最后将num[0] = tmp, 如果编号i为奇数，则不管它，那么就只需要 一个变量，但是我发现好像时间复杂度变长了，得套用两个for循环。

  • 以下是两种思路的代码实现

方式一

static void fun(int[] num){
    int len = num.length;
    int[] data = new int[len + 1];
    int tmpLoc = len / 2;
    data[tmpLoc] = num[0];
    int left = tmpLoc - 1,right = tmpLoc + 1;
    for(int i = 1; i < len; i ++){
        data[left--] = num[i];
        if (i < len - 1){
            i ++;
        }
        data[right] = num[i];
        if (right < len){
            right ++;
        }
    }

    for(int i = 0; i < len; i ++){
        System.out.print(data[i] + " ");
    }
}

方式二

static void fun2(int[] num){
    int len  = num.length;
    int tmp;
    for (int i = 1; i < len; i ++){
        tmp = num[i];
        if (i % 2 != 0){
            for (int j = i; j > 0; j --){
                num[j] = num[j - 1];

            }
            num[0] = tmp;
        }

    }

    for(int i = 0; i < len; i ++){
        System.out.print(num[i] + " ");
    }
}
  • 以上就是两个思路以及两种解决方案的代码啦。。突然间发现，方法二不加 i % 2 ！= 0 的条件，就可以反转数组啦。。。哈哈哈！新大陆呀