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

一、排序算法辅助工具类

1. 随机生成一个整形数组
2. 生成一个近乎有序的整形数组
3. 判断一个数组是否有序，有序返回true，无序返回false
4. 拷贝一个整形数组
5. 交换数组中的两个索引的位置
6. 打印数组

public class SortTestUtils {

    /**
     * 	随机生成一个整形数组
     * @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;
    }

    /**
     * 生成一个近乎有序的整形数组
     * @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;
    }

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

    /**
     * 拷贝一个整形数组
     * @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;
    }

    /**
     * 交换数组中的两个索引的位置
     * @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;
    }

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

二、三种基本排序算法

1. 冒泡排序
2. 选择排序
3. 插入排序

/**
 * 冒泡排序
 * @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);
                        }
                }
        }
}

/**
 * 选择排序
 * 		-选择一个最小的数，插入最左边
 * @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);
        }
}

/**
 * 插入排序
 * 		-随机选一个数，插入到合适的位置
 * @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;
        }
}
复制代码