排序

一、选择排序

1.堆排序

定义：堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序
可参考https://www.cnblogs.com/chengxiao/p/6129630
https://www.jianshu.com/p/938789fde325

public class HeapSort {
    public static void main(String[] args) {

        /**
         * 堆排序，利用二叉树左右节点的模式来比较
         */
        int[] a = {19, 8, 27, 6, 35, 14, 3, 12, 1, 0, 9, 10, 7};

        HeapSort heapSort = new HeapSort();
        heapSort.heapSort(a);
        for (int i = 0; i < a.length; i++) {
            System.out.println(a[i]);
        }

    }

    public void heapSort(int[] a) {
        if (a == null || a.length <= 1) {
            return;
        }

        buildMaxHeap(a);
        for (int i = a.length - 1; i > 0; i--) {
            //最大的在0位置，那么开始沉降，这样每交换一次最大的值就丢到最后了
            exchangeElement(a, 0, i);
            //继续获取0位置最大值
            maxHeap(a, i, 0);

        }

    }

    /**
     * 创建最大堆
     *
     * @param a
     */
    private void buildMaxHeap(int[] a) {
        if (a == null || a.length <= 1) {
            return;
        }
        int half = (a.length ) / 2-1;
        for (int i = half; i >= 0; i--) {
            maxHeap(a, a.length, i);
        }

    }

    /**
     * 利用二叉树跟、左、右节点的值进行比较，不断的更换最大值对应的小标largest，
     * 当当前传过来的下标与最大值的小标不想等时，两者交换相应的位置，然后再用递归的方式进行查找最大，
     * 但是此时是以前面所找的最大值的小标为标准
     * @param a
     * @param length
     * @param index
     */
    private void maxHeap(int[] a, int length, int index) {
        int left = index * 2 + 1;
        int right = index * 2 + 2;
        int largest = index;
        if (left < length  && a[left] > a[index]) {
            largest = left;
        }
        if (right < length  && a[right] > a[largest]) {
            largest = right;
        }
        if (index != largest) {
            exchangeElement(a, index, largest);

            maxHeap(a, length, largest);
        }
    }

    private void exchangeElement(int[] a, int index, int largest) {
        int temp = a[index];
        a[index] = a[largest];
        a[largest] = temp;
    }

}

2，

定义：首先，找到数组中最小的那个元素，其次，将它和数组的第一个元素交换位置（如果第一个元素就是最小元素那么它就和自己交换）。再次，在剩下的元素中找到最小的元素，将它与数组的第二个元素交换位置。如此往复，直到将整个数组排序。这种方法叫做选择排序，因为它在不断地选择剩余元素之中的最小者。

 public static void main(String[] args) {

       int[] a = {3, 7, 1, 5, 6, 2, 4};
        for (int i = 0; i < a.length; i++) {
            for (int j = i + 1; j < a.length; j++) {
                int temp;
                if (a[i] > a[j]) {
                    temp = a[i];
                    a[i] = a[j];
                    a[j] = temp;
                }
            }
            System.out.println(a[i]);
        }



    }

二、插入排序（适合小规模数组）

1.直接插入排序

定义：每次将一个待排序的元素与已排序的元素进行逐一比较，直到找到合适的位置按大小插入。
自己的理解：
在一个无序的数组中，首先将前两个元素进行对比排序，然后第三个元素和第二个元素进行对比，如果第三个元素大于第二个元素，则进行下一步，将第四个元素和第三个元素对比排序；否则如果第三个元素小于第二个元素，将两者位置互换后，再将重新排序后的第二个元素和第一个元素进行对比排序.....以此类推即可实现插入排序

public class InsertSort {
    public static void main(String[] args) {

        /**
         * 直接插入排序
         */
        int[] a = {9, 3, 8, 23, 86, 33, 54, 0, 1, 65, 10, -1};
        //从数组中下标为1的元素开始
        for (int i = 1; i < a.length; i++) {
            //用temp记录当前遍历的元素值
            int temp = a[i];
            //外部定义j，为了在break的情况下记录j的值
            int j;
            for (j = i - 1; j >= 0; j--) {
                //如果a[j]大于当前的值，则最后一个元素需要往后移动一位，所以将a[j]的值赋值给a[j+1]，
                //否则，就结束循环，记录j的值
                if (a[j] > temp) {
                    a[j + 1] = a[j];
                } else {
                    break;
                }
            }
            //break下的小标为j，值比temp小，所以temp的值需要赋值给a[j+1]
            a[j + 1] = temp;
        }

        for (int i = 0; i < a.length; i++) {
            System.out.println(a[i]);
        }

    }
}

2.二分法插入排序

先要知道数组中的左边、右边以及中间的下标，然后当坐标下标小于等于右边下标时，将要插入的数字与中间下标对应的数字进行比较，做变换左、中、右下标的循环，最后以左下标为标准，将左及左后边全部后移，当左下标的值不等于i时，左位置插入该数据。

public class BinaryInsertSort {
    public static void main(String[] args) {
        int[] a = {3, 0, 1, 90, 56, 34, 23, 76, 46, -1, 77};
        BinaryInsertSort b = new BinaryInsertSort();
        b.sort(a);
        for (int i = 0; i < a.length; i++) {
            System.out.println(a[i]);
        }

    }

    /**
     * 二分法插入排序
     *
     * @param a
     */
    public void sort(int[] a) {
        for (int i = 1; i < a.length; i++) {
            //记录当前遍历到的数值
            int temp = a[i];
            //定义左边的下标
            int left = 0;
            //定义右边的下标
            int right = i - 1;
            //初始化中间的下标
            int mid = 0;
            //循环：当左边下标小于等于右边下标时
            while (left <= right) {
                //计算中间下标
                mid = (left + right) / 2;
                //当当前遍历的值�大于中间小标对应的值时，变动左边下标
                if (temp > a[mid]) {
                    left = mid + 1;
                } else {
                    //当当前遍历的值小于中间小标对应的值时，变动右边下标
                    right = mid - 1;
                }
            }

            //遍历数组，以左下标为标准，让大于等于左边下标对应的所有的值都往后移动一位
            for (int j = i - 1; j >= left; j--) {
                if (temp < a[j]) {
                    a[j + 1] = a[j];
                }

            }

            //当左边下标不等于遍历的小标时（即要插入的那个数在当前排序数字中不是最大时），给左边下标对应的数赋值
            //要插入的那个数在当前排序数字中是最大时，直接插入，不做任何操作
            if (left != i) {
                a[left] = temp;
            }
        }


    }
}

3.希尔排序

定义：希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止

希尔排序过程

public class HeerSort {
    public static void main(String[] args) {
        /**
         * 希尔排序
         */
        int[] a = {49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 1, 33, 85, 29};
        int d = a.length / 2;   //默认增量，总长度除以2
        while (true) {
            for (int i = 0; i < d; i++) {//注意i的值是小于增量的
                for (int j = i; j + d < a.length; j += d) {//以增加作为间距
                    int temp;
                    if (a[j] > a[j + d]) {
                        temp = a[j];
                        a[j] = a[j + d];
                        a[j + d] = temp;
                    }
                }
            }
            //增量为1时结束
            if (d == 1) {
                break;
            }
            d--;
        }

        for (int i = 0; i < a.length; i++) {
            System.out.println(a[i]);
        }

    }
}

三、快速排序

定义：是对冒泡排序的一种改进。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列

public class QuickSort {
    public static void main(String[] args) {
        QuickSort quickSort = new QuickSort();
        int[] a = {19, 2, 6, 90, 67, 33, -7, 24, 3, 56, 34, 5};
        quickSort.quick(a);
        for (int i = 0; i < a.length; i++) {
            System.out.println(a[i]);
        }

    }

    public void quick(int[] a) {
        if (a.length < 0) {
            return;
        }
        quickSort(a, 0, a.length - 1);

    }

    /**
     * 快速排序
     *
     * @param a
     * @param low
     * @param high
     */
    private void quickSort(int[] a, int low, int high) {
        //获取下标后，以该下标为基准，用迭代的方法左右两边都做相同的操作
         if (low < high) {
            int middle = getMiddle(a, low, high);
            quickSort(a, 0, middle - 1);
            quickSort(a, middle + 1, high);
        }
    }

    /**
     * 以数组中的一个数为基准元素，然后获取该元素在此数组中的排序的下标
     * @param a
     * @param low
     * @param high
     * @return
     */
    private int getMiddle(int[] a, int low, int high) {
        int temp = a[low];//以下标为low的值作为基准元素
        while (low < high) {
            //从右边开始，一个个与基准元素进行比较，大于基准元素的，high--，小于基准元素的，结束循环
            while (low < high && temp < a[high]) {
                high--;
            }
            //结束循环之后，将a[high]的值放到a[low]中，
            a[low] = a[high];

            //在从左边开始，一个个与基准元素进行比较，小于基准元素的，low++；大于基准元素的，结束循环
            while (low < high && temp > a[low]) {
                low++;
            }
            //结束循环之后，将a[low]的值放到a[high]中，
            a[high] = a[low];
        }
        a[low] = temp;
        return low;
    }
}

四、归并排序

定义：是一类与插入排序、交换排序、选择排序不同的另一种排序方法。归并的含义是将两个或两个以上的有序表合并成一个新的有序表；
基本思想：分而治之(divide - conquer);每个递归过程涉及三个步骤
第一, 分解: 把待排序的 n 个元素的序列分解成两个子序列, 每个子序列包括 n/2 个元素.
第二, 治理: 对每个子序列分别调用归并排序MergeSort, 进行递归操作
第三, 合并: 合并两个排好序的子序列,生成排序结果.

image

public class MergeSort {
    public static void main(String[] args) {
        int[] a = new int[]{90, 3, 2, 67, 44, -9, 87, 65, 11, 9, 2, 8};
        MergeSort m = new MergeSort();
        m.mergeSort(a, 0, a.length - 1);
        for (int i = 0; i < a.length; i++) {
            System.out.println(a[i]);
        }

    }

    /**
     * 归并排序
     * @param a
     * @param left
     * @param right
     */
    public void mergeSort(int[] a, int left, int right) {
        if (left < right) {
            int middle = (left + right) / 2;
            //将数组拆分成单个元素的多个数组
            mergeSort(a, left, middle);
            mergeSort(a, middle + 1, right);
            //逐一合并
            merge(a, left, middle, right);
        }

    }

    /**
     * 合并排好序的数组，定义一个新的数组，然后两个数组从第一个开始进行比较，
     * 谁小就放入新的数组，同时对应的下标加或者减1，
     * @param a
     * @param left
     * @param middle
     * @param right
     */
    private void merge(int[] a, int left, int middle, int right) {
        int[] tempArray = new int[a.length];
        int rightStart = middle + 1;
        int temp = left;
        int third = left;
        //当左边小于等于中间；右边开始下标小于等于右边
        while (left <= middle && rightStart <= right) {
            //从第一个元素开始逐个比较，如果左边的值小于右边的值，将左边的值放在新的数组中，否则，将右边的值放在新的数组中
            if (a[left] <= a[rightStart]) {
                tempArray[third++] = a[left++];
//                tempArray[third]=a[left];
//                third++;
//                left++;
            } else {
                tempArray[third++] = a[rightStart++];
            }
        }

        //当右边的数组全部比较完了，但是左边的依然还有，则将左边剩余的元素依次放入新的数组中
        while (left <= middle) {
            tempArray[third++] = a[left++];
        }
        //当左边的数组全部比较完了，但是右边的依然还有，则将右边剩余的元素依次放入新的数组中
        while (rightStart <= right) {
            tempArray[third++] = a[rightStart++];
        }

        while (temp <= right) {
            a[temp] = tempArray[temp];
            temp++;
        }


    }
}

五、基数排序

基本思路：

• 第一：获取数组中的最大值以及最大值的位数；
• 第二：创建一个多维数组，里面有十个数组，分别存放位数对应的1-10的数字；
• 第三：遍历原始数组，分别获取个位、十位、百位等位对应的值，通过这个值获取在多维数组中对应的数组，
• 把原始数组中的这个元素添加到多维数组中对应的数组中，
• 第四：开始收集；遍历多维数组中的每个数组，把每个数组中的元素一个个赋值给原始数组元素，赋值一个，移除一个，同时count次数++

public class BasicSort {
    public static void main(String[] args) {
        int[] a = {136, 2, 6, 8, 9, 2, 8, 11, 23, 56, 34, 90, 89, 29, 145, 209, 320, 78, 3};
        BasicSort basicSort = new BasicSort();
        basicSort.sort(a);
        for (int i = 0; i < a.length; i++) {
            System.out.println(a[i]);
        }

    }

    /**
     * 基数排序：
     * 基本思路：
     * 第一：获取数组中的最大值以及最大值的位数；
     * 第二：创建一个多维数组，里面有十个数组，分别存放位数对应的1-10的数字；
     * 第三：遍历原始数组，分别获取个位、十位、百位等位对应的值，通过这个值获取在多维数组中对应的数组，
     * 把原始数组中的这个元素添加到多维数组中对应的数组中，
     * 第四：开始收集；遍历多维数组中的每个数组，把每个数组中的元素一个个赋值给原始数组元素，赋值一个，移除一个，
     * 同时count次数++
     *
     * @param a
     */
    public void sort(int[] a) {
        //获取数组中的最大值
        int max = 0;
        for (int i = 0; i < a.length; i++) {
            if (max < a[i]) {
                max = a[i];
            }
        }

        //获取最大值的位数
        int times = 0;
        while (max > 0) {
            max = max / 10;
            times++;
        }

        //创建一个多维数组
        List<ArrayList> queue = new ArrayList<>();
        for (int i = 0; i < 10; i++) {
            ArrayList q = new ArrayList();
            queue.add(q);
        }

        for (int i = 0; i < times; i++) {
            for (int j = 0; j < a.length; j++) {
                //获取对应的位的值（i为0是各位，1是10位，2是百位）
                int x = a[j] % (int) Math.pow(10, i + 1) / (int) Math.pow(10, i);
                //通过得到的位的值获取多维数组中对应的数组，然后将该数据添加到对应的数组中
                ArrayList q = queue.get(x);
                q.add(a[j]);
            }

            //开始收集
            int count = 0;
            //遍历多维数组中的每个数组
            for (int j = 0; j < 10; j++) {
                while (queue.get(j).size() > 0) {
                    ArrayList<Integer> q = queue.get(j);//获取多维数组中的单个数组
                    //将第一个值赋值给原有的数组，然后移除第一个
                    a[count] = q.get(0);
                    q.remove(0);
                    count++;

                }
            }
        }

    }
}

六、二分查找

public class BinarySearch {
    public static void main(String[] args) {
        int[] array = {10, 23, 4, 3, 2, 5, 1, 2, 623, 92, 23, 23, 234, 2, 34, 234, 234, 2, 10};
        BinarySearch binarySearch = new BinarySearch();
        BasicSort basicSort = new BasicSort();
        basicSort.sort(array);
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + "---");
        }
//        binarySearch.binarySearch(5, array, 0, array.length - 1);
        binarySearch.directBinarySearch(array,5);


    }

    /**
     * 递归查找（二分查找）
     *
     * @param elem
     * @param array
     * @param low
     * @param high
     * @return
     */
    public int binarySearch(int elem, int[] array, int low, int high) {
        if (low > high) {
            return -1;
        }
        int middle = (low + high) / 2;
        if (elem < array[middle]) {
            //找左边
            return binarySearch(elem, array, low, middle - 1);
        } else if (elem > array[middle]) {
            //找右边
            return binarySearch(elem, array, middle + 1, high);
        } else if (elem == array[middle]) {
            System.out.print("-------" + middle);
            return middle;
        } else {
            return -1;
        }

    }

    /**
     * 非递归查找
     * @param array
     * @param elem
     * @return
     */
    public int directBinarySearch(int[] array, int elem) {
        int low = 0;
        int high = array.length - 1;
        while (low <= high) {
            int middle = (low + high) / 2;
            if (elem < array[middle]) {
                high = middle - 1;
            } else if (elem > array[middle]) {
                low = middle + 1;
            } else if (elem == array[middle]) {
                System.out.print("-------" + middle);
                return middle;
            }
        }
        return -1;
    }
}