排序算法之桶排序及Java实现

喜欢ヅ旅行 2022-05-26 04:57 174阅读 0赞

## 一、排序算法的分类 ##

1.  选择排序（[直接选择排序][Link 1]，[堆排序][Link 2]）
2.  交换排序（[冒泡排序][Link 3]，[快速排序][Link 4]）
3.  插入排序（[直接插入排序][Link 5]，[希尔排序][Link 6]）
4.  [归并排序][Link 7]
5.  桶式排序
6.  基数排序

## 二、桶排序的原理 ##

之前介绍的算法都是非线性时间比较类排序，而桶排序是一种线性时间非比较类的排序算法，它是常见排序算法中最快的一种，但是也同时非常耗费空间，是典型的空间换时间的排序算法。桶排序的原理是申请一个数组空间，遍历待排序数组时，将待排序数组的值放在数组空间的索引位置上，例如待排序数组为\[4,2,3,4\]，新申请的数组空间为a\[4\]，则a\[2\]的值为1，a\[3\]的值为1，a\[4\]的值为2，其他索引处的值为0，这样当遍历a时，将数组中非0值的索引按数量打印出来，就得到了从小到大的序列。

## 三、桶排序的实现 ##

public class BucketSort {
        public static void bucSort(int[] arr, int min, int max){
            int[] temp = new int[max-min+1];
            for(int i=0; i<arr.length; i++){
                temp[arr[i]-min]++;
            }
    
            for(int j=0; j<temp.length; j++){
                if(temp[j]!=0){
                    for(int k=0; k<temp[j]; k++)
                    System.out.print(j + min + " ");
                }
            }
    
        }
        public static void main(String args[]){
            int[] test = {
       2,3,5,4,3,2,-2};
            bucSort(test,-2,5);
        }
    
    }

测试结果

-2 2 2 3 3 4 5

[Link 1]: https://blog.csdn.net/xdzhouxin/article/details/80017538
[Link 2]: https://blog.csdn.net/xdzhouxin/article/details/80079195
[Link 3]: https://blog.csdn.net/xdzhouxin/article/details/80017719
[Link 4]: https://blog.csdn.net/xdzhouxin/article/details/80031668
[Link 5]: https://blog.csdn.net/xdzhouxin/article/details/80024190
[Link 6]: https://blog.csdn.net/xdzhouxin/article/details/80070031
[Link 7]: https://blog.csdn.net/xdzhouxin/article/details/80070839