摆动排序

摆动排序一

描述

---

给你一个没有排序的数组，请将原数组就地重新排列满足如下性质
nums[0] <= nums[1] >= nums[2] <= nums[3]….

---

分析

---

先对数组进行排序，然后依次把两两相邻的元素进行交换，最终成为一个波动递增的数列，满足题目要求

1 2 3 4 5 6 7 8 9
1 3 2 5 4 7 6 9 8

---

实现

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;
        }
    }

摆动排序二

描述

---

给你一个数组nums，将它重排列如下形式
nums[0] < nums[1] > nums[2] < nums[3]….

---

分析

---

和摆动排序一的区别是 没有等于
先元素排序，然后把元素按照中心轴切分开，把前半部分元素正向插入1,3,5…，把后半部分元素正向插入2,4,6…

1.前半部分插入 1 3 5 位置，后半部分 从前往后插入 2 4 6 8
1 2 3 4 5 6 7 8 9
1 6 2 7 3 8 4 9 5

2.前半部分插入 1 3 5 位置，后半部分从后往前插入 2 4 6 8
1 2 3 4 5 6 7 8 9
1 9 2 8 3 7 4 6 5

3.前半部分的偶数位置和后半部分的奇数部分互换
1 2 3 4 5 6 7 8 9
1 7 3 9 5 6 2 8 4

4.前半部分的偶数位置和后半部分的奇数部分互换
1 2 3 4 5 6 7 8 9
1 9 3 7 5 6 4 8 2

---

实现

cpp