稳定排序的应用

题目 输入任意数字组成的数组,将该数组前半部分全部变成偶数,后半部分变成奇数输出

1. Code

说应用,代码多少是要改的,用思想!

import java.util.*;
public class Test{
    // 交换类:冒泡/快速
    // 插入类:直接插入/折半插入/希尔排序
    // 选择类:直接选择/堆排序
    // 其他:基数排序/二分归并
    // 稳定:冒泡/直接插入/希尔排序/二分归并/基数排序
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        List<Integer> list = new ArrayList<Integer>();
        int temp=in.nextInt();
        while(temp!=-1){
            list.add(temp);
            temp=in.nextInt();
        }
        int[] arr = new int[list.size()];
        for(int i=0; i<list.size(); i++)
            arr[i]=list.get(i);
        BubbleSort(arr);
        System.out.println();
        InsertSort(arr);
        System.out.println();
        SpaceSort(arr);
       in.close();
    }

• 冒泡排序

    public static void BubbleSort(int[] arr){
        for(int i=0; i<arr.length;i++){
            for(int j=0; j<arr.length-1-i;j++){
                int temp=0;
                // 前偶后奇就交换
                if(arr[j] %2==0 && arr[j+1] %2==1){
                    temp = arr[j+1];
                    arr[j+1] = arr[j];
                    arr[j]= temp; 
                }
            }
        }
        for(int i=0;i<arr.length;i++){
            System.out.print(arr[i]+" ");            
        }
    }

• 直接插入排序

    public static void InsertSort(int[] arr){
        int nextOddIndex=0;
        int possibleOddIndex=0;
        for(int i=0;i<arr.length;i++){
            if(arr[i]%2==1){
                nextOddIndex = i;
                while(nextOddIndex > possibleOddIndex){
                    int temp = arr[nextOddIndex];
                    arr[nextOddIndex] = arr[nextOddIndex-1];
                    arr[nextOddIndex-1] = temp;
                    nextOddIndex--;
                }
                possibleOddIndex++;
            }
        }
        for(int i=0;i<arr.length;i++){
            System.out.print(arr[i]+" ");            
        }
    } 

• 以空间换时间(新建一个数组)

    public static void SpaceSort(int[] arr){
        int oddBegin=0,oddEnd=0;
        for(int i=0;i<arr.length;i++){
            if(arr[i]%2==0)
                oddEnd++;
        }
        int[] sorted = new int[arr.length];
        for(int i=0;i<arr.length;i++){
            if(arr[i] %2== 1){
                sorted[oddBegin] =arr[i];
                oddBegin++;
            }else{
                sorted[oddEnd] = arr[i];
                oddEnd++;
            }
        }
        arr = sorted;
        for(int i=0;i<arr.length;i++){
            System.out.print(arr[i]+" ");            
        }
    }
}

/**
 * Main method to demonstrate the rearrangeArray functionality.
 */
public static void main(String[] args) {
    int[] arr = {1, 2, 3, 4, 5, 6, 7, 8};
    rearrangeArray(arr);
    System.out.println(Arrays.toString(arr));
}
 
/**
 * Rearranges the array so that the first half contains only even numbers and the second half contains only odd numbers.
 *
 * @param arr The input array to be rearranged.
 */
public static void rearrangeArray(int[] arr) {
    int middleIndex = arr.length / 2;
    int leftIndex = 0;
    int rightIndex = middleIndex;
 
    while (leftIndex < middleIndex && rightIndex < arr.length) {
        leftIndex = processLeftHalf(arr, leftIndex, middleIndex, rightIndex);
        middleIndex = processRightHalf(arr, leftIndex, middleIndex);
        rightIndex++;
    }
}
 
/**
 * Processes the left half of the array to ensure it contains only even numbers.
 *
 * @param arr         The input array to be processed.
 * @param leftIndex   The current index in the left half of the array.
 * @param middleIndex The middle index of the array.
 * @param rightIndex  The current index in the right half of the array.
 * @return The updated left index.
 */
public static int processLeftHalf(int[] arr, int leftIndex, int middleIndex, int rightIndex) {
    if (arr[leftIndex] % 2 == 0) {
        return leftIndex + 1;
    } else {
        int evenIndex = findNextEven(arr, rightIndex);
        if (evenIndex != -1) {
            swap(arr, leftIndex, evenIndex);
            return leftIndex + 1;
        }
    }
    return leftIndex;
}
 
/**
 * Processes the right half of the array to ensure it contains only odd numbers.
 *
 * @param arr         The input array to be processed.
 * @param leftIndex   The current index in the left half of the array.
 * @param middleIndex The middle index of the array.
 * @return The updated middle index.
 */
public static int processRightHalf(int[] arr, int leftIndex, int middleIndex) {
    if (arr[middleIndex] % 2 == 1) {
        return middleIndex + 1;
    } else {
        int oddIndex = findNextOdd(arr, leftIndex);
        if (oddIndex != -1) {
            swap(arr, middleIndex, oddIndex);
            return middleIndex + 1;
        }
    }
    return middleIndex;
}
 
/**
 * Finds the index of the next even number in the array starting from the specified index.
 *
 * @param arr        The input array.
 * @param startIndex The starting index for the search.
 * @return The index of the next even number, or -1 if not found.
 */
public static int findNextEven(int[] arr, int startIndex) {
    for (int i = startIndex; i < arr.length; i++) {
        if (arr[i] % 2 == 0) {
            return i;
        }
    }
    return -1;
}
 
/**
 * Finds the index of the next odd number in the array starting from the specified index.
 *
 * @param arr        The input array.
 * @param startIndex The starting index for the search.
 * @return The index of the next odd number, or -1 if not found.
 */
public static int findNextOdd(int[] arr, int startIndex) {
    for (int i = startIndex; i < arr.length; i++) {
        if (arr[i] % 2 == 1) {
            return i;
        }
    }
    return -1;
}
 
/**
 * Swaps the elements at the specified indices in the array.
 *
 * @param arr The input array.
 * @param i   The first index.
 * @param j   The second index.
 */
public static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}