?Java數(shù)據(jù)結(jié)構(gòu)的十大排序
更新時(shí)間：2022年01月26日 15:38:26 作者：wwzzzzzzzzzzzzz?
這篇文章主要介紹了?Java數(shù)據(jù)結(jié)構(gòu)的十大排序，排序算法分為比較類排序和非比較類排序，具體的內(nèi)容，需要的朋友參考下面思維導(dǎo)圖及文章介紹，希望對你有所幫助
1.直接插入排序
1.1 動圖演示
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)，并對每一組內(nèi)的記錄進(jìn)行排序。然后，取gap = (gap/3)+1，重復(fù)上述分組和排序的工作。當(dāng)?shù)竭_(dá)gap=1時(shí)，所有記錄在統(tǒng)一組內(nèi)排好序。
- 希爾排序是對直接插入排序的優(yōu)化。
- 當(dāng)gap > 1時(shí)都是預(yù)排序，目的是讓數(shù)組更接近于有序。當(dāng)gap == 1時(shí)，數(shù)組已經(jīng)接近有序的了，這樣就會很快。這樣整體而言，可以達(dá)到優(yōu)化的效果。我們實(shí)現(xiàn)后可以進(jìn)行性能測試的對比。
2.2 動圖演示
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 動圖演示
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 動圖演示
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 動圖演示
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)值的右邊；
- 采用分治思想，對左右兩個(gè)小區(qū)間按照同樣的方式處理，直到小區(qū)間的長度 == 1，代表已經(jīng)有序，或者小區(qū)間的長度 == 0，代表沒有數(shù)據(jù)。
6.2 動圖演示
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 動圖演示
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）對所有的計(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 動圖演示
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ù)排序的升級版。它利用了函數(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í)，對于桶中元素的排序，選擇何種比較排序算法對于性能的影響至關(guān)重要。
9.2 算法的步驟
- 設(shè)置一個(gè)定量的數(shù)組當(dāng)作空桶；
- 遍歷輸入數(shù)據(jù)，并且把數(shù)據(jù)一個(gè)一個(gè)放到對應(yīng)的桶里去；
- 對每個(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ù)組；
- 對radix進(jìn)行計(jì)數(shù)排序（利用計(jì)數(shù)排序適用于小范圍數(shù)的特點(diǎn)）
10.2 動圖演示
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)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
您可能感興趣的文章:
- Java數(shù)據(jù)結(jié)構(gòu)常見幾大排序梳理
- Java 數(shù)據(jù)結(jié)構(gòu)與算法系列精講之排序算法
- java 數(shù)據(jù)結(jié)構(gòu)與算法 (快速排序法)
- Java深入了解數(shù)據(jù)結(jié)構(gòu)中常見的排序算法
- Java數(shù)據(jù)結(jié)構(gòu)之二叉排序樹的實(shí)現(xiàn)
- 帶你了解Java數(shù)據(jù)結(jié)構(gòu)和算法之高級排序
- Java數(shù)據(jù)結(jié)構(gòu)和算法之冒泡,選擇和插入排序算法
- Java 數(shù)據(jù)結(jié)構(gòu)七大排序使用分析
相關(guān)文章
這篇文章主要介紹了Java中&與&&的區(qū)別及說明,具有很好的參考價(jià)值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2023-08-08
Java Volatile關(guān)鍵字實(shí)現(xiàn)原理過程解析
這篇文章主要介紹了Java Volatile關(guān)鍵字實(shí)現(xiàn)原理過程解析,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-03-03
Java8通過CompletableFuture實(shí)現(xiàn)異步回調(diào)
這篇文章主要介紹了Java8通過CompletableFuture實(shí)現(xiàn)異步回調(diào)，CompletableFuture是Java?8?中新增的一個(gè)類，它是對Future接口的擴(kuò)展，下文關(guān)于其更多相關(guān)詳細(xì)介紹需要的小伙伴可以參考一下2022-04-04
今天小編就為大家分享一篇Java Unsafe學(xué)習(xí)筆記，具有很好的參考價(jià)值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-11-11
面向?qū)ο竽耸荍ava語言的核心，是程序設(shè)計(jì)的思想。Java語言的面向?qū)ο蠹夹g(shù)包括了面向?qū)ο蠛兔嫦蜻^程的基本概念，面向?qū)ο蟮奶卣?，Java語言的類，對象，修飾符，抽象類等一系列的知識點(diǎn)2022-03-03
這篇文章主要介紹了JVM的垃圾回收算如何判斷對象是否可以被回收，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，,需要的朋友可以參考下2019-06-06
這篇文章主要介紹了java數(shù)組輸出的實(shí)例代碼，有需要的朋友可以參考一下2013-12-12
為什么在foreach循環(huán)中JAVA集合不能添加或刪除元素
今天給大家?guī)淼奈恼率顷P(guān)于Java的相關(guān)知識,文章圍繞著為什么在foreach循環(huán)中JAVA集合不能添加或刪除元素展開,文中有非常詳細(xì)的介紹及代碼示例,需要的朋友可以參考下2021-06-06
今天小編就為大家分享一篇關(guān)于Java五子棋AI實(shí)現(xiàn)代碼，小編覺得內(nèi)容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價(jià)值，需要的朋友一起跟隨小編來看看吧2019-02-02
SpringSecurity實(shí)現(xiàn)登陸認(rèn)證并返回token方式
這篇文章主要介紹了SpringSecurity實(shí)現(xiàn)登陸認(rèn)證并返回token方式,具有很好的參考價(jià)值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2024-03-03