當前位置：首頁 > news >正文

企業(yè)網(wǎng)站優(yōu)化案例論壇優(yōu)化seo

news 2025/7/12 9:20:37

企業(yè)網(wǎng)站優(yōu)化案例,論壇優(yōu)化seo,做公眾號可以看的網(wǎng)站,湖北省建設部網(wǎng)站公告歸并排序歸并排序遵循分治的思想：將原問題分解為幾個規(guī)模較小但類似于原問題的子問題，遞歸地求解這些子問題，然后合并這些子問題的解來建立原問題的解，歸并排序的步驟如下： 劃分：分解待排序的 n 個元素…

歸并排序

歸并排序遵循分治的思想：將原問題分解為幾個規(guī)模較小但類似于原問題的子問題，遞歸地求解這些子問題，然后合并這些子問題的解來建立原問題的解，歸并排序的步驟如下：

劃分：分解待排序的 n 個元素的序列成各具 n/2 個元素的兩個子序列，將長數(shù)組的排序問題轉換為短數(shù)組的排序問題，當待排序的序列長度為 1 時，遞歸劃分結束
合并：合并兩個已排序的子序列得出已排序的最終結果

歸并排序的代碼實現(xiàn)如下：

    private void sort(int[] nums, int left, int right) {if (left >= right) {return;}// 劃分int mid = left + right >> 1;sort(nums, left, mid);sort(nums, mid + 1, right);// 合并merge(nums, left, mid, right);}private void merge(int[] nums, int left, int mid, int right) {// 輔助數(shù)組int[] temp = Arrays.copyOfRange(nums, left, right + 1);int leftBegin = 0, leftEnd = mid - left;int rightBegin = leftEnd + 1, rightEnd = right - left;for (int i = left; i <= right; i++) {if (leftBegin > leftEnd) {nums[i] = temp[rightBegin++];} else if (rightBegin > rightEnd || temp[leftBegin] < temp[rightBegin]) {nums[i] = temp[leftBegin++];} else {nums[i] = temp[rightBegin++];}}}

歸并排序最吸引人的性質是它能保證將長度為 n 的數(shù)組排序所需的時間和 nlogn 成正比；它的主要缺點是所需的額外空間和 n 成正比。

算法特性：

空間復雜度：借助輔助數(shù)組實現(xiàn)合并，使用 O(n) 的額外空間；遞歸深度為 logn，使用 O(logn) 大小的棧幀空間。忽略低階部分，所以空間復雜度為 O(n)
非原地排序
穩(wěn)定排序
非自適應排序

以上代碼是歸并排序常見的實現(xiàn)，下面我們來一起看看歸并排序的優(yōu)化策略：

將多次創(chuàng)建小數(shù)組的開銷轉換為只創(chuàng)建一次大數(shù)組

在上文實現(xiàn)中，我們在每次合并兩個有序數(shù)組時，即使是很小的數(shù)組，我們都會創(chuàng)建一個新的 temp[] 數(shù)組，這部分耗時是歸并排序運行時間的主要部分。更好的解決方案是將 temp[] 數(shù)組定義成 sort() 方法的局部變量，并將它作為參數(shù)傳遞給 merge() 方法，實現(xiàn)如下：

    private void sort(int[] nums, int left, int right, int[] temp) {if (left >= right) {return;}// 劃分int mid = left + right >> 1;sort(nums, left, mid, temp);sort(nums, mid + 1, right, temp);// 合并merge(nums, left, mid, right, temp);}private void merge(int[] nums, int left, int mid, int right, int[] temp) {System.arraycopy(nums, left, temp, left, right - left + 1);int l = left, r = mid + 1;for (int i = left; i <= right; i++) {if (l > mid) {nums[i] = temp[r++];} else if (r > right || temp[l] < temp[r]) {nums[i] = temp[l++];} else {nums[i] = temp[r++];}}}

當數(shù)組有序時，跳過 merge() 方法

我們可以在執(zhí)行合并前添加判斷條件：如果 nums[mid] <= nums[mid + 1] 時我們認為數(shù)組已經(jīng)是有序的了，那么我們就跳過 merge() 方法。它不影響排序的遞歸調用，但是對任意有序的子數(shù)組算法的運行時間就變成線性的了，代碼實現(xiàn)如下：

    private void sort(int[] nums, int left, int right, int[] temp) {if (left >= right) {return;}// 劃分int mid = left + right >> 1;sort(nums, left, mid, temp);sort(nums, mid + 1, right, temp);// 合并if (nums[mid] > nums[mid + 1]) {merge(nums, left, mid, right, temp);}}private void merge(int[] nums, int left, int mid, int right, int[] temp) {System.arraycopy(nums, left, temp, left, right - left + 1);int l = left, r = mid + 1;for (int i = left; i <= right; i++) {if (l > mid) {nums[i] = temp[r++];} else if (r > right || temp[l] < temp[r]) {nums[i] = temp[l++];} else {nums[i] = temp[r++];}}}

對小規(guī)模子數(shù)組使用插入排序

對小規(guī)模數(shù)組進行排序會使遞歸調用過于頻繁，而使用插入排序處理小規(guī)模子數(shù)組一般可以將歸并排序的運行時間縮短 10% ~ 15%，代碼實現(xiàn)如下：

    /*** M 取值在 5 ~ 15 之間大多數(shù)情況下都能令人滿意*/private final int M = 9;private void sort(int[] nums, int left, int right) {if (left + M >= right) {// 插入排序insertSort(nums);return;}// 劃分int mid = left + right >> 1;sort(nums, left, mid);sort(nums, mid + 1, right);// 合并merge(nums, left, mid, right);}/*** 插入排序*/private void insertSort(int[] nums) {for (int i = 1; i < nums.length; i++) {int base = nums[i];int j = i - 1;while (j >= 0 && nums[j] > base) {nums[j + 1] = nums[j--];}nums[j + 1] = base;}}private void merge(int[] nums, int left, int mid, int right) {// 輔助數(shù)組int[] temp = Arrays.copyOfRange(nums, left, right + 1);int leftBegin = 0, leftEnd = mid - left;int rightBegin = leftEnd + 1, rightEnd = right - left;for (int i = left; i <= right; i++) {if (leftBegin > leftEnd) {nums[i] = temp[rightBegin++];} else if (rightBegin > rightEnd || temp[leftBegin] < temp[rightBegin]) {nums[i] = temp[leftBegin++];} else {nums[i] = temp[rightBegin++];}}}

快速排序

快速排序也遵循分治的思想，它與歸并排序不同的是，快速排序是 原地排序，而且快速排序會先排序當前數(shù)組，再對子數(shù)組進行排序，它的算法步驟如下：

哨兵劃分：選取數(shù)組中最左端元素為基準數(shù)，將小于基準數(shù)的元素放在基準數(shù)左邊，將大于基準數(shù)的元素放在基準數(shù)右邊
排序子數(shù)組：將哨兵劃分的索引作為劃分左右子數(shù)組的分界，分別對左右子數(shù)組進行哨兵劃分和排序

快速排序的代碼實現(xiàn)如下：

    private void sort(int[] nums, int left, int right) {if (left >= right) {return;}// 哨兵劃分int partition = partition(nums, left, right);// 分別排序兩個子數(shù)組sort(nums, left, partition - 1);sort(nums, partition + 1, right);}/*** 哨兵劃分*/private int partition(int[] nums, int left, int right) {// 以 nums[left] 作為基準數(shù)，并記錄基準數(shù)索引int originIndex = left;int base = nums[left];while (left < right) {// 從右向左找小于基準數(shù)的元素while (left < right && nums[right] >= base) {right--;}// 從左向右找大于基準數(shù)的元素while (left < right && nums[left] <= base) {left++;}swap(nums, left, right);}// 將基準數(shù)交換到兩子數(shù)組的分界線swap(nums, originIndex, left);return left;}private void swap(int[] nums, int left, int right) {int temp = nums[left];nums[left] = nums[right];nums[right] = temp;}

算法特性：

時間復雜度：平均時間復雜度為 O(nlogn)，最差時間復雜度為 O(n²)
空間復雜度：最差情況下，遞歸深度為 n，所以空間復雜度為 O(n)
原地排序
非穩(wěn)定排序
自適應排序

歸并排序的時間復雜度一直是 O(nlogn)，而快速排序在最壞的情況下時間復雜度為 O(n²)，為什么歸并排序沒有快速排序應用廣泛呢？

答：因為歸并排序是非原地排序，在合并階段需要借助非常量級的額外空間

快速排序有很多優(yōu)點，但是在哨兵劃分不平衡的情況下，算法的效率會比較低效。下面是對快速排序排序優(yōu)化的一些方法：

切換到插入排序

對于小數(shù)組，快速排序比插入排序慢，快速排序的 sort() 方法在長度為 1 的子數(shù)組中也會調用一次，所以，在排序小數(shù)組時切換到插入排序排序的效率會更高，如下：

    /*** M 取值在 5 ~ 15 之間大多數(shù)情況下都能令人滿意*/private final int M = 9;public void sort(int[] nums, int left, int right) {// 小數(shù)組采用插入排序if (left + M >= right) {insertSort(nums);return;}int partition = partition(nums, left, right);sort(nums, left, partition - 1);sort(nums, partition + 1, right);}/*** 插入排序*/private void insertSort(int[] nums) {for (int i = 1; i < nums.length; i++) {int base = nums[i];int j = i - 1;while (j >= 0 && nums[j] > base) {nums[j + 1] = nums[j--];}nums[j + 1] = base;}}private int partition(int[] nums, int left, int right) {int originIndex = left;int base = nums[left];while (left < right) {while (left < right && nums[right] >= base) {right--;}while (left < right && nums[left] <= base) {left++;}swap(nums, left, right);}swap(nums, left, originIndex);return left;}private void swap(int[] nums, int left, int right) {int temp = nums[left];nums[left] = nums[right];nums[right] = temp;}

基準數(shù)優(yōu)化

如果數(shù)組為倒序的情況下，選擇最左端元素為基準數(shù)，那么每次哨兵劃分會導致右數(shù)組長度為 0，進而使快速排序的時間復雜度為 O(n²)，為了盡可能避免這種情況，我們可以對基準數(shù)的選擇進行優(yōu)化，采用 三取樣切分 的方法：選取數(shù)組最左端、中間和最右端這三個值的中位數(shù)為基準數(shù)，這樣選擇的基準數(shù)大概率不是區(qū)間的極值，時間復雜度為 O(n²) 的概率大大降低，代碼實現(xiàn)如下：

    public void sort(int[] nums, int left, int right) {if (left >= right) {return;}// 基準數(shù)優(yōu)化betterBase(nums, left, right);int partition = partition(nums, left, right);sort(nums, left, partition - 1);sort(nums, partition + 1, right);}/*** 基準數(shù)優(yōu)化，將 left, mid, right 這幾個值中的中位數(shù)換到 left 的位置* 注意其中使用了異或運算進行條件判斷*/private void betterBase(int[] nums, int left, int right) {int mid = left + right >> 1;if ((nums[mid] < nums[right]) ^ (nums[mid] < nums[left])) {swap(nums, left, mid);} else if ((nums[right] < nums[left]) ^ (nums[right] < nums[mid])) {swap(nums, left, right);}}private int partition(int[] nums, int left, int right) {int originIndex = left;int base = nums[left];while (left < right) {while (left < right && nums[right] >= base) {right--;}while (left < right && nums[left] <= base) {left++;}swap(nums, left, right);}swap(nums, originIndex, left);return left;}private void swap(int[] nums, int left, int right) {int temp = nums[left];nums[left] = nums[right];nums[right] = temp;}

三向切分

在數(shù)組有大量重復元素的情況下，快速排序的遞歸性會使元素全部重復的子數(shù)組經(jīng)常出現(xiàn)，而對這些數(shù)組進行快速排序是沒有必要的，我們可以對它進行優(yōu)化。

一個簡單的想法是將數(shù)組切分為三部分，分別對應小于、等于和大于基準數(shù)的數(shù)組，每次將其中“小于”和“大于”的數(shù)組進行排序，那么最終也能得到排序的結果，這種策略下我們不會對等于基準數(shù)的子數(shù)組進行排序，提高了排序算法的效率，它的算法流程如下：

從左到右遍歷數(shù)組，維護指針 l 使得 [left, l - 1] 中的元素都小于基準數(shù)，維護指針 r 使得 [r + 1, right] 中的元素都大于基準數(shù)，維護指針 mid 使得 [l, mid - 1] 中的元素都等于基準數(shù)，其中 [mid, r] 區(qū)間中的元素還未確定大小關系，圖示如下：

快速排序-荷蘭國旗.jpg

它的代碼實現(xiàn)如下：

    public void sort(int[] nums, int left, int right) {if (left >= right) {return;}// 三向切分int l = left, mid = left + 1, r = right;int base = nums[l];while (mid <= r) {if (nums[mid] < base) {swap(nums, l++, mid++);} else if (nums[mid] > base) {swap(nums, mid, r--);} else {mid++;}}sort(nums, left, l - 1);sort(nums, r + 1, right);}private void swap(int[] nums, int left, int right) {int temp = nums[left];nums[left] = nums[right];nums[right] = temp;}