[数据结构与算法]排序算法实现JAVA版本

冒泡排序算法

	/**
     * 这里的排序默认从小到大
     * 以正数作为排序内容
     */
     
 	/**
     * 冒泡排序算法
     *
     * @param A 排序内容
     * @param N 大小
     */
    public static void BubbleSort(int[] A, int N) {
        int temp = 0;
        boolean flag;
        //这里 j=n-1 可以避免 A[i + 1] 超过范围
        for (int j = N - 1; j > 0; j--) {
            flag = true;
            //一趟排序
            for (int i = 0; i < j; i++) {
                //前面的大于后面的 需要交换顺序
                if (A[i] > A[i + 1]) {
                    temp = A[i];
                    A[i] = A[i + 1];
                    A[i + 1] = temp;
                    flag = false;
                }
            }
            //某一趟排序 flag 没有变化 ，表示这一趟排序下来，已经为排好序了
            if (flag) {
                break;
            }
        }
    }

插入排序

/**
 * 插入排序
 * 由小到大
 *
 * @param A 传入待排序内容
 * @param N 待排序的元素个数
 */
public static void InsertSort(int[] A, int N) {
    int tmp, j;
    //认为第一个已经有序
    for (int i = 1; i < N; i++) {
        //一趟排序，从已有序的序列 从最后一个位置往前，
        //如果有序序列最后一个（A[j]）大于现在这个A[i]就 把A[j] 往后挪一个位置。
        //下一次重复上述操作
        tmp = A[i];
        // j = i-1 表示有序序列的最大个数未i-1一个，
        //最开始的时候 就是0 即认为第一个元素自己是有序的
        for (j = i; j > 0 && A[j - 1] > tmp; j--) {
            //将元素依次往后挪一个位置
            A[j] = A[j - 1];
        }
        A[j] = tmp;
    }
}

选择排序

  /**
     * 选择排序
     */
    public static void selectionSort(int[] A, int N) {
        int minPosition;
        //每一次选择里面一个最小的
        for (int i = 0; i < N; i++) {
            //从A 中的下标为i开始到N-1 寻找其中最小的元素 将位置赋给 minPosition
            minPosition = scanForMin(A, i, N - 1);
            //将i 和 minPosition 所指的元素互换位置，其中A[i] 表示有序序列 A[i~N-1] 为无序序列
            swap(A, minPosition, i);
        }
    }

    private static void swap(int[] a, int minPosition, int i) {
        int tmp = a[i];
        a[i] = a[minPosition];
        a[minPosition] = tmp;
    }

    private static int scanForMin(int[] a, int i, int N) {
        int minPosition = i;
        for (int j = i + 1; j <= N; j++) {
            if (a[j] < a[minPosition]) {
                minPosition = j;
            }
        }
        return minPosition;
    }
    //测试用例
    public static void main(String[] args) {
        int[] ints = {13, 432, 4553, 322, 442, 5, 5, 0, 32,};

        selectionSort(ints, ints.length);

        System.out.println(Arrays.toString(ints));
    }

预计今天2021-12-23 更新
插入 选择 希尔排序