?Java數(shù)據(jù)結(jié)構(gòu)的十大排序

更新時(shí)間：2022年01月26日 15:38:26 作者：wwzzzzzzzzzzzzz?

這篇文章主要介紹了?Java數(shù)據(jù)結(jié)構(gòu)的十大排序，排序算法分為比較類排序和非比較類排序，具體的內(nèi)容，需要的朋友參考下面思維導(dǎo)圖及文章介紹，希望對(duì)你有所幫助

1.直接插入排序

1.1 動(dòng)圖演示

1.2 插入排序的思路

從第一個(gè)元素開始,這里我們第一個(gè)元素是已排序的.
取下一個(gè)元素,和有序序列的元素從后往前比較.( 有序區(qū)間 : [0,i) )
如果得到的有序序列的元素比該元素大則將取得的有序元素往后放
重復(fù)3操作,直到得到的有序元素比該元素小, 或者有序元素比完了.記錄這個(gè)位置
然后將該元素放入到這個(gè)位置.
遍歷數(shù)組,重復(fù)2~5的操作.

1.3 代碼實(shí)現(xiàn)

 ? /**
? ? ?* 時(shí)間復(fù)雜度:
? ? ?* ? ? ?最好的情況: O(n)
? ? ?* ? ? ?最壞的情況: O(n^2)
? ? ?* 空間復(fù)雜度: O(1)
? ? ?* @param array
? ? ?*/
? ? public static void insertSort(int[] array) {
? ? ? ? for (int i = 1; i < array.length; i++) {
? ? ? ? ? ? int j = i - 1;
? ? ? ? ? ? int tmp = array[i];
? ? ? ? ? ? while (j >= 0) {
? ? ? ? ? ? ? ? if (array[j] > tmp) {
? ? ? ? ? ? ? ? ? ? array[j + 1] = array[j];
? ? ? ? ? ? ? ? ? ? j--;
? ? ? ? ? ? ? ? }else {
? ? ? ? ? ? ? ? ? ? break;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? ? ? array[j + 1] = tmp;
? ? ? ? }
? ? }

1.4 性能分析

時(shí)間復(fù)雜度(平均)	時(shí)間復(fù)雜度(最壞)	時(shí)間復(fù)雜度(最好)	空間復(fù)雜度	穩(wěn)定性
O(n^2)	O(n^2)	O(n)	O(1)	穩(wěn)定

插入排序，初始數(shù)據(jù)越接近有序，時(shí)間效率越高。

2.希爾排序

2.1 原理

希爾排序法又稱縮小增量法。希爾排序法的基本思想是：先選定一個(gè)整數(shù)gap，把待排序文件中所有記錄分成個(gè)gap組，所有距離為gap的記錄分在同一組內(nèi)，并對(duì)每一組內(nèi)的記錄進(jìn)行排序。然后，取gap = (gap/3)+1，重復(fù)上述分組和排序的工作。當(dāng)?shù)竭_(dá)gap=1時(shí)，所有記錄在統(tǒng)一組內(nèi)排好序。

希爾排序是對(duì)直接插入排序的優(yōu)化。
當(dāng)gap > 1時(shí)都是預(yù)排序，目的是讓數(shù)組更接近于有序。當(dāng)gap == 1時(shí)，數(shù)組已經(jīng)接近有序的了，這樣就會(huì)很快。這樣整體而言，可以達(dá)到優(yōu)化的效果。我們實(shí)現(xiàn)后可以進(jìn)行性能測(cè)試的對(duì)比。

2.2 動(dòng)圖演示

2.3 代碼實(shí)現(xiàn)

? ? /**
? ? ?*
? ? ? * @param array 排序的數(shù)組
? ? ?* @param gap 每組的間隔 -> 數(shù)組
? ? ?*/
? ? ?public static void shell(int[] array,int gap){
? ? ? ? ?for (int i = gap; i < array.length ; i++) {
? ? ? ? ? ? ?int tmp = array[i];
? ? ? ? ? ? ?int j = i - gap;
? ? ? ? ? ? ?while(j>=0){
? ? ? ? ? ? ? ? ?if(array[j] > tmp){
? ? ? ? ? ? ? ? ? ? ?array[j + gap] = array[j];
? ? ? ? ? ? ? ? ? ? ?j -= gap;
? ? ? ? ? ? ? ? ?}else {
? ? ? ? ? ? ? ? ? ? ?break;
? ? ? ? ? ? ? ? ?}
? ? ? ? ? ? ?}
? ? ? ? ? ? ?array[j + gap] = tmp;
? ? ? ? ?}
? ? ?}

? ? ?public static void shellSort(int[] array){
? ? ? ? ?int gap = array.length;
? ? ? ? ?while (gap > 1){
? ? ? ? ? ? ?gap = (gap / 3) + 1;// +1 保證最后一個(gè)序列是 1 (除幾都行)
? ? ? ? ? ? ?shell(array,gap);
? ? ? ? ?}
? ? ?}

2.4 性能分析

時(shí)間復(fù)雜度(平均)	時(shí)間復(fù)雜度(最壞)	時(shí)間復(fù)雜度(最好)	空間復(fù)雜度	穩(wěn)定性
O(n^1.3)	O(n^2)	O(n)	O(1)	不穩(wěn)定

3.直接選擇排序

3.1 動(dòng)圖演示

3.2 代碼實(shí)現(xiàn)

?/**
? ? ?* 時(shí)間復(fù)雜度:
? ? ?* ? ? ?最好: O(n^2)
? ? ?* ? ? ?最壞: O(n^2)
? ? ?* 空間復(fù)雜度: O(1)
? ? ?* 穩(wěn)定性: 不穩(wěn)定
? ? ?* @param array
? ? ?*/
? ? public static void selectSort(int[] array){
? ? ? ? for (int i = 0; i < array.length - 1; i++) {
? ? ? ? ? ? for (int j = i + 1; j <array.length ; j++) {
? ? ? ? ? ? ? ? if(array[j] < array[i]){
? ? ? ? ? ? ? ? ? ? int tmp = array[i];
? ? ? ? ? ? ? ? ? ? array[i] = array[j];
? ? ? ? ? ? ? ? ? ? array[j] = tmp;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
? ? }

3.3 性能分析

時(shí)間復(fù)雜度(平均)	時(shí)間復(fù)雜度(最壞)	時(shí)間復(fù)雜度(最好)	空間復(fù)雜度	穩(wěn)定性
O(n^2)	O(n^2)	O(n^2)	O(1)	不穩(wěn)定

4.堆排序

4.1 動(dòng)圖演示

4.2 代碼實(shí)現(xiàn)

? ? public static void siftDown(int[] array,int root, int len){
? ? ? ? int parent = root;
? ? ? ? int child = root * 2 + 1;
? ? ? ? while (child < len){
? ? ? ? ? ? if( child+1 < len && array[child] < array[child+1] ){
? ? ? ? ? ? ? ? child++;
? ? ? ? ? ? }
? ? ? ? ? ? //這里child下標(biāo)就是左右孩子的最大值的下標(biāo)
? ? ? ? ? ? if(array[child] > array[parent]){
? ? ? ? ? ? ? ? int tmp = array[child];
? ? ? ? ? ? ? ? array[child] = array[parent];
? ? ? ? ? ? ? ? array[parent] = tmp;
? ? ? ? ? ? ? ? parent = child;
? ? ? ? ? ? ? ? child = parent * 2 + 1;
? ? ? ? ? ? }else {
? ? ? ? ? ? ? ? break;
? ? ? ? ? ? }
? ? ? ? }
? ? }

? ? public static void createHeap(int[] array){
? ? ? ? for (int i = (array.length - 1 - 1) / 2; i >= 0; i++) {
? ? ? ? ? ? siftDown(array,i,array.length);
? ? ? ? }
? ? }
? ? public static void heapSort(int[] array){
? ? ? ? createHeap(array);
? ? ? ? int end = array.length - 1;
? ? ? ? while (end > 0){
? ? ? ? ? ? int tmp = array[end];
? ? ? ? ? ? array[end] = array[0];
? ? ? ? ? ? array[0] =tmp;
? ? ? ? ? ? siftDown(array,0,end);
? ? ? ? ? ? end--;
? ? ? ? }
? ? }

4.3 性能分析

時(shí)間復(fù)雜度(平均)	時(shí)間復(fù)雜度(最壞)	時(shí)間復(fù)雜度(最好)	空間復(fù)雜度	穩(wěn)定性
O(n * log(n))	O(n * log(n))	O(n * log(n))	O(1)	不穩(wěn)定

5.冒泡排序

5.1 動(dòng)圖演示

5.2 代碼實(shí)現(xiàn)

public static void BubbleSort(int[] array){
? ? ? ? for (int i = 0; i < array.length - 1; i++) {
? ? ? ? ? ? boolean flg = false;
? ? ? ? ? ? for (int j = 0; j < array.length - 1 - i ; j++) {
? ? ? ? ? ? ? ? if(array[j+1] < array[j]){
? ? ? ? ? ? ? ? ? ? int tmp = array[j];
? ? ? ? ? ? ? ? ? ? array[j] = array[j+1];
? ? ? ? ? ? ? ? ? ? array[j+1] = tmp;
? ? ? ? ? ? ? ? ? ? flg = true;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? ? ? if(!flg){
? ? ? ? ? ? ? ? break;
? ? ? ? ? ? }
? ? ? ? }
? ? }

5.3 性能分析

時(shí)間復(fù)雜度(平均)	時(shí)間復(fù)雜度(最壞)	時(shí)間復(fù)雜度(最好)	空間復(fù)雜度	穩(wěn)定性
O(n^2)	O(n^2)	O(n)	O(1)	穩(wěn)定

6.快速排序

6.1 原理

從待排序區(qū)間選擇一個(gè)數(shù)，作為基準(zhǔn)值(pivot)；
Partition: 遍歷整個(gè)待排序區(qū)間，將比基準(zhǔn)值小的（可以包含相等的）放到基準(zhǔn)值的左邊，將比基準(zhǔn)值大的（可以包含相等的）放到基準(zhǔn)值的右邊；
采用分治思想，對(duì)左右兩個(gè)小區(qū)間按照同樣的方式處理，直到小區(qū)間的長(zhǎng)度 == 1，代表已經(jīng)有序，或者小區(qū)間的長(zhǎng)度 == 0，代表沒有數(shù)據(jù)。

6.2 動(dòng)圖演示

6.3 實(shí)現(xiàn)方法

6.3.1 Hoare法

6.3.2 挖坑法

6.4 代碼實(shí)現(xiàn)

? //Hoare法
? ? public static void swap(int[] array,int i,int j){
? ? ? ? int tmp = array[i];
? ? ? ? array[i] = array[j];
? ? ? ? array[j] = tmp;
? ? }
? ? public static int partition1(int[] array,int low,int high) {
? ? ? ? int i = low;
? ? ? ? int tmp = array[low];
? ? ? ? while (low < high){
? ? ? ? ? ? while (low < high && array[high] >= tmp){
? ? ? ? ? ? ? ? high--;
? ? ? ? ? ? }
? ? ? ? ? ? while (low < high && array[low] <= tmp){
? ? ? ? ? ? ? ? low++;
? ? ? ? ? ? }
? ? ? ? ? ? swap(array,low,high);
? ? ? ? }
? ? ? ? swap(array,i,low);
? ? ? ? return low;
? ? }

? ? //挖坑法
? ? public static int partition2(int[] array,int low,int high) {
? ? ? ? int tmp = array[low];

? ? ? ? while (low < high){
? ? ? ? ? ? while (low < high && array[high] >= tmp){
? ? ? ? ? ? ? ? high--;
? ? ? ? ? ? }
? ? ? ? ? ? array[low] = array[high];
? ? ? ? ? ? while (low < high && array[low] <= tmp){
? ? ? ? ? ? ? ? low++;
? ? ? ? ? ? }
? ? ? ? ? ? array[high] = array[low];
? ? ? ? }
? ? ? ? array[low] = tmp;
? ? ? ? return low;
? ? }

? ? public static void quick(int[] array,int start,int end){
? ? ? ? if(start >= end) return;
? ? ? ? int pivot = partition1(array,start,end);

? ? ? ? quick(array,start,pivot-1);

? ? ? ? quick(array,pivot+1,end);
? ? }
? ? public static void quickSort(int[] array){
? ? ? ? quick(array,0,array.length-1);
? ? }

6.5 快排優(yōu)化

6.5.1 三數(shù)取中法

? ?public static void swap(int[] array,int i,int j){
? ? ? ? int tmp = array[i];
? ? ? ? array[i] = array[j];
? ? ? ? array[j] = tmp;
? ? }
? ? ? ? public static int partition2(int[] array,int low,int high) {
? ? ? ? int tmp = array[low];

? ? ? ? while (low < high){
? ? ? ? ? ? while (low < high && array[high] >= tmp){
? ? ? ? ? ? ? ? high--;
? ? ? ? ? ? }
? ? ? ? ? ? array[low] = array[high];
? ? ? ? ? ? while (low < high && array[low] <= tmp){
? ? ? ? ? ? ? ? low++;
? ? ? ? ? ? }
? ? ? ? ? ? array[high] = array[low];
? ? ? ? }
? ? ? ? array[low] = tmp;
? ? ? ? return low;
? ? }
? ? public static void selectPivotMedianOFThree(int[] array,int start,int end,int mid){
? ? ? ? if(array[mid] > array[start]){
? ? ? ? ? ? swap(array,start,mid);
? ? ? ? }//此時(shí)mid下標(biāo)的值肯定小于start下標(biāo)的值 array[mid] <= array[start]
? ? ? ? if(array[mid] > array[end]){
? ? ? ? ? ? swap(array,mid,end);
? ? ? ? }//此時(shí)mid下標(biāo)的值肯定小于end下標(biāo)的值 array[mid] <= array[end]
? ? ? ? if(array[start] > array[end]){
? ? ? ? ? ? swap(array,start,end);
? ? ? ? }//此時(shí)有 array[mid] <= array[start] <= array[end]
? ? }

? ? public static void quick1(int[] array,int start,int end){
? ? ? ? if(start >= end) return;
? ? ? ? int mid = (start + end) / 2;
? ? ? ? selectPivotMedianOFThree(array,start,end,mid);

? ? ? ? int pivot = partition2(array,start,end);

? ? ? ? quick1(array,start,pivot-1);

? ? ? ? quick1(array,pivot+1,end);
? ? }

? ? public static void quick1Sort(int[] array){
? ? ? ? quick1(array,0,array.length - 1);
? ? }

6.5.2 加上直接插入排序

?? ?public static void swap(int[] array,int i,int j){
? ? ? ? int tmp = array[i];
? ? ? ? array[i] = array[j];
? ? ? ? array[j] = tmp;
? ? }
? ? public static void insertSort2(int[] array,int start,int end){
? ? ? ? for (int i = start + 1; i <= end; i++) {
? ? ? ? ? ? int j = i + 1;
? ? ? ? ? ? int tmp = array[i];
? ? ? ? ? ? while (j >= 0){
? ? ? ? ? ? ? ? if(array[j] > tmp){
? ? ? ? ? ? ? ? ? ? array[j+1] = array[j];
? ? ? ? ? ? ? ? }else {
? ? ? ? ? ? ? ? ? ? break;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? ? ? array[j+1] = tmp;
? ? ? ? }
? ? }
? ? ? ? public static int partition2(int[] array,int low,int high) {
? ? ? ? int tmp = array[low];

? ? ? ? while (low < high){
? ? ? ? ? ? while (low < high && array[high] >= tmp){
? ? ? ? ? ? ? ? high--;
? ? ? ? ? ? }
? ? ? ? ? ? array[low] = array[high];
? ? ? ? ? ? while (low < high && array[low] <= tmp){
? ? ? ? ? ? ? ? low++;
? ? ? ? ? ? }
? ? ? ? ? ? array[high] = array[low];
? ? ? ? }
? ? ? ? array[low] = tmp;
? ? ? ? return low;
? ? }
? ? ? ? public static void selectPivotMedianOFThree(int[] array,int start,int end,int mid){
? ? ? ? if(array[mid] > array[start]){
? ? ? ? ? ? swap(array,start,mid);
? ? ? ? }//此時(shí)mid下標(biāo)的值肯定小于start下標(biāo)的值 array[mid] <= array[start]
? ? ? ? if(array[mid] > array[end]){
? ? ? ? ? ? swap(array,mid,end);
? ? ? ? }//此時(shí)mid下標(biāo)的值肯定小于end下標(biāo)的值 array[mid] <= array[end]
? ? ? ? if(array[start] > array[end]){
? ? ? ? ? ? swap(array,start,end);
? ? ? ? }//此時(shí)有 array[mid] <= array[start] <= array[end]
? ? }

? ? public static void quick2(int[] array,int start,int end){
? ? ? ? if(start >= end) return;
? ? ? ? if(end - start + 1 <= 100){
? ? ? ? ? ? insertSort2(array,start,end);
? ? ? ? ? ? return;
? ? ? ? }
? ? ? ? int mid = (start + end)/2;
? ? ? ? selectPivotMedianOFThree(array,start,end,mid);

? ? ? ? int pivot = partition2(array,start,end);
? ? ? ? quick2(array,start,pivot-1);
? ? ? ? quick2(array,pivot+1,end);
? ? } ? ?
? ? public static void quick2Sort(int[] array){
? ? ? ? quick2(array,0,array.length - 1);
? ? }

6.6 非遞歸的實(shí)現(xiàn)

6.6.1 非遞歸思路

首先調(diào)用partition,找到pivot
然后把pivot的左區(qū)間和右區(qū)間的下標(biāo)放到棧立馬
判斷棧是否為空,不為空,彈出棧頂?shù)?個(gè)元素(注意:入棧的順序決定了出棧的順序中的第一個(gè)元素是high的還是low的)
然后再進(jìn)行調(diào)用partition,找pivot,
重復(fù)以上操作.

6.6.2 非遞歸代碼實(shí)現(xiàn)

? public static void quickSort4(int[] array){
? ? ? ? Stack<Integer> stack = new Stack<>();
? ? ? ? int low = 0;
? ? ? ? int high = array.length - 1;

? ? ? ? int pivot = partition2(array,low ,high);
? ? ? ? //左邊有2個(gè)元素即以上
? ? ? ? if(pivot > low + 1){
? ? ? ? ? ? stack.push(0);
? ? ? ? ? ? stack.push(pivot - 1);
? ? ? ? }
? ? ? ? //右邊有2個(gè)元素即以上
? ? ? ? if(pivot < high - 1){
? ? ? ? ? ? stack.push(pivot + 1);
? ? ? ? ? ? stack.push(high);
? ? ? ? }
? ? ? ? while (!stack.isEmpty()){
? ? ? ? ? ? high = stack.pop();
? ? ? ? ? ? low = stack.pop();
? ? ? ? ? ? pivot = partition2(array,low,high);
? ? ? ? ? ? //左邊有2個(gè)元素即以上
? ? ? ? ? ? if(pivot > low + 1){
? ? ? ? ? ? ? ? stack.push(0);
? ? ? ? ? ? ? ? stack.push(pivot - 1);
? ? ? ? ? ? }
? ? ? ? ? ? //右邊有2個(gè)元素即以上
? ? ? ? ? ? if(pivot < high - 1){
? ? ? ? ? ? ? ? stack.push(pivot + 1);
? ? ? ? ? ? ? ? stack.push(high);
? ? ? ? ? ? }
? ? ? ? }
? ? }

6.7 性能分析

時(shí)間復(fù)雜度(平均)	時(shí)間復(fù)雜度(最壞)	時(shí)間復(fù)雜度(最好)	空間復(fù)雜度	穩(wěn)定性
O(n * log(n))	O(n^2)	O(n * log(n))	O(log(n))~O(n)	不穩(wěn)定

7.歸并排序

7.1 原理

歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序的序列；即先使每個(gè)子序列有序，再使子序列段間有序。若將兩個(gè)有序表合并成一個(gè)有序表，稱為二路歸并。

7.2 動(dòng)圖演示

7.3 代碼實(shí)現(xiàn)—遞歸

? ? public static void merge(int[] array,int low ,int high ,int mid){
? ? ? ? int s1 = low;
? ? ? ? int e1 = mid;
? ? ? ? int s2 = mid+1;
? ? ? ? int e2 = high;

? ? ? ? int[] tmp = new int[high - low + 1];
? ? ? ? int k = 0;

? ? ? ? while (s1 <= e1 && s2 <= e2){
? ? ? ? ? ? if(array[s1] <= array[s2]){
? ? ? ? ? ? ? ? tmp[k++] = array[s1++];
? ? ? ? ? ? }else {
? ? ? ? ? ? ? ? tmp[k++] = array[s2++];
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? while (s1 <= e1){
? ? ? ? ? ? tmp[k++] = array[s1++];
? ? ? ? }
? ? ? ? while (s2 <= e2){
? ? ? ? ? ? tmp[k++] = array[s2++];
? ? ? ? }

? ? ? ? for (int i = 0; i < tmp.length; i++) {
? ? ? ? ? ? array[i+low] = tmp[i];
? ? ? ? }
? ? }
? ? public static void mergeSortInternal(int[] array,int low ,int high){
? ? ? ? if(low >= high) return;
? ? ? ? int mid = (low + high) / 2;
? ? ? ? mergeSortInternal(array,low,mid);
? ? ? ? mergeSortInternal(array,mid+1,high);

? ? ? ? merge(array,low,high,mid);
? ? }

? ? public static void mergeSort(int[] array){
? ? ? ? mergeSortInternal(array,0,array.length - 1);
? ? }

7.4 代碼實(shí)現(xiàn)—非遞歸

? ? public static void merge1(int[] array,int gap){
? ? ? ? int[] tmp = new int[array.length];
? ? ? ? int k = 0;

? ? ? ? int s1 = 0;
? ? ? ? int e1 = s1 + gap - 1;

? ? ? ? int s2 = e1 + 1;
? ? ? ? int e2 = s2 + gap - 1 > array.length ? array.length - 1 : s2 + gap - 1;

? ? ? ? while (s2 < array.length){
? ? ? ? ? ? while (s1 <= e1 && s2 <= e2){
? ? ? ? ? ? ? ? if(array[s1] <= array[s2]){
? ? ? ? ? ? ? ? ? ? tmp[k++] = array[s1++];
? ? ? ? ? ? ? ? }else {
? ? ? ? ? ? ? ? ? ? tmp[k++] = array[s2++];
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? ? ? while (s1 <= e1){
? ? ? ? ? ? ? ? tmp[k++] = array[s1++];
? ? ? ? ? ? }
? ? ? ? ? ? while (s2 <= e2){
? ? ? ? ? ? ? ? tmp[k++] = array[s2++];
? ? ? ? ? ? }

? ? ? ? ? ? s1 = e2 + 1;
? ? ? ? ? ? e1 = s1 + gap - 1;

? ? ? ? ? ? s2 = e1 + 1;
? ? ? ? ? ? e2 = s2 + gap - 1 > array.length ? array.length - 1 : s2 + gap - 1;
? ? ? ? }

? ? ? ? while (s1 <= array.length - 1){
? ? ? ? ? ? tmp[k++] = array[s1++];
? ? ? ? }

? ? ? ? for (int i = 0; i < tmp.length; i++) {
? ? ? ? ? ? array[i] = tmp[i];
? ? ? ? }
? ? }


? ? public static void mergeSort1(int[] array){
? ? ? ? for (int i = 1; i < array.length; i*=2) {
? ? ? ? ? ? merge1(array,i);
? ? ? ? }
? ? }

7.5 性能分析

時(shí)間復(fù)雜度(平均)	時(shí)間復(fù)雜度(最壞)	時(shí)間復(fù)雜度(最好)	空間復(fù)雜度	穩(wěn)定性
O(n * log(n))	O(n * log(n))	O(n * log(n))	O(n)	穩(wěn)定

8.計(jì)數(shù)排序

當(dāng)輸入的元素是 n 個(gè) 0 到 k 之間的整數(shù)時(shí)，它的運(yùn)行時(shí)間是 O(n + k)。計(jì)數(shù)排序不是比較排序，排序的速度快于任何比較排序算法。

8.1 算法的步驟

（1）找出待排序的數(shù)組中最大和最小的元素
（2）統(tǒng)計(jì)數(shù)組中每個(gè)值為i的元素出現(xiàn)的次數(shù)，存入數(shù)組C的第i項(xiàng)
（3）對(duì)所有的計(jì)數(shù)累加（從C中的第一個(gè)元素開始，每一項(xiàng)和前一項(xiàng)相加）
（4）反向填充目標(biāo)數(shù)組：將每個(gè)元素i放在新數(shù)組的第C(i)項(xiàng)，每放一個(gè)元素就將C(i)減去1

8.2 動(dòng)圖演示

8.3 代碼實(shí)現(xiàn)

? ? public static void CountingSort(int[] array){
? ? ? ? int maxValue = GetMaxValue(array);
? ? ? ? int bucketLen = maxValue + 1;
? ? ? ? int[] bucket = new int[bucketLen];
? ? ? ? for (int value:array) {
? ? ? ? ? ? bucket[value]++;
? ? ? ? }
? ? ? ? int index = 0 ;

? ? ? ? for (int i = 0; i < bucketLen; i++) {
? ? ? ? ? ? while(bucket[i] > 0){
? ? ? ? ? ? ? ? array[index++] = i;
? ? ? ? ? ? ? ? bucket[i]--;
? ? ? ? ? ? }
? ? ? ? }
? ? }

? ? public static int GetMaxValue(int[] array){
? ? ? ? int maxValue = array[0];
? ? ? ? for (int i = 0; i < array.length; i++) {
? ? ? ? ? ? if(maxValue < array[i]){
? ? ? ? ? ? ? ? maxValue = array[i];
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return maxValue;
? ? }

8.4 性能分析

時(shí)間復(fù)雜度(平均)	時(shí)間復(fù)雜度(最壞)	時(shí)間復(fù)雜度(最好)	空間復(fù)雜度	穩(wěn)定性
O(n+k)	O(n+k)	O(n+k)	O(k)	穩(wěn)定

9.桶排序

9.1 原理

桶排序是計(jì)數(shù)排序的升級(jí)版。它利用了函數(shù)的映射關(guān)系，高效與否的關(guān)鍵就在于這個(gè)映射函數(shù)的確定。桶排序 (Bucket sort)的工作的原理：假設(shè)輸入數(shù)據(jù)服從均勻分布，將數(shù)據(jù)分到有限數(shù)量的桶里，每個(gè)桶再分別排序（有可能再使用別的排序算法或是以遞歸方式繼續(xù)使用桶排序進(jìn)行排）。

為了使桶排序更加高效，我們需要做到這兩點(diǎn)：

在額外空間充足的情況下，盡量增大桶的數(shù)量
使用的映射函數(shù)能夠?qū)⑤斎氲?N 個(gè)數(shù)據(jù)均勻的分配到 K 個(gè)桶中

同時(shí)，對(duì)于桶中元素的排序，選擇何種比較排序算法對(duì)于性能的影響至關(guān)重要。

9.2 算法的步驟

設(shè)置一個(gè)定量的數(shù)組當(dāng)作空桶；
遍歷輸入數(shù)據(jù)，并且把數(shù)據(jù)一個(gè)一個(gè)放到對(duì)應(yīng)的桶里去；
對(duì)每個(gè)不是空的桶進(jìn)行排序；
從不是空的桶里把排好序的數(shù)據(jù)拼接起來。

9.3 畫圖解析

9.4 代碼實(shí)現(xiàn)

?public static void bucketSort(int[] arr) {
? ? ? ? if (arr.length == 0) {
? ? ? ? ? ? return;
? ? ? ? }

? ? ? ? int minValue = arr[0];
? ? ? ? int maxValue = arr[0];
? ? ? ? for (int value : arr) {
? ? ? ? ? ? if (value < minValue) {
? ? ? ? ? ? ? ? minValue = value;
? ? ? ? ? ? } else if (value > maxValue) {
? ? ? ? ? ? ? ? maxValue = value;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? //得到最大和最小元素

? ? ? ? int bucketNum = (maxValue - minValue) / arr.length + 1;//桶的數(shù)量
? ? ? ? ArrayList<ArrayList<Integer>> bucket = new ArrayList<>(bucketNum);
? ? ? ? for (int i = 0; i < bucketNum; i++) {
? ? ? ? ? ? bucket.add(new ArrayList<>());
? ? ? ? }
? ? ? ??
? ? ? ? //將元素放入到桶中
? ? ? ? for (int i = 0; i < arr.length; i++) {
? ? ? ? ? ? int num = (arr[i] - minValue) / arr.length;
? ? ? ? ? ? bucket.get(num).add(arr[i]);
? ? ? ? }

? ? ? ? for (int i = 0; i < bucket.size(); i++) {
? ? ? ? ? ? //這里是比較,可以選擇其他的方式實(shí)現(xiàn),這里為了演示采取Collection的sort
? ? ? ? ? ? Collections.sort(bucket.get(i));
? ? ? ? }

? ? ? ? // 將桶中的元素賦值到原序列
? ? ? ? int index = 0;
? ? ? ? for(int i = 0; i < bucket.size(); i++){
? ? ? ? ? ? for(int j = 0; j < bucket.get(i).size(); j++){
? ? ? ? ? ? ? ? arr[index++] = bucket.get(i).get(j);
? ? ? ? ? ? }
? ? ? ? }
? ? }

9.5 性能分析

時(shí)間復(fù)雜度(平均)	時(shí)間復(fù)雜度(最壞)	時(shí)間復(fù)雜度(最好)	空間復(fù)雜度	穩(wěn)定性
O(n+k)	O(n^2)	O(n+k)	O(n+k)	穩(wěn)定

10.基數(shù)排序

10.1 算法的步驟

取得數(shù)組中的最大數(shù)，并取得位數(shù)；
arr為原始數(shù)組，從最低位開始取每個(gè)位組成radix數(shù)組；
對(duì)radix進(jìn)行計(jì)數(shù)排序（利用計(jì)數(shù)排序適用于小范圍數(shù)的特點(diǎn)）

10.2 動(dòng)圖演示

10.3 代碼實(shí)現(xiàn)

? ? public static int getNumLength(int num){
? ? ? ? if(num == 0) return 1;
? ? ? ? int count = 0;
? ? ? ? for (int i = num; i != 0; i /= 10) {
? ? ? ? ? ? count++;
? ? ? ? }
? ? ? ? return count;
? ? }
? ? public static void RadixSort(int[] array){
? ? ? ? int maxValue = array[0];
? ? ? ? for (int i = 0; i < array.length; i++) {
? ? ? ? ? ? if(maxValue < array[i]){
? ? ? ? ? ? ? ? maxValue = array[i];
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? int maxDigit = getNumLength(maxValue);

? ? ? ? int mod = 10;
? ? ? ? int dev = 1;
? ? ? ? for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
? ? ? ? ? ? int[][] counter = new int[mod * 2][0];

? ? ? ? ? ? for (int j = 0; j < array.length; j++) {
? ? ? ? ? ? ? ? int bucket = ((array[j] % mod) / dev) + mod;
? ? ? ? ? ? ? ? counter[bucket] = arrayAppend(counter[bucket], array[j]);
? ? ? ? ? ? }

? ? ? ? ? ? int pos = 0;
? ? ? ? ? ? for (int[] bucket : counter) {
? ? ? ? ? ? ? ? for (int value : bucket) {
? ? ? ? ? ? ? ? ? ? array[pos++] = value;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }

? ? }
? ? public static int[] arrayAppend(int[] arr, int value) {
? ? ? ? arr = Arrays.copyOf(arr, arr.length + 1);
? ? ? ? arr[arr.length - 1] = value;
? ? ? ? return arr;
? ? }

10.4 性能分析

時(shí)間復(fù)雜度(平均)	時(shí)間復(fù)雜度(最壞)	時(shí)間復(fù)雜度(最好)	空間復(fù)雜度	穩(wěn)定性
O(n*k)	O(n*2)	O(n*k)	O(n+k)	穩(wěn)定

總結(jié)：

到此這篇關(guān)于 Java數(shù)據(jù)結(jié)構(gòu)的十大排序的文章就介紹到這了,更多相關(guān) Java數(shù)據(jù)結(jié)構(gòu)十大排序內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: