摆动排序 I
给你一个没有排序的数组，请将原数组就地重新排列满足如下性质
nums[0] <= nums[1] >= nums[2] <= nums[3]....
允许相邻元素相等
思路
先对数组进行排序，然后依次把两两相邻的元素进行交换，最终成为一个波动递增的数列，满足题目要求
实现
public void wiggleSort(int[] nums) {
// write your code here
//先对数组进行排序
Arrays.sort(nums);
//然后依次把i和i+1的元素进行交换，就可以得到一个摆动排序
for (int i=1;i<nums.length-1;i=i+2) {
int temp = nums[i];
nums[i] = nums[i + 1];
nums[i + 1] = temp;
}
}
摆动排序 II
给你一个数组nums，将它重排列如下形式
nums[0] < nums[1] > nums[2] < nums[3]....
样例
给出 nums = [1, 5, 1, 1, 6, 4],一种方案为 [1, 4, 1, 5, 1, 6].
给出 nums = [1, 3, 2, 2, 3, 1],一种方案为 [2, 3, 1, 3, 1, 2].
思路
先元素排序，然后把元素按照中心轴切分开，把前半部分元素正向插入1,3,5...，把后半部分元素正向插入2,4,6...
你可以想象一个直角三角形，从中间切开之后，把较小的部分穿插进较大的部分，形成一个波动的图像。
实现
public void wiggleSort(int[] nums) {
// write your code here
//边界
if (nums.length <= 1) {
return;
}
//先对数组进行排序
Arrays.sort(nums);
//取中心轴
int axis = nums.length / 2;
//创建结果数组
int[] result = new int[nums.length];
if (nums.length % 2 == 0) {
//如果数组长度为偶数
//把前半部分元素正向插入1,3,5...
int j = 0;
for (int i = 0; i < axis; i++) {
result[j] = nums[i];
j = j + 2;
}
//把后半部分元素正向插入2,4,6...
int k = 1;
for (int i = axis; i < nums.length; i++) {
result[k] = nums[i];
k = k + 2;
}
} else {
//如果数组长度为奇数
//把前半部分元素正向插入1,3,5...
int j = 0;
for (int i = 0; i <= axis; i++) {
result[j] = nums[i];
j = j + 2;
}
//把后半部分元素正向插入2,4,6...
int k = 1;
for (int i = axis + 1; i < nums.length; i++) {
result[k] = nums[i];
k = k + 2;
}
}
for (int i=1;i<nums.length;i++) {
if (result[i] == result[i - 1]) {
//假如出现了这种边界情况 4 5 5 6 要想办法转化成 5 6 4 5
//把6移到第一个5的位置
int temp = result[i + 1];
result[i + 1] = result[i - 1];
result[i - 1] = temp;
//把4移到第二个5的位置
int tepo = result[i];
result[i] = result[i - 2];
result[i - 2] = tepo;
}
}
System.arraycopy(result,0,nums,0,nums.length);
}
基于上一个思路的代码改进
较上一思路，这次采用了从大端到小端的逆向插入
相当于把上一个思路中的递增三角形进行了水平翻转，变成一个递减三角形，分成两半，穿插成一个波动图像
同时也巧妙避开了 4 5 5 6 的问题
public static void wiggleSort(int[] nums) {
int n = nums.length;
if(n == 0) return ;
int[] a = Arrays.copyOfRange(nums,0,n);
Arrays.sort(a);
int k = 0 , p = (n-1)/2, q = n-1;
boolean sign = true;
//sign控制交替赋值
while(k < n){
if(sign) nums[k++]=a[p--];
else nums[k++]=a[q--];
sign = !sign;
}
printArray(nums);
}
如果觉得文章对你有帮助的话，不要忘了打赏小编哟
