數據結構與算法的基數排序是什么

本篇內容主要講解“數據結構與算法的基數排序是什么”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學習“數據結構與算法的基數排序是什么”吧!

 基數排序

1. 鴻蒙官方戰略合作共建——HarmonyOS技術社區

2. 基數排序(radix sort)屬于“分配式排序”(distribution sort)，又稱為“桶子法”(bucket sort)或bin  sort,顧明思議，它是通過鍵值的各個位的值，將要排序的元素分配至某些桶中，達到排序的作用。

3. 基數排序屬于穩定性的排序，基數排序法是效率高的穩定性排序法。

4. 基數排序是桶排序的擴展。

5. 基數排序是1887年赫爾曼·何樂禮發明的。它是這樣實現的：將整數按位數切割成不同的數字，然后按每個位數分別比較。

排序的基本思想

將所有待比較的值統一為同樣的數位長度，數位較短的數前面補零。然后，從最低位開始，依次進行一次排序。這樣從最低位排序一直到最高位排序完成以后，數列就變成一個有序序列。

代碼案例

package com.xie.sort;  public class RadixSort {     public static void main(String[] args) {         int[] arr = new int[8000000];         for (int i = 0; i < 8000000; i++) {             arr[i] = (int)(Math.random()*800000000);         }         long start = System.currentTimeMillis();         radixSort(arr);         long end = System.currentTimeMillis();         System.out.println("耗時："+(end-start)+"ms");         /*         800萬數據，耗時：939ms          */     }      //基數排序     public static void radixSort(int[] arr) {          int max = arr[0];         for (int i = 1; i < arr.length; i++) {             if (arr[i] > max) {                 max = arr[i];             }         }         //數組中的最長位數         int maxLength = (max + "").length();          //第1輪（針對每個元素的個位進行排序處理）         //定義一個二維數組，表示10個桶，每個桶就是一個一維數組         //1.二維數組包含10個一維數組         //2.為了防止在放入數的時候，數據溢出，則每個一維數組（桶），大小定為arr.length         //3.基數排序是使用空間換時間的經典算法         int[][] bucket = new int[10][arr.length];          //為了記錄每個桶中，實際存放了多少數據，我們定義一個一維數組來記錄各個桶的每次放入的數據的個數。         //bucketElementCounts[0]，記錄的就是bucket[0]桶的放入數據的個數。         int[] bucketElementCounts = new int[10];          //按照桶的順序（一維數組的下標依次取出數據，放入原來數組）         int index = 0;         for (int i = 0, n = 10; i < maxLength; i++, n *= 10) {             for (int j = 0; j < arr.length; j++) {                 //取出位數                 int digitOfElement = arr[j] / n % 10;                 //讓如對應的桶中                 bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];                 bucketElementCounts[digitOfElement]++;             }              index = 0;             //遍歷每個桶，并將桶中的數據，放入原數組             for (int k = 0; k < bucketElementCounts.length; k++) {                 //如果桶中有數據，才放入到原數組                 if (bucketElementCounts[k] != 0) {                     //循環桶中第k個桶（即第k個一維數組),放入。                     for (int l = 0; l < bucketElementCounts[k]; l++) {                         //取出元素放入arr                         arr[index] = bucket[k][l];                         index++;                     }                 }                 bucketElementCounts[k] = 0;             }         }     } }

基數排序說明

1. 基數排序是拿空間換時間的，對海量數據進行排序時，容易造成OutOfMemoryError.

2. 基數排序時穩定的。【注：假定在待排序的記錄序列中，存在多個具有相同的關鍵字的記錄，若經過排序，這些記錄的相對次序保持不變，即在原序列中r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，則稱這種算法是穩定的，否則不穩定】。

3. 對于有負數的數組進行基數排序

到此，相信大家對“數據結構與算法的基數排序是什么”有了更深的了解，不妨來實際操作一番吧！這里是億速云網站，更多相關內容可以進入相關頻道進行查詢，關注我們，繼續學習！