一、選擇排序

1.堆排序

定義：堆排序是利用堆這種數(shù)據(jù)結構而設計的一種排序算法，堆排序是一種選擇排序
可參考https://www.cnblogs.com/chengxiao/p/6129630
http://www.itdecent.cn/p/938789fde325

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

        /**
         * 堆排序，利用二叉樹左右節(jié)點的模式來比較
         */
        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);
            //繼續(xù)獲取0位置最大值
            maxHeap(a, i, 0);

        }

    }

    /**
     * 創(chuàng)建最大堆
     *
     * @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);
        }

    }

    /**
     * 利用二叉樹跟、左、右節(jié)點的值進行比較，不斷的更換最大值對應的小標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，

定義：首先，找到數(shù)組中最小的那個元素，其次，將它和數(shù)組的第一個元素交換位置（如果第一個元素就是最小元素那么它就和自己交換）。再次，在剩下的元素中找到最小的元素，將它與數(shù)組的第二個元素交換位置。如此往復，直到將整個數(shù)組排序。這種方法叫做選擇排序，因為它在不斷地選擇剩余元素之中的最小者。

 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]);
        }



    }

二、插入排序（適合小規(guī)模數(shù)組）

1.直接插入排序

定義：每次將一個待排序的元素與已排序的元素進行逐一比較，直到找到合適的位置按大小插入。
自己的理解：
在一個無序的數(shù)組中，首先將前兩個元素進行對比排序，然后第三個元素和第二個元素進行對比，如果第三個元素大于第二個元素，則進行下一步，將第四個元素和第三個元素對比排序；否則如果第三個元素小于第二個元素，將兩者位置互換后，再將重新排序后的第二個元素和第一個元素進行對比排序.....以此類推即可實現(xiàn)插入排序

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

        /**
         * 直接插入排序
         */
        int[] a = {9, 3, 8, 23, 86, 33, 54, 0, 1, 65, 10, -1};
        //從數(shù)組中下標為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]，
                //否則，就結束循環(huán)，記錄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.二分法插入排序

先要知道數(shù)組中的左邊、右邊以及中間的下標，然后當坐標下標小于等于右邊下標時，將要插入的數(shù)字與中間下標對應的數(shù)字進行比較，做變換左、中、右下標的循環(huán)，最后以左下標為標準，將左及左后邊全部后移，當左下標的值不等于i時，左位置插入該數(shù)據(jù)。

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++) {
            //記錄當前遍歷到的數(shù)值
            int temp = a[i];
            //定義左邊的下標
            int left = 0;
            //定義右邊的下標
            int right = i - 1;
            //初始化中間的下標
            int mid = 0;
            //循環(huán)：當左邊下標小于等于右邊下標時
            while (left <= right) {
                //計算中間下標
                mid = (left + right) / 2;
                //當當前遍歷的值?大于中間小標對應的值時，變動左邊下標
                if (temp > a[mid]) {
                    left = mid + 1;
                } else {
                    //當當前遍歷的值小于中間小標對應的值時，變動右邊下標
                    right = mid - 1;
                }
            }

            //遍歷數(shù)組，以左下標為標準，讓大于等于左邊下標對應的所有的值都往后移動一位
            for (int j = i - 1; j >= left; j--) {
                if (temp < a[j]) {
                    a[j + 1] = a[j];
                }

            }

            //當左邊下標不等于遍歷的小標時（即要插入的那個數(shù)在當前排序數(shù)字中不是最大時），給左邊下標對應的數(shù)賦值
            //要插入的那個數(shù)在當前排序數(shù)字中是最大時，直接插入，不做任何操作
            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]);
        }

    }
}

三、快速排序

定義：是對冒泡排序的一種改進。它的基本思想是：通過一趟排序將要排序的數(shù)據(jù)分割成獨立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分數(shù)據(jù)分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數(shù)據(jù)變成有序序列

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);
        }
    }

    /**
     * 以數(shù)組中的一個數(shù)為基準元素，然后獲取該元素在此數(shù)組中的排序的下標
     * @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--，小于基準元素的，結束循環(huán)
            while (low < high && temp < a[high]) {
                high--;
            }
            //結束循環(huán)之后，將a[high]的值放到a[low]中，
            a[low] = a[high];

            //在從左邊開始，一個個與基準元素進行比較，小于基準元素的，low++；大于基準元素的，結束循環(huán)
            while (low < high && temp > a[low]) {
                low++;
            }
            //結束循環(huán)之后，將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;
            //將數(shù)組拆分成單個元素的多個數(shù)組
            mergeSort(a, left, middle);
            mergeSort(a, middle + 1, right);
            //逐一合并
            merge(a, left, middle, right);
        }

    }

    /**
     * 合并排好序的數(shù)組，定義一個新的數(shù)組，然后兩個數(shù)組從第一個開始進行比較，
     * 誰小就放入新的數(shù)組，同時對應的下標加或者減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) {
            //從第一個元素開始逐個比較，如果左邊的值小于右邊的值，將左邊的值放在新的數(shù)組中，否則，將右邊的值放在新的數(shù)組中
            if (a[left] <= a[rightStart]) {
                tempArray[third++] = a[left++];
//                tempArray[third]=a[left];
//                third++;
//                left++;
            } else {
                tempArray[third++] = a[rightStart++];
            }
        }

        //當右邊的數(shù)組全部比較完了，但是左邊的依然還有，則將左邊剩余的元素依次放入新的數(shù)組中
        while (left <= middle) {
            tempArray[third++] = a[left++];
        }
        //當左邊的數(shù)組全部比較完了，但是右邊的依然還有，則將右邊剩余的元素依次放入新的數(shù)組中
        while (rightStart <= right) {
            tempArray[third++] = a[rightStart++];
        }

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


    }
}

五、基數(shù)排序

基本思路：

• 第一：獲取數(shù)組中的最大值以及最大值的位數(shù)；
• 第二：創(chuàng)建一個多維數(shù)組，里面有十個數(shù)組，分別存放位數(shù)對應的1-10的數(shù)字；
• 第三：遍歷原始數(shù)組，分別獲取個位、十位、百位等位對應的值，通過這個值獲取在多維數(shù)組中對應的數(shù)組，
• 把原始數(shù)組中的這個元素添加到多維數(shù)組中對應的數(shù)組中，
• 第四：開始收集；遍歷多維數(shù)組中的每個數(shù)組，把每個數(shù)組中的元素一個個賦值給原始數(shù)組元素，賦值一個，移除一個，同時count次數(shù)++

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]);
        }

    }

    /**
     * 基數(shù)排序：
     * 基本思路：
     * 第一：獲取數(shù)組中的最大值以及最大值的位數(shù)；
     * 第二：創(chuàng)建一個多維數(shù)組，里面有十個數(shù)組，分別存放位數(shù)對應的1-10的數(shù)字；
     * 第三：遍歷原始數(shù)組，分別獲取個位、十位、百位等位對應的值，通過這個值獲取在多維數(shù)組中對應的數(shù)組，
     * 把原始數(shù)組中的這個元素添加到多維數(shù)組中對應的數(shù)組中，
     * 第四：開始收集；遍歷多維數(shù)組中的每個數(shù)組，把每個數(shù)組中的元素一個個賦值給原始數(shù)組元素，賦值一個，移除一個，
     * 同時count次數(shù)++
     *
     * @param a
     */
    public void sort(int[] a) {
        //獲取數(shù)組中的最大值
        int max = 0;
        for (int i = 0; i < a.length; i++) {
            if (max < a[i]) {
                max = a[i];
            }
        }

        //獲取最大值的位數(shù)
        int times = 0;
        while (max > 0) {
            max = max / 10;
            times++;
        }

        //創(chuàng)建一個多維數(shù)組
        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);
                //通過得到的位的值獲取多維數(shù)組中對應的數(shù)組，然后將該數(shù)據(jù)添加到對應的數(shù)組中
                ArrayList q = queue.get(x);
                q.add(a[j]);
            }

            //開始收集
            int count = 0;
            //遍歷多維數(shù)組中的每個數(shù)組
            for (int j = 0; j < 10; j++) {
                while (queue.get(j).size() > 0) {
                    ArrayList<Integer> q = queue.get(j);//獲取多維數(shù)組中的單個數(shù)組
                    //將第一個值賦值給原有的數(shù)組，然后移除第一個
                    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;
    }
}