桶排序（Bucket sort）------时间复杂度为O(n)的排序方法（一）_多桶排序时间复杂度-CSDN博客
桶排序
测试场景：数组中有10000个随机数，范围在(0-100000)
使用100个桶，每个桶存放的数据范围为：0-999, 1000-1999, 2000-2999，依次类推
public class BucketSort { public static void bucketSort(int[] data){ //新建100个桶 int bucketSize = 100; ArrayList<ArrayList<Integer>> buckets = new ArrayList<>(bucketSize); for (int i = 0; i < bucketSize; i++) { buckets.add(new ArrayList<>()); //0-99 } //遍历数据，将数据放到桶中 for (int i : data) { //0-10000 buckets.get(i / 1000).add(i); } //在桶内部进行排序 int k = 0; for (int i = 0; i < bucketSize; i++) { ArrayList<Integer> list = buckets.get(i); Integer[] num = list.toArray(new Integer[1]); Arrays.sort(num); //拷贝到data中 for (int n : num) { data[k++] = n; } } } public static void main(String[] args) { Random random = new Random(); int[] data = new int[10000]; for (int i = 0; i < data.length; i++) { data[i] = random.nextInt(100000); } BucketSort.bucketSort(data); System.out.println(Arrays.toString(data)); } }
数据结构分类
时间复杂度
对于有n个元素的数组。
选择排序：
循环一次进行n次比较，找出一个最小值。
再循环一次进行n-1次比较找出次小值。
。。。
这样的循环有n次，每轮循环进行n次，n-1次。。。1次比较
时间复杂度计算:
循环复杂度：n+n-1+n-2+...+1
比较复杂度：n+n-1+n-2+...+1
合计为一个等差数列 an^2+bn+C
用极限的思维，时间复杂度考虑最坏情况，只看最高项。时间复杂度为o(n^2)
冒泡排序：
假设排序规则为升序
从左往右进行一次循环，相邻两个数进行比较交换位置。进行了n-1次比较。第一次循环肯定确定了最右边一个元素。
再循环一次进行n-2次确定次右边一个元素。
。。。
这样的循环有n次，每轮循环进行n-1次，n-2次。。。1次比较
时间复杂度计算:
循环复杂度：n-1+n-2+...+1
比较复杂度：n-1+n-2+...+1
合计为一个等差数列 an^2+bn+C
用极限的思维，时间复杂度考虑最坏情况，只看最高项。时间复杂度为o(n^2)
异或运算 无进位相加
两数交换值
异或运算相比用直接相加的方式来说是没有用到第三个临时参数来储存值，并且位运算是直接操作内存地址，比加减乘除都要快。
前提条件是a，b不能是同一个内存地址，而不是说a,b值相等就不能进行位运算相加。因为a，b同内存的话，操作a或者b同时改变了两者的值都归零了。
int a,b;
a = a^b
b = a^b
a = a^b
