问题描述

有一个长度为2n的数组{a1, a2, a3, ..., an, b1, b2, b3, ..., bn}，希望排序后变成{a1, b1, a2, b2, a3, b3, ..., an, bn}。请考虑有没有时间复杂度为O(n)而空间复杂度为O(1)的解法。

解决方案

位置置换算法

下面算法的时间复杂度为O(n)，空间复杂度为O(n)。

算法代码

package com.liuzhen.practice;public class Main {    public void getLocationReplace(String[] A) {        int len = A.length;        String[] temp = new String[len];        for (int i = 1; i < len; i++) {            temp[(2 * i) % len] = A[i];        }        for (int i = 1; i < len; i++) {            A[i] = temp[i];        }        for (int i = 1; i < len; i = i + 2) {            String a1 = A[i];            A[i] = A[i + 1];            A[i + 1] = a1;        }    }    public static void main(String[] args) {        Main test = new Main();        String[] A = {"", "a1", "a2", "a3", "a4", "a5", "b1", "b2", "b3", "b4", "b5"};        test.getLocationReplace(A);        for (int i = 1; i < A.length; i++) {            System.out.print(A[i] + " ");        }    }}

运行结果

a1 b1 a2 b2 a3 b3 a4 b4 a5 b5

走环算法

下面算法的时间复杂度为O(n)，空间复杂度为O(1)。

算法代码

package com.liuzhen.practice;public class Main1 {    public void CycleLeader(String[] A, int start, int mod) {        for (int i = start * 2 % mod; i != start; i = i * 2 % mod) {            String temp = A[i];            A[i] = A[start];            A[start] = temp;        }        return;    }    public void Reverse(String[] A, int start, int end) {        while (start < end) {            String temp = A[start];            A[start++] = A[end];            A[end--] = temp;        }        return;    }    public void RightRotate(String[] A, int start, int m, int n) {        Reverse(A, start + m + 1, start + n);        Reverse(A, start + n + 1, start + n + m);        Reverse(A, start + m + 1, start + n + m);        return;    }    public void PerfectShuffle(String[] A) {        int len = A.length;        int n = (len - 1) / 2;        int start = 0;        while (n > 1) {            int k = 0, m = 1;            for (; (len - 1) / m >= 3; k++, m = m * 3) {            }            m = m / 2;            RightRotate(A, start, m, n);            for (int i = 0, t = 1; i < k; i++, t = t * 3) {                CycleLeader(A, t, m * 2 + 1);            }            start = start + m * 2;            n = n - m;        }        if (n == 1) {            String temp = A[1 + start];            A[1 + start] = A[2 + start];            A[2 + start] = temp;        }        for (int i = 1; i < len; i = i + 2) {            String a1 = A[i];            A[i] = A[i + 1];            A[i + 1] = a1;        }        return;    }    public static void main(String[] args) {        Main1 test = new Main1();        String[] A = {"", "a1", "a2", "a3", "a4", "a5", "b1", "b2", "b3", "b4", "b5"};        test.PerfectShuffle(A);        for (int i = 1; i < A.length; i++) {            System.out.print(A[i] + " ");        }    }}

运行结果

a1 b1 a2 b2 a3 b3 a4 b4 a5 b5

总结

本文探讨了两种排序数组的方法：位置置换算法和走环算法。位置置换算法虽然实现简单，但空间复杂度为O(n)。走环算法实现复杂，但空间复杂度为O(1)，更符合用户要求。

转载地址：http://brvyz.baihongyu.com/

你可能感兴趣的文章