package com.itheima;

import java.util.Arrays;

/**
* 1、 排序有哪几种方法？请列举。并用JAVA实现一个快速排序.
*
* @author snow
*
*/
public class Test1 {
        public static void main(String[] args) {
                int arr[] = new int[] { 10, 8, 20, 11, 19 };
                // int[] a = {2, 34, 2};// 一个数组的定义和实例化
                // System.out.println(Arrays.toString(sort2(arr)));
                System.out.println(Arrays.toString(sort4(arr, 0, arr.length - 1)));
                System.out.println(Arrays.toString(sort6(arr, arr)));
        }

        // 冒泡排序法
        public static int[] sort1(int[] arr) {
                for (int i = 0; i < arr.length; i++) {
                        int temp = 0;
                        for (int j = 0; j < arr.length - i - 1; j++) {
                                if (arr[j] > arr[j + 1]) {
                                        temp = arr[j];
                                        arr[j] = arr[j + 1];
                                        arr[j + 1] = temp;
                                }
                        }
                }
                return arr;
        }

        // 插入排序法
        public static int[] sort2(int[] arr, int left, int right) {
                for (int i = left, j = i; i < right; j = ++i) {
                        int arri = arr[i + 1];
                        while (arri < arr[j]) {
                                arr[j + 1] = arr[j];
                                if (j-- == left) {
                                        break;
                                }
                        }
                        arr[j + 1] = arri;
                }
                return arr;
        }

        // 选择排序法
        public static int[] sort3(int[] arr) {
                for (int i = 0; i < arr.length - 1; i++) {
                        int j = i;
                        int temp = 0;
                        for (int k = i + 1; k < arr.length; k++) {
                                if (arr[k] < arr[j]) {
                                        j = k;
                                }
                        }
                        if (j != i) {
                                temp = arr[j];
                                arr[j] = arr[i];
                                arr[i] = temp;
                        }
                }
                return arr;
        }

        // 快速排序法
        /**
         * 快速排序思想： 1，首先找到中间的数，i初始为0递增，直到大于或等于中间的数。j初始为length-1递减，直到小于或者等于中间的数。
         * 2，交换i，j所指向的数。
         * 3，递归调用该方法。
         * @param arr
         * @param left
         * @param right
         * @return
         */
        public static int[] sort4(int[] arr, int left, int right) {
                int i = left, j = right;
                int middle, temp;

                middle = arr[(left + right) / 2];
                do {
                        while ((arr[i] < middle) && (i < right)) {
                                i++;
                        }
                        while ((arr[j] > middle) && (j > left)) {
                                j--;
                        }
                        if (i <= j) {
                                temp = arr[i];
                                arr[i] = arr[j];
                                arr[j] = temp;
                                i++;
                                j--;
                        }
                } while (i <= j);
                if (left < j) {
                        sort4(arr, left, j);
                }

                if (right > i)
                        sort4(arr, i, right);
                return arr;
        }

        public static int[] sort5(int[] arr, int step) {
                int min;
                int temp;

                int sequence = 1;
                while (sequence < arr.length / step) {
                        sequence = sequence * step + 1; // 产生到以step为步长到arr.length的最大值.
                }

                while (sequence > 0) {

                        for (int i = sequence; i < arr.length; i++) {
                                temp = arr[i];
                                min = i;

                                while (min > sequence - 1 && arr[min - sequence] > temp) {
                                        arr[min] = arr[min - sequence];
                                        min = min - sequence;
                                }

                                arr[min] = temp;
                        }

                        sequence = (sequence - 1) / step; // 递减序列关键字
                }
                return arr;
        }


        /**
         * 归并操作的工作原理如下：
         * 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
         * 设定两个指针，最初位置分别为两个已经排序序列的起始位置
         * 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
         * 　重复步骤3直到某一指针达到序列尾
         * 将另一序列剩下的所有元素直接复制到合并序列尾
         * @param data1
         * @param data2
         * @return
         */
        public static int[] sort6(int[] data1, int[] data2) {
                int[] temp = new int[data1.length + data2.length];
                int i = 0, j = 0, iter = 0;
                for (; i < data1.length && j < data2.length;) {
                        if (data1[i] <= data2[j]) {
                                temp[iter] = data1[i];
                                iter++;
                                i++;
                        } else {
                                temp[iter] = data2[j];
                                iter++;
                                j++;
                        }
                }
                for (; i < data1.length; i++, iter++) {
                        temp[iter] = data1[i];
                }
                for (; j < data2.length; j++, iter++) {
                        temp[iter] = data2[j];
                }
                return temp;
        }

}

package com.itheima;

import java.util.Arrays;

/**
* 1、 排序有哪几种方法？请列举。并用JAVA实现一个快速排序.
*
* @author snow
*
*/
public class Test1 {
        public static void main(String[] args) {
                int arr[] = new int[] { 10, 8, 20, 11, 19 };
                // int[] a = {2, 34, 2};// 一个数组的定义和实例化
                // System.out.println(Arrays.toString(sort2(arr)));
                System.out.println(Arrays.toString(sort4(arr, 0, arr.length - 1)));
                System.out.println(Arrays.toString(sort6(arr, arr)));
        }

        // 冒泡排序法
        public static int[] sort1(int[] arr) {
                for (int i = 0; i < arr.length; i++) {
                        int temp = 0;
                        for (int j = 0; j < arr.length - i - 1; j++) {
                                if (arr[j] > arr[j + 1]) {
                                        temp = arr[j];
                                        arr[j] = arr[j + 1];
                                        arr[j + 1] = temp;
                                }
                        }
                }
                return arr;
        }

        // 插入排序法
        public static int[] sort2(int[] arr, int left, int right) {
                for (int i = left, j = i; i < right; j = ++i) {
                        int arri = arr[i + 1];
                        while (arri < arr[j]) {
                                arr[j + 1] = arr[j];
                                if (j-- == left) {
                                        break;
                                }
                        }
                        arr[j + 1] = arri;
                }
                return arr;
        }

        // 选择排序法
        public static int[] sort3(int[] arr) {
                for (int i = 0; i < arr.length - 1; i++) {
                        int j = i;
                        int temp = 0;
                        for (int k = i + 1; k < arr.length; k++) {
                                if (arr[k] < arr[j]) {
                                        j = k;
                                }
                        }
                        if (j != i) {
                                temp = arr[j];
                                arr[j] = arr[i];
                                arr[i] = temp;
                        }
                }
                return arr;
        }

        // 快速排序法
        /**
         * 快速排序思想： 1，首先找到中间的数，i初始为0递增，直到大于或等于中间的数。j初始为length-1递减，直到小于或者等于中间的数。
         * 2，交换i，j所指向的数。
         * 3，递归调用该方法。
         * @param arr
         * @param left
         * @param right
         * @return
         */
        public static int[] sort4(int[] arr, int left, int right) {
                int i = left, j = right;
                int middle, temp;

                middle = arr[(left + right) / 2];
                do {
                        while ((arr[i] < middle) && (i < right)) {
                                i++;
                        }
                        while ((arr[j] > middle) && (j > left)) {
                                j--;
                        }
                        if (i <= j) {
                                temp = arr[i];
                                arr[i] = arr[j];
                                arr[j] = temp;
                                i++;
                                j--;
                        }
                } while (i <= j);
                if (left < j) {
                        sort4(arr, left, j);
                }

                if (right > i)
                        sort4(arr, i, right);
                return arr;
        }

        public static int[] sort5(int[] arr, int step) {
                int min;
                int temp;

                int sequence = 1;
                while (sequence < arr.length / step) {
                        sequence = sequence * step + 1; // 产生到以step为步长到arr.length的最大值.
                }

                while (sequence > 0) {

                        for (int i = sequence; i < arr.length; i++) {
                                temp = arr[i];
                                min = i;

                                while (min > sequence - 1 && arr[min - sequence] > temp) {
                                        arr[min] = arr[min - sequence];
                                        min = min - sequence;
                                }

                                arr[min] = temp;
                        }

                        sequence = (sequence - 1) / step; // 递减序列关键字
                }
                return arr;
        }


        /**
         * 归并操作的工作原理如下：
         * 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
         * 设定两个指针，最初位置分别为两个已经排序序列的起始位置
         * 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
         * 　重复步骤3直到某一指针达到序列尾
         * 将另一序列剩下的所有元素直接复制到合并序列尾
         * @param data1
         * @param data2
         * @return
         */
        public static int[] sort6(int[] data1, int[] data2) {
                int[] temp = new int[data1.length + data2.length];
                int i = 0, j = 0, iter = 0;
                for (; i < data1.length && j < data2.length;) {
                        if (data1[i] <= data2[j]) {
                                temp[iter] = data1[i];
                                iter++;
                                i++;
                        } else {
                                temp[iter] = data2[j];
                                iter++;
                                j++;
                        }
                }
                for (; i < data1.length; i++, iter++) {
                        temp[iter] = data1[i];
                }
                for (; j < data2.length; j++, iter++) {
                        temp[iter] = data2[j];
                }
                return temp;
        }

}