數組排序（正數在左，負數在右）

import java.util.Arrays;
/**
 * [1,2,3,-2,-4,5,3,-2,4,1,-5,3]數組排序
 輸出結果[1,2,3,5,3,4,1,-2,-4,-2,-5]
 要求:
 1.正數在左，負數在右，
 2.相對順序不變，
 3.空間複雜度O(1)
 */
public class ArraySort {
    //arr 待排序數組，data 需要插入的資料， dataIndex待插入資料的原始下标
    public static int[] InsertArr(int arr[], int data, int dataIndex){
        for(int index = dataIndex; index < arr.length-1; index++){
            arr[index] = arr[index+1];
        }
        arr[arr.length-1] = data;
        return arr;
    }

    public static void ArrSort(int arr[]){
        boolean flag;
        for(int index = 0; index <arr.length; ){
            //如果一次子循環，沒有資料進行交換，則執行index ++,繼續向後周遊，但是如果有資料交換就不能index ++了，
            // 因為交換的該位置同樣有可能為負數，則需要繼續執行是否交換判斷邏輯
            flag = false;
            if (arr[index] < 0){
                //從左向右周遊，如果有負數，則看負數後面還有沒有正數,如果有正數，則把該負數取出，其後面的數依次前移，該負數插入到數組的最後一位
                for(int minusIndex = index; minusIndex< arr.length; minusIndex++){
                    if (arr[minusIndex] > 0){
                        //将該負數插入到數組的尾部，其餘資料依次前移
                        arr = InsertArr(arr, arr[index], index);
                        flag = true;
                        System.out.println(Arrays.toString(arr));
                        break;
                    }
                }
            }
            //如果為真就不執行index++了，繼續判斷arr[index]是否為負數
            if(flag) continue;
            index++;
        }
    }

    public static void main(String[] args) {
        System.out.println("原始數組排列順序：");
        int arr[] = {1,2,3,-2,-4,5,3,-2,4,1,-5,3};
        System.out.println(Arrays.toString(arr));
        System.out.println("排列過程：");
        ArrSort(arr);
        System.out.println("數組最後排列結果：");
        System.out.println(Arrays.toString(arr));
    }
}      

執行結果： 原始數組排列順序： [1, 2, 3, -2, -4, 5, 3, -2, 4, 1, -5, 3] 排列過程： [1, 2, 3, -4, 5, 3, -2, 4, 1, -5, 3, -2] [1, 2, 3, 5, 3, -2, 4, 1, -5, 3, -2, -4] [1, 2, 3, 5, 3, 4, 1, -5, 3, -2, -4, -2] [1, 2, 3, 5, 3, 4, 1, 3, -2, -4, -2, -5] 數組最後排列結果： [1, 2, 3, 5, 3, 4, 1, 3, -2, -4, -2, -5]

轉載于:https://www.cnblogs.com/lihao7/p/10759621.html