排序算法实现JAVA版本

测试用例

//测试用例
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));
}

1. 冒泡排序算法

	/** * 这里的排序默认从小到大 * 以正数作为排序内容 */
     
 	/** * 冒泡排序算法 * * @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;
            }
        }
    }

2. 插入排序

/** * 插入排序 * 由小到大 * * @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;
    }
}

3. 选择排序

  /** * 选择排序 */
    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;
    }

4. 希尔排序

/** * 希尔排序 * * @param A 排序内容 * @param N 排序内容个数 */
public static void shellSort(int[] A, int N) {
    
    int d;//开始的增量间隔

    for (d = N / 2; d > 0; d /= 2) {
    //希尔增量序列
        int tmp, j;
        for (int i = d; i < N; i++) {
    //插入排序 把d换成1 就是shell排序
            tmp = A[i];
            for (j = i; j >= d && A[j - d] > tmp; j -= d)
                A[j] = A[j - d];
            A[j] = tmp;
        }
    }
}

5. 堆排序

5.1 方案一：

 /** * 堆排序 方案一 使用最小堆 每次出来一个就放在临时数组里面 * * @param A 排序元素内容 * @param N 元素个数 */
    public static void heapSort(int[] A, int N) throws Exception {
    
        int tempA[] = new int[N];
        //构建最小堆
        MinHeap minHeap = buildMinHeap(A, N);
        for (int i = 0; i < N; i++) {
    
            tempA[i] = deleteMin(minHeap);
        }
        //将tmpA的元素复制给A
        for (int i = 0; i < N; i++) {
    
            A[i] = tempA[i];
        }
    }

5.2 方案二：

    /** * 堆排序 方案二 构建最大堆 每次将出来的元素放在末尾 ，末尾元素放在最大位置 * * @param A 排序元素内容 * @param N 元素个数 */
    public static void heapSort2(int[] A, int N) throws Exception {
        //构建最大堆
        for (int i = N / 2; i >= 0; i--) {
    
            percDownMax(A, N - 1, i, 0, 0, 0);
        }

        //将最大元素 放在末尾，每次放最大元素在末尾
        for (int i = N - 1; i > 0; i--) {
    
            swap(A, 0, i);
            percDownMax(A, i - 1, 0, 0, 0, 0);
        }
    }

6.堆排序

    /** * 最小堆取出一个最小元素 * * @param minHeap 最小堆 * @return */
    private static int deleteMin(MinHeap minHeap) throws Exception {
    
        if (minHeap.size < 0) {
    
            throw new Exception("没了呀");
        }
        int min = minHeap.elements[0], tmp = 0, parent = 0, child = 0;
        swap(minHeap.elements, 0, minHeap.size--);
        //调平最小堆 向下调平
        percDownMin(minHeap.elements, minHeap.size, parent, parent, child, tmp);
        return min;
    }

    private static MinHeap buildMinHeap(int[] a, int N) {
    
        for (int i = N / 2; i >= 0; i--) {
    
            percDownMin(a, N - 1, i, 0, 0, 0);
        }
        MinHeap minHeap = new MinHeap();
        minHeap.elements = a;
        minHeap.capacity = N;
        minHeap.size = N - 1;
        return minHeap;
    }

    /** * 向下遍历调平最小堆 * * @param a 数组最大堆 * @param n 大小 从0开始 * @param beginIndex 从哪个节点开始向下遍历 * @param parent 父节点临时变量 * @param child 子节点临时变量 * @param tmp 用来存储最开始那个节点代表的值 * @return 返回 */
    private static void percDownMin(int[] a, int n, int beginIndex, int parent, int child, int tmp) {
    
        tmp = a[beginIndex];
        for (parent = beginIndex; parent < n && (2 * parent + 1) <= n; parent = child) {
    
            child = 2 * parent + 1;//左子树下标 向左
            if ((child + 1) <= n && a[child] > a[child + 1])
                child++;//右子树下标 如果进了这个循环就是向右
            if (a[child] < tmp)
                a[parent] = a[child];
            else break;
        }
        a[parent] = tmp;
    }

    /** * 向下遍历调平最大堆 * * @param a 数组最小堆 * @param n 大小 从0开始 * @param beginIndex 从哪个节点开始向下遍历 * @param parent 父节点临时变量 * @param child 子节点临时变量 * @param tmp 用来存储最开始那个节点代表的值 * @return 返回 */
    private static void percDownMax(int[] a, int n, int beginIndex, int parent, int child, int tmp) {
    
        tmp = a[beginIndex];
        for (parent = beginIndex; parent < n && (2 * parent + 1) <= n; parent = child) {
    
            child = 2 * parent + 1;//左子树下标 向左
            if ((child + 1) <= n && a[child] < a[child + 1])
                child++;//右子树下标 如果进了这个循环就是向右
            if (a[child] > tmp)
                a[parent] = a[child];
            else break;
        }
        a[parent] = tmp;
    }

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


    static class MinHeap {
    
        private int[] elements;//存储元素
        private int size;//当前大小
        private int capacity;//最大容量
    }

7.归并排序

7.1.方式一：按照递归的方式

    /** * 有序子序列合并 * 从小大大排序 * * @param A 待排序序列 * @param tmpA 临时数组 * @param l 左边起始位置 * @param r 右边起始位置 * @param rightEnd 右边终止位置 */
    private void merge(int[] A, int[] tmpA, int l, int r, int rightEnd) {
    
        int leftEnd = r - 1; //左边终点位置 假设左右两边挨着
        int tmp = l; // 存放结果的数组终点位置
        int numElements = rightEnd - l - 1;//总的待排序数量
        while (l <= leftEnd && r <= rightEnd) {
    
            if (A[l] <= A[r]) tmpA[tmp++] = A[l++];
            else tmpA[tmp++] = A[r++];
        }
        //跳出循环
        while (l <= leftEnd) {
    //复制左边剩下的
            tmpA[tmp++] = A[l++];
        }
        while (r <= rightEnd) {
    //复制左边剩下的
            tmpA[tmp++] = A[r++];
        }
        //将剩下的元素复制给 A,但是是从左右边开始 遍历按照个数遍历
        for (int i = 0; i < numElements; i++, rightEnd--) {
    
            A[rightEnd] = tmpA[rightEnd];
        }
    }


    //分而治之 采用递归算法
    private void mSort(int[] A, int[] tmpA, int l, int rightEnd) {
    
        int center;
        if (l < rightEnd) {
    
            center = (rightEnd + l) / 2;
            mSort(A, tmpA, l, center);
            mSort(A, tmpA, center + 1, rightEnd);
            merge(A, tmpA, l, center + 1, rightEnd);
        }
    }

    //对外暴露的方法

    /** * 归并排序 从小到大排序 * * @param A 待排序数组 * @param n 需要排序元素个数 */
    public void mergeSort(int[] A, int n) {
    
        int[] tmpA = new int[n];
        mSort(A, tmpA, 0, n - 1);
    }

7.2.方式二 非递归使用循环的方式

    /** * 从小到大排序 * * @param A 待排序的数据 * @param tmpA 临时数组 * @param n 总的1个数 * @param length 按照多少个元素归并 */
    private void mergePass(int A[], int tmpA[], int n, int length) {
    
        int i = 0;
        for (; i < n - 2 * length; i += length) {
    
            merge1(A, tmpA, i, i + length, i + 2 * length - 1);
        }
        if (i + length < n) {
    
            merge1(A, tmpA, i, i + length, n - 1);
        } else
            for (int j = i; j < n; j++) tmpA[j] = A[j];

    }

    /** * 有序子序列合并 * 从小大大排序 * * @param A 待排序序列 * @param tmpA 临时数组 * @param l 左边起始位置 * @param r 右边起始位置 * @param rightEnd 右边终止位置 */
    private void merge1(int[] A, int[] tmpA, int l, int r, int rightEnd) {
    
        int leftEnd = r - 1; //左边终点位置 假设左右两边挨着
        int tmp = l; // 存放结果的数组终点位置
        int numElements = rightEnd - l - 1;//总的待排序数量
        while (l <= leftEnd && r <= rightEnd) {
    
            if (A[l] <= A[r]) tmpA[tmp++] = A[l++];
            else tmpA[tmp++] = A[r++];
        }
        //跳出循环
        while (l <= leftEnd) {
    //复制左边剩下的
            tmpA[tmp++] = A[l++];
        }
        while (r <= rightEnd) {
    //复制左边剩下的
            tmpA[tmp++] = A[r++];
        }
    }

    public void mergeSort1(int A[], int n) {
    
        int length = 1;
        int tmpA[] = new int[n];
        while (length < n) {
    
            mergePass(A, tmpA, n, length);
            length *= 2;
            mergePass(tmpA, A, n, length);
            length *= 2;
        }
    }