?學數據結構之前 必看_嗶哩嗶哩_bilibili

1.認識復雜度和簡單排序算法_嗶哩嗶哩_bilibili

桶排序（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-10000buckets.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