欧美在线免费看,香蕉视频网站入口,毛片在线不卡

①排序

所謂排序，就是使一串記錄，按照其中的某個或某些關鍵字的大小，遞增或遞減的排列起來的操作。排序算法，就是如何使得記錄按照要求排列的方法。排序算法在很多領域得到相當地重視，尤其是在大量數據的處理方面。一個優秀的算法可以節省大量的資源。在各個領域中考慮到數據的各種限制和規范，要得到一個符合實際的優秀算法，得經過大量的推理和分析。

? 復雜度

java算法之排序算法大全

排序算法	平均時間	最差時間	穩定性	空間	備注
冒泡排序	O(n2)	O(n2)	穩定	O(1)	n較小時好
選擇排序	O(n2)	O(n2)	不穩定	O(1)	n較小時好
插入排序	O(n2)	O(n2)	穩定	O(1)	大部分已有序時好
希爾排序	O(nlogn)	O(ns)(1<s<2)	不穩定	O(1)	s是所選分組
快速排序	O(nlogn)	O(n2)	不穩定	O(logn)	n較大時好
歸并排序	O(nlogn)	O(nlogn)	穩定	O(n)/O(1)	n較大時好
基數排序	O(n*k)	O(n*k)	穩定	O(n)	n為數據個數，k為數據位數
堆排序	O(nlogn)	O(nlogn)	不穩定	O(1)	n較大時好
桶排序	O(n+k)	O(n2)	穩定	O(n+k)
計數排序	O(n+k)	O(n+k)	穩定	O(k)

?冒泡排序

算法步驟

比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
對每一對相鄰元素作同樣的工作。這步做完后，最后的元素會是最大的數。
針對所有的元素重復以上的步驟，除了最后一個。
持續每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較。
一共進行了 數組元素個數-1 次大循環，小循環要比較的元素越來越少。
優化：如果在某次大循環，發現沒有發生交換，則證明已經有序。

public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = {4, 5, 1, 6, 2};
        int[] res = bubbleSort(arr);
        System.out.println(Arrays.toString(res));
    }

    public static int[] bubbleSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            boolean flag = true;  //定義一個標識，來記錄這趟大循環是否發生了交換
            for (int j = 0; j < arr.length - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    flag = false;
                }
            }
            //如果這次循環沒發生交換，直接停止循環
            if (flag){
                break;
            }
        }
        return arr;
    }
}

?選擇排序

算法步驟

遍歷整個數組，找到最小（大）的元素，放到數組的起始位置。
再遍歷剩下的數組，找到剩下元素中的最小（大）元素，放到數組的第二個位置。
重復以上步驟，直到排序完成。
一共需要遍歷 數組元素個數-1 次，當找到第二大（小）的元素時，可以停止。這時最后一個元素必是最大（小）元素。

public class SelectSort {
    public static void main(String[] args) {
        int[] arr = {3, 1, 6, 10, 2};
        int[] res = selectSort(arr);
        System.out.println(Arrays.toString(res));
    }

    public static int[] selectSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            int min = i;
            for (int j = i + 1; j < arr.length; j++) {
                if(arr[min] > arr[j]){
                    min = j;
                }
            }
            // 將找到的最小值和i位置所在的值進行交換
            int temp = arr[i];
            arr[i] = arr[min];
            arr[min] = temp;
        }
        return arr;
    }
}

?插入排序

算法步驟

將待排序序列第一個元素看做一個有序序列，把第二個元素到最后一個元素當成是未排序序列。
從頭到尾依次掃描未排序序列，將掃描到的每個元素插入有序序列的適當位置。（如果待插入的元素與有序序列中的某個元素相等，則將待插入元素插入到相等元素的后面）

java算法之排序算法大全

黑色代表有序序列，紅色代表待插入元素

public class InsertSort {
    public static void main(String[] args) {
        int[] arr = {3, 1, 6, 10, 2};
        int[] res = insertSort(arr);
        System.out.println(Arrays.toString(res));
    }

    public static int[] insertSort(int[] arr) {
        //從數組的第二個元素開始選擇合適的位置插入
        for (int i = 1; i < arr.length; i++) {
            //記錄要插入的數據,后面移動元素可能會覆蓋該位置上元素的值
            int temp = arr[i];
            //從已經排序的序列最右邊開始比較，找到比其小的數
            //變量j用于遍歷前面的有序數組
            int j = i;
            while (j > 0 && temp < arr[j - 1]) {
                //如果有序數組中的元素大于temp，則后移一個位置
                arr[j] = arr[j - 1];
                j--;
            }
            //j所指位置就是待插入的位置
            if (j != i) {
                arr[j] = temp;
            }
        }
        return arr;
    }
}

?希爾排序

插入排序存在的問題

當最后一個元素為整個數組的最小元素時，需要將前面的有序數組中的每個元素都向后移一位，這樣是非常花時間的。所以有了希爾排序來幫我們將數組從無序變為整體有序再變為有序。

算法步驟

選擇一個增量序列 t1（一般是數組長度/2），t2（一般是一個分組長度/2），……，tk，其中 ti > tj, tk = 1；
按增量序列個數 k，對序列進行 k 趟排序；
每趟排序，根據對應的增量 ti，將待排序列分割成若干長度為 m 的子序列，分別對各子表進行直接插入排序。當增量因子為 1 時，整個序列作為一個表來處理，表長度即為整個序列的長度。

java算法之排序算法大全

public class ShellSort {
    public static void main(String[] args) {
        int[] arr = {3, 6, 1, 4, 5, 8, 2, 0};
        int[] res = shellSort(arr);
        System.out.println(Arrays.toString(res));
    }

    public static int[] shellSort(int[] arr) {
        //將數組分為gap組,每個組內部進行插入排序
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            //i用來指向未排序數組的首個元素
            for (int i = gap; i < arr.length; i++) {
                int temp = arr[i];
                int j = i;
                while (j - gap >= 0 && temp < arr[j - gap]) {
                    arr[j] = arr[j - gap];
                    j -= gap;
                }
                arr[j] = temp;
            }
        }
        return arr;
    }
}

?快速排序

算法步驟

先把數組中的一個數當做基準數（pivot），一般會把數組中最左邊的數當做基準數。
然后從兩邊進行檢索。
- 先從右邊檢索比基準數小的
- 再從左邊檢索比基準數大的
- 如果檢索到了，就停下，然后交換這兩個元素。然后再繼續檢索
- 直到兩邊指針重合時，把基準值和重合位置值交換
排序好后，該基準就處于數列的中間位置。這個稱為分區（partition）操作；
然后遞歸地（recursive）把小于基準值的子數組和大于基準值元素的子數組再排序。

java算法之排序算法大全

你注意最后形成的這棵二叉樹是什么？是一棵二叉搜索樹

你甚至可以這樣理解：快速排序的過程是一個構造二叉搜索樹的過程。

但談到二叉搜索樹的構造，那就不得不說二叉搜索樹不平衡的極端情況，極端情況下二叉搜索樹會退化成一個鏈表，導致操作效率大幅降低。為了避免出現這種極端情況，需要引入隨機性。

public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {8, 12, 19, -1, 45, 0, 14, 4, 11};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    public static void quickSort(int[] arr, int left, int right) {
        //遞歸終止條件
        if (left >= right) return;
        //定義數組第一個數為基準值
        int pivot = arr[left];
        //定義兩個哨兵
        int i = left;
        int j = right;

        while (i != j) {
            //從右往左找比基準值小的數，找到就停止，沒找到就繼續左移
            while (pivot <= arr[j] && i < j) j--;
            //從左往右找比基準值大的數，找到就停止，沒找到就繼續右移
            while (pivot >= arr[i] && i < j) i++;
            //兩邊都找到就交換它們
            if (i < j) { 
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        //此時，i和j相遇，把基準值和重合位置值交換
        arr[left] = arr[i];
        arr[i] = pivot;
        quickSort(arr, left, i - 1);//對左邊的子數組進行快速排序
        quickSort(arr, i + 1, right);//對右邊的子數組進行快速排序
    }
}

private static void sort(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }
        int p = partition(nums, left, right);
        sort(nums, left, p - 1);
        sort(nums, p + 1, right);
}

public static int partition(int[] arr, int left, int right) {
      int pivot = arr[left];//定義基準值為數組第一個數
      int i = left;
      int j = right;
      while (i != j) {
          //case1:從右往左找比基準值小的數，找到就停止，沒找到就繼續左移
          while (pivot <= arr[j] && i < j) j--;
          //case2:從左往右找比基準值大的數，找到就停止，沒找到就繼續右移
          while (pivot >= arr[i] && i < j) i++;
          //將找到的兩數交換位置
          if (i < j) { 
              int temp = arr[i];
              arr[i] = arr[j];
              arr[j] = temp;
          }
      }
      arr[left] = arr[i];
      arr[i] = pivot;//把基準值放到合適的位置
      return i;
}

參考：快速排序法（詳解）

?歸并排序

歸并排序（Merge sort）是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。

算法步驟

申請空間，該空間用來存放合并后的序列；
設定兩個指針，最初位置分別為兩個已經排序序列的起始位置；
比較兩個指針所指向的元素，選擇相對小的元素放入到合并空間，并移動指針到下一位置；
重復步驟 3 直到某一指針達到序列尾；
將序列剩下的所有元素直接復制到合并序列尾。

java算法之排序算法大全

分治法

治理階段

public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {8, 4, 5, 7, 1, 3, 6, 2};
        int[] tmp = new int[arr.length];
        mergeSort(arr, 0, arr.length - 1, tmp);
        System.out.println(Arrays.toString(arr));
    }

    //分+治
    public static void mergeSort(int[] arr, int left, int right, int[] tmp) {

        if(left >= right){
            return ;
        }
        int mid = (left + right) / 2;//中間索引
        //向左遞歸進行分解
        mergeSort(arr, left, mid, tmp);
        //向右遞歸進行分解
        mergeSort(arr, mid + 1, right, tmp);
        //合并（治理）
        merge(arr, left, right, tmp);
    }


    //治理階段（合并）
    public static void merge(int[] arr, int left, int right, int[] tmp) {
        int mid = (left + right) / 2;
        int i = left; // 初始化i, 左邊有序序列的初始索引
        int j = mid + 1; //初始化j, 右邊有序序列的初始索引
        int t = 0; // 指向temp數組的當前索引

        //(一)
        //先把左右兩邊(有序)的數據按照規則填充到temp數組
        //直到左右兩邊的有序序列，有一邊處理完畢為止
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                tmp[t++] = arr[i++];
            } else {
                tmp[t++] = arr[j++];
            }
        }
        //(二)
        //把有剩余數據的一邊的數據依次全部填充到temp
        while (i <= mid) {//左邊的有序序列還有剩余的元素，就全部填充到temp
            tmp[t++] = arr[i++];
        }
        while (j <= right) {
            tmp[t++] = arr[j++];
        }
        //(三)
        //將temp數組的元素拷貝到arr
        t = 0;
        while (left <= right) {
            arr[left++] = tmp[t++];
        }
    }
}

?基數排序

基數排序是使用空間換時間的經典算法

算法步驟

將所有待比較數值（正整數）統一為同樣的數位長度，數位較短的數前面補零
事先準備10個數組(10個桶)，對應位數的 0-9
根據每個數最低位值(個位)，將數放入到對應位置桶中，即進行一次排序
然后從 0-9 個數組/桶，依次，按照加入元素的先后順序取出
以此類推，從最低位排序一直到最高位（個位->十位->百位->…->最高位），循環輪數為最大數位長度
排序完成以后, 數列就變成一個有序序列
需要我們獲得最大數的位數：可以通過將最大數變為String類型，再求得它的長度即可

排序過程	排序后結果

public class RadixSort {
    public static void main(String[] args) {
        int[] arr = {53, 3, 542, 748, 14, 214};
        radixSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void radixSort(int[] arr) {
        //定義一個二維數組，表示10個桶, 每個桶就是一個一維數組
        int[][] bucket = new int[10][arr.length];
        //為了記錄每個桶中存放了多少個數據,我們定義一個數組來記錄各個桶的每次放入的數據個數
        //比如：bucketElementCounts[0] , 記錄的就是 bucket[0] 桶的放入數據個數
        int[] bucketElementCounts = new int[10];
        //最大位數
        int maxLen = getMaxLen(arr);

        for (int i = 0, n = 1; i < maxLen; i++, n *= 10) {
            //maxLen輪排序
            for (int j = 0; j < arr.length; j++) {
                //取出每個元素的對應位的值
                int digitOfElement = arr[j] / n % 10;
                //放入到對應的桶中
                bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
                bucketElementCounts[digitOfElement]++;
            }
            //按照桶的順序和加入元素的先后順序取出，放入原來數組
            int index = 0;
            for (int k = 0; k < 10; k++) {
                //如果桶中，有數據，我們才放入到原數組
                int position = 0;
                while (bucketElementCounts[k] > 0) {
                    //取出元素放入到arr
                    arr[index++] = bucket[k][position++];
                    bucketElementCounts[k]--;
                }
            }
        }

    }

    //得到該數組中最大元素的位數
    public static int getMaxLen(int[] arr) {
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        //將最大值轉為字符串，它的長度就是它的位數
        int maxLen = (max + "").length();
        return maxLen;
    }

}

?堆排序

給定一個數組：String[] arr = {“S”,”O”,”R”,”T”,”E”,”X”,”A”,”M”,”P”,”L”,”E”}請對數組中的字符按從小到大排序。

實現步驟：

1.構造堆；
2.得到堆頂元素，這個值就是最大值；
3.交換堆頂元素和數組中的最后一個元素，此時所有元素中的最大元素已經放到合適的位置；
4.對堆進行調整，重新讓除了最后一個元素的剩余元素中的最大值放到堆頂；
5.重復2~4這個步驟，直到堆中剩一個元素為止。

java算法之排序算法大全

public class HeapSort {

    public static void main(String[] args) throws Exception {
        String[] arr = {"S", "O", "R", "T", "E", "X", "A", "M", "P", "L", "E"};
        HeapSort.sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    //判斷heap堆中索引i處的元素是否小于索引j處的元素
    private static boolean less(Comparable[] heap, int i, int j) {
        return heap[i].compareTo(heap[j]) < 0;
    }

    //交換heap堆中i索引和j索引處的值
    private static void exch(Comparable[] heap, int i, int j) {
        Comparable tmp = heap[i];
        heap[i] = heap[j];
        heap[j] = tmp;
    }


    //根據原數組source，構造出堆heap
    private static void createHeap(Comparable[] source, Comparable[] heap) {
        //把source中的元素拷貝到heap中，heap中的元素就形成一個無序的堆
        System.arraycopy(source, 0, heap, 1, source.length);
        //對堆中的元素做下沉調整(從長度的一半處開始，往索引1處掃描)
        for (int i = (heap.length) / 2; i > 0; i--) {
            sink(heap, i, heap.length - 1);
        }

    }

    //對source數組中的數據從小到大排序
    public static void sort(Comparable[] source) {
        //構建堆
        Comparable[] heap = new Comparable[source.length + 1];
        createHeap(source, heap);
        //定義一個變量，記錄未排序的元素中最大的索引
        int N = heap.length - 1;
        //通過循環，交換1索引處的元素和排序的元素中最大的索引處的元素
        while (N != 1) {
            //交換元素
            exch(heap, 1, N);
            //排序交換后最大元素所在的索引，讓它不要參與堆的下沉調整
            N--;
            //需要對索引1處的元素進行對的下沉調整
            sink(heap, 1, N);
        }
        //把heap中的數據復制到原數組source中
        System.arraycopy(heap, 1, source, 0, source.length);

    }

    //在heap堆中，對target處的元素做下沉，范圍是0~range
    private static void sink(Comparable[] heap, int target, int range) {

        while (2 * target <= range) {
            //1.找出當前結點的較大的子結點
            int max;
            if (2 * target + 1 <= range) {
                if (less(heap, 2 * target, 2 * target + 1)) {
                    max = 2 * target + 1;
                } else {
                    max = 2 * target;
                }
            } else {
                max = 2 * target;
            }

            //2.比較當前結點的值和較大子結點的值
            if (!less(heap, target, max)) {
                break;
            }
            exch(heap, target, max);
            target = max;
        }
    }
}