数据结构与算法-排序算法辅助工具编写与三种基本排序算法（Java实现）

初学者刚刚接触算法的时候，可以通过编写一些辅助的工具来辅助算法的学习。

一、排序算法辅助工具类

1. 随机生成一个整形数组

/**
 *     随机生成一个整形数组
 * @param size        数组大小
 * @param rangeL    数组左边范围（包含）
 * @param rangeR    数组右边范围（包含）
 * @return
 */
public static int[] generateRandomArray(int size,int rangeL,int rangeR) {
    int[] arr = new int[size];
    for(int i = 0;i < size;i++) {
        arr[i] = (int) (Math.random() * (rangeR-rangeL+1)) + rangeL;
    }
    return arr;
}

2. 生成一个近乎有序的整形数组

/**
 * 生成一个近乎有序的整形数组
 * @param size        数组大小
 * @param swapTimes    将有序数组打乱次数
 * @return
 */
public static int[] generateAlmostOrderlyArray(int size,int swapTimes) {
    int[] arr = new int[size];
    for(int i = 0;i<size;i++) {
        arr[i] = i;
    }
    for(int i = 0;i < swapTimes;i++) {
        int index1 = (int) Math.random()*size;
        int index2 = (int) Math.random()*size;
        swap(arr,index1,index2);
    }
    return arr;
}

3. 判断一个数组是否正反皆有序

/**
 * 判断一个数组是否有序，有序返回true，无序返回false
 * @param arr    整形数组
 * @return
 */
public static boolean isOrderly(int[] arr) {
    if(isOrderAsc(arr) || isOrderDesc(arr)) {
        return true;
    }
    return false;
}

/**
 * 判断一个数组是否顺序有序，有序返回true，无序返回false
 * @param arr
 * @return
 */
private static boolean isOrderAsc(int[] arr) {
    for(int i=0;i < arr.length-1;i++) {
        if(arr[i] > arr[i+1]) {
            return false;
        }
    }
    return true;
}

/**
 * 判断一个数组是否倒序有序，有序返回true，无序返回false
 * @param arr
 * @return
 */
private static boolean isOrderDesc(int[] arr) {
    for(int i = arr.length-1; i > 0; i--) {
        if(arr[i] > arr[i-1]) {
            return false;
        }
    }
    return true;
}

4. 拷贝一个整形数组

/**
 * 拷贝一个整形数组
 * @param arr    整形数组
 * @return
 */
public static int[] copyIntArray(int[] arr) {
    int[] copyArr = new int[arr.length];
    for(int i = 0;i < arr.length; i++) {
        copyArr[i] = arr[i];
    }
    return copyArr;
}

5. 交换数组中的两个索引的位置

/**
 * 交换数组中的两个索引的位置
 * @param arr    整形数组
 * @param i        第一个索引
 * @param j        第二个索引
 */
public static void swap(int[] arr, int i, int j){
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

6. 打印数组

/**
 *     打印数组
 * @param arr    整形数组
 */
public static void printArray(int[] arr) {
    for (int i : arr) {
        System.out.print(i+"\t");
    }
    System.out.println();
}

二、三种基本排序算法

1. 冒泡排序

/**
 * 冒泡排序
 * @param arr    整形数组
 */
public static void bubbleSort(int[] arr) {
    for(int i = 0;i < arr.length-1;i++) {
        for(int j = 0;j < arr.length-1;j++) {
            if(arr[j+1] < arr[j]) {
                SortTestUtils.swap(arr, j+1, j);
            }
        }
    }
}

2. 选择排序

/**
 * 选择排序
 *         -选择一个最小的数，插入最左边
 * @param arr    整形数组
 */
public static void selectSort(int[] arr) {
    for(int i = 0;i < arr.length-1;i++) {
        int min = i;
        for(int j = i+1;j < arr.length;j++) {
            if(arr[j] < arr[min]) {
                min = j;
            }
        }
        SortTestUtils.swap(arr, i, min);
    }
}

3. 插入排序

/**
 * 插入排序
 *         -随机选一个数，插入到合适的位置
 * @param arr    整形数组
 */
public static void insertSort(int[] arr) {
    for(int i = 1; i < arr.length; i++) {
        int insertValue = arr[i];
        int j = 0;
        for(j = i;j > 0 && arr[j-1] > insertValue; j--) {
            arr[j] = arr[j-1]; 
        }
        arr[j] = insertValue;
    }
}