中文字幕av专区_日韩电影在线播放_精品国产精品久久一区免费式_av在线免费观看网站

溫馨提示×

溫馨提示×

您好,登錄后才能下訂單哦!

密碼登錄×
登錄注冊×
其他方式登錄
點擊 登錄注冊 即表示同意《億速云用戶服務條款》

Java數據結構常見排序算法有哪些

發布時間:2023-02-01 11:06:13 來源:億速云 閱讀:171 作者:iii 欄目:編程語言

今天小編給大家分享一下Java數據結構常見排序算法有哪些的相關知識點,內容詳細,邏輯清晰,相信大部分人都還太了解這方面的知識,所以分享這篇文章給大家參考一下,希望大家閱讀完這篇文章后有所收獲,下面我們一起來了解一下吧。

1、 認識排序

在學校中,如果我們要參加運動會,或者軍訓的時候,會按照身高從矮到高進行站隊,比如上課老師手上拿的考勤表,通常是按照學號從低到高進行排序的。再比如編程語言排行榜,也是在排序。

Java數據結構常見排序算法有哪些

生活中有相當多的排序場景,由此可知,排序還是很重要的, 本章就會介紹常見的一些排序算法。

所謂排序呢,就拿我們上面的舉例來說,會按照某個或某些關鍵字的大小,遞增或者遞減排列起來的操作,這就是排序,這里面也涉及到排序的穩定性,舉個例子:

比如有這樣的一組數據:B  D  A  C  A  F,要按照他們的 ascll 碼來排序,這里出現了兩個 A,我們把第一個出現的 A 稱為 A1,第二個出現的 A 稱為 A2。

假定排序后結果為:A1  A2  B  C  D  F,那么這個排序算法就是穩定的。

假設排序后結果為:A2  A1  B  C  D  F,那么這個排序算法就是不穩定的。

簡而言之,如果待排序的數據中,有兩個相同的元素,排序結束后,這兩個元素的關系沒有發生改變,比如 A1 排序前在 A2 前面,排完序后,A1 還在 A2 前面,這就是穩定的排序算法。

注意:一個不穩定的排序算法,天生就是不穩定的,但是一個穩定的排序算法,你可以把它設計成不穩定的。

2、常見排序的分類

Java數據結構常見排序算法有哪些

這張圖,概括了我們后續要講的排序算法,接著正式進入本章的學習吧!(排序算法章節,默認都是升序排序) 注:后續所說的復雜度 log,都是以2為底,特殊的會標注出來。

3、直接插入排序

現在想請各位小伙伴,想象一下自己在摸撲克牌,摸了第一張牌放在了自己的手中,接著再摸一張,把這張牌跟手上的一張牌進行比較,把它放到合適的位置, 接著再摸一張,把這張牌跟手上的兩張牌進行比較,放到合適的位置。

這就是直接插入排序,簡單來說,我們每次取的元素,會往一個有序的序列中插入,也就是每次摸牌之前,手上的牌都是排好序的,我們只需要把新摸到的牌,依次與手上有序的牌進行比較,把它放入合適的位置就行!

這里我們用一副靜態的圖來簡單演示下:

Java數據結構常見排序算法有哪些

大致的思想我們已經明白了,接下來我們就需要用代碼來實現他:

public void insertSort(int[] array) {
   // 外循環控制趟數, 第一張牌默認有序, 所以 i 從 1 開始
   for (int i = 1; i < array.length; i++) {
       int tmp = array[i]; //當前摸到的牌
       // 每次從手中牌的最后一張牌開始比較, 一直比到第一張牌
       int j = i - 1;
       for (; j >= 0; j--) {
           //如果當前位置的牌,大于我摸到的牌,就往后挪
           if (array[j] > tmp) {
               array[j + 1] = array[j];
           } else {
               break;
           }
       }
       // 把摸到的牌放到對應位置上
       array[j + 1] = tmp;
   }
}
  • 時間復雜度分析:外循環一共要 n - 1 次,內循環每次最差的情況下要比較 1....n 次,那么去掉 n 前面的小項,也就是 (n - 1) * n 次,即 n^2 - n,去掉最小項,最后的時間復雜度為 O(n^2)

  • 空間復雜度分析:只是開辟了一個 tmp 的變量 i,j,常數,即空間復雜度:O(1)

  • 穩定性:穩定

  • 該排序再數據越接近有序的情況,時間效率越高。

4、希爾排序(縮小增量排序)

這個排序是直接插入排序的一種優化,你可以想象一下,你面前有并排放好的 8 個愛心號碼牌,但是它們是無序的,我們要給號碼牌分組,按要求,第一次間隔為 4 個號碼牌的為一組,分完組后進行直接插入排序,第二次間隔為 2 個號碼牌的為一組,進行直接插入排序,第三次間隔為 1 個號碼牌為一組,進行直接插入排序。

聽到這有點沒理解,沒關系,我們就通過畫圖來把我上述說的內容再次理解下:

Java數據結構常見排序算法有哪些

由上圖我們可以發現,當間隔 > 1 的時候,都是預排序,也就是讓我們的數據更接近有序,但是當間隔為 1 的時候,就是直接插入排序了,前面我們說過,直接插入排序,再數據接近有序的時候時間效率是很快的。由此可見,希爾排序,是直接插入排序的優化版。

如何在代碼中實現呢?間隔的值如何取呢?代碼中把這個間隔的值稱為 gap,這個 gap 的取值方法有很多,有的人提出 gap 為奇數好,有的提出 gap 為偶數好,我們就采取一種比較簡單的方法來取 gap 值,首次取數組長度一半的值為 gap,后續 gap /= 2,即可。當 gap 為 1,也就是直接插入排序了。

代碼實現如下:

public void shellSort(int[] array) {
   // gap初始值設置成數組長度的一半
   int gap = array.length >> 1;
   // gap 為 1 的時候直接插入排序
   while (gap >= 1) {
       shell(array, gap);
       gap >>= 1; // 更新 gap 值 等價于 -> gap /= 2;
   }
}
private void shell(int[] array, int gap) {
   for (int i = gap; i < array.length; i++) {
       int tmp = array[i];
       int j = i - gap;
       for (; j >= 0; j -= gap) {
           if (array[j] > tmp) {
               array[j + gap] = array[j];
           } else {
               break;
           }
       }
       array[j + gap] = tmp;
   }
}

如果實在是不好理解,就結合上邊講的直接插入排序來理解,相信你能理解到的。

  • 時間復雜度分析:希爾排序的時間復雜度不好分析, 這里我們就大概記一下,約為 O(n^1.3),感興趣的話,可以查閱一下相關書籍。

  • 空間復雜度分析:仍然開辟的是常數個變量,空間復雜度為 O(1)

  • 穩定性:不穩定

5、選擇排序

這個排序是個很簡單的排序,你想象一下,有個小屁孩,喜歡玩小球,我給他安排了個任務,把這一排小球從小到大排列起來,擺給我看,于是小屁孩就找,每次從一排小球中找出最大的,放到最后,固定不動,那是不是也就是說,每次能確定一個最大的石子的最終位置了。我們來看圖:

Java數據結構常見排序算法有哪些

通過圖片我們也能看出來,每次找到最大值于最后一個值交換,所以每趟都能把最大的放到最后固定不動,每趟能排序一個元素出來,那這樣用代碼來實現就很簡單了:

public void selectSort(int[] array) {
   int end = array.length - 1;
   // 剩最后一個元素的時候, 不用比較了, 已經有序了
   // 所以 i < array.length - 1
   for (int i = 0; i < array.length - 1; i++) {
       int max = 0;
       int j = 0;
       while (j <= end) {
           if (array[j] > array[max]) {
               max = j;
           }
           j++;
       }
       //找到了最大值的下標, 把最大值與最后一個值交換
       swap(array, max, end--); // end-- 最后一個元素固定了, 不用參與比較
   }
}

這個算法有沒有可以優化的空間呢?

有!那么既然小屁孩能一次找出最大的球,那能不能讓小屁孩一次找出兩個球出來呢?分別是這些球中,最大的和最小的,最大的放在最右邊,最小的放在最左邊,那么我們每次就能確定兩個球的最終位置,也就是我們一次能排序兩個元素。圖解:

Java數據結構常見排序算法有哪些

代碼實現如下:

public void selectSort(int[] array) {
   int left = 0;
   int right = array.length - 1;
   while (left < right) {
       int maxIndex = left;
       int minIndex = left;
       // i = left + 1 -> 每次找最大最小值下標的時候, 可以不用算默認給的最大值和最小值下標
       for (int i = left + 1; i <= right; i++) {
           if (array[i] > array[maxIndex]) {
               maxIndex = i;
           }
           if (array[i] < array[minIndex]) {
               minIndex = i;
           }
       }
       swap(array, minIndex, left);
       // 如果最大值為 left 的位置情況的話, 走到這, 最大值已經被交換到 min 位置上了
       if (maxIndex == left) {
           // 更新最大值的位置
           maxIndex = minIndex;
       }
       swap(array, maxIndex, right);
       left++;
       right--;
   }
}
  • 時間復雜度分析:雖然是優化了,但去小項之后,還是 O(n^2)

  • 空間復雜度分析:O(1)

  • 穩定性:不穩定

  • 實際開發中用的不多

6、堆排序

如果你有學習過優先級隊列,或者看過博主優先級隊列的文章,那么這個排序對于你來說還是很輕松的,當然在堆排序的講解中,不會過多的去介紹堆的概念,如果對這部分概念還不理解,可以移至博主的上一篇文章進行學習。

堆排序,簡單來說,就是把一組數據,看成一個完全二叉樹,再把這棵樹,建大堆或者建小堆,接著進行排序的一種思路。至于如何建大堆或小堆,和向上調整算法以及向下調整算法,這里也不多介紹了,博主的上篇文章都詳細介紹過。

這里我們來分析一下,排升序應該建什么堆?大堆!排降序建小堆!

這里我們來排升序,建大堆,因為大堆堆頂元素一定是堆中最大的,所以我們可以把堆頂元素和最后一個元素進行交換,這樣我們就確認了最大值的位置,接著將交換后的堆頂元素進行向下調整,仍然使得該數組滿足大堆的特性!圖解如下:

Java數據結構常見排序算法有哪些

Java數據結構常見排序算法有哪些

如上圖步驟也很簡單,先是將數組建成大堆,然后利用大堆來進行堆排序,首先將堆頂元素和最后一個元素交換,由此最大的元素就有序了,接著將該堆進行向下調整,使繼續滿足大堆性質,依次進行下去即可。

代碼實現:

public void heapSort(int[] array) {
   // 建大堆 從最后一個非葉子節點開始向下調整
   // 非葉子節點下標 = (孩子節點下標 - 1) / 2
   for (int parent = (array.length - 1 - 1) / 2; parent >= 0; parent--) {
       shiftDown(array, parent, array.length);
   }
   // 建大堆完成后, 每次堆頂元素與最后一個元素交換, 鎖定最大元素的位置
   for (int len = array.length - 1; len > 0; len--) {
       swap(array, 0, len); //根節點與最后一個元素交換
       shiftDown(array, 0, len); //根節點位置向下調整
   }
}
private void shiftDown(int[] array, int parent, int len) {
   int child = parent * 2 + 1;
   while (child < len) {
       if (child + 1 < len && array[child + 1] > array[child]) {
           child++;
       }
       // 判斷父節點是否大于較大的孩子節點
       if (array[parent] < array[child]) {
           swap(array, parent, child);
           // 更新下標的位置
           parent = child;
           child = parent * 2 + 1;
       } else {
           return;
       }
   }
}
  • 時間復雜度分析:建堆的時間復雜度優先級隊列那期有說過為 O(n),排序調整堆的時候,一共要調整 n-1 次,每次向下調整的時間復雜度是 logn,所以即 logn(n - 1),即 O(n*logn),加上面建堆的時間復雜度:O(n) + O(n*logn),最終時間復雜度也就是:O(n*logn)。

  • 空間復雜度分析:O(1)

  • 穩定性:不穩定

以上就是“Java數據結構常見排序算法有哪些”這篇文章的所有內容,感謝各位的閱讀!相信大家閱讀完這篇文章都有很大的收獲,小編每天都會為大家更新不同的知識,如果還想學習更多的知識,請關注億速云行業資訊頻道。

向AI問一下細節

免責聲明:本站發布的內容(圖片、視頻和文字)以原創、轉載和分享為主,文章觀點不代表本網站立場,如果涉及侵權請聯系站長郵箱:is@yisu.com進行舉報,并提供相關證據,一經查實,將立刻刪除涉嫌侵權內容。

AI

西昌市| 楚雄市| 察哈| 庆元县| 高淳县| 东阳市| 哈尔滨市| 红桥区| 道孚县| 章丘市| 江门市| 乐东| 桂阳县| 满洲里市| 双流县| 兰州市| 登封市| 水富县| 榆林市| 务川| 卓资县| 沛县| 文水县| 瑞金市| 高邮市| 浦东新区| 即墨市| 白城市| 望江县| 穆棱市| 南宫市| 托克逊县| 都江堰市| 九寨沟县| 丹寨县| 汶上县| 新沂市| 卓尼县| 临邑县| 宣威市| 镇赉县|