排序算法

基礎(chǔ)排序，時(shí)間復(fù)雜度O(n2)

直接插入排序(穩(wěn)定)
冒泡排序(穩(wěn)定)
選擇排序(不穩(wěn)定)

進(jìn)階排序盛龄，時(shí)間復(fù)雜度O(nlogn)

快排(不穩(wěn)定)
歸并(穩(wěn)定)
堆排(不穩(wěn)定)

1. 直接插入排序(穩(wěn)定)：從i=1開始遍歷饰迹，提取nums[i]作為標(biāo)準(zhǔn)芳誓，排序[insertIndex,i-1]區(qū)間，排序完成之后啊鸭，將nums[i]插入到insertIndex+1位置

時(shí)間復(fù)雜度：O(n2)锹淌，最好On
空間復(fù)雜度：O(1)
穩(wěn)定：在排序后的序列后面插入，就算是相等赠制，相對(duì)位置沒有發(fā)生變化赂摆，穩(wěn)定
基本實(shí)現(xiàn)

    private static void insertSort(int[] nums) {
        //1. 判斷邊界條件
        if(nums.length < 2){
            return;
        }

        //2. 外層從左往右，內(nèi)層從i往左
        for(int i=1;i<nums.length;i++){
            //待排序元素
            int insertNum = nums[i];
            //insertIndex用于保存
            int insertIndex;
            //往前搜索钟些，以nums[i]為標(biāo)準(zhǔn)烟号，比numns[i]大才進(jìn)行循環(huán)，排序好[insertIndex,i-1]區(qū)間
            for(insertIndex = i-1;insertIndex>=0 && nums[insertIndex] > insertNum;insertIndex--){
                nums[insertIndex + 1] = nums[insertIndex];
            }
            //排序好之后厘唾，將insertNum插入到insertIndex+1
            nums[insertIndex+1] = insertNum;
        }
    }

2. 冒泡排序(穩(wěn)定)：j循環(huán)[0,nums.length-1-i]褥符，前后比較，如果前比后大抚垃，交換

時(shí)間復(fù)雜度：On2喷楣，最好On
空間復(fù)雜度：O(1)
穩(wěn)定：只是交換相鄰兩個(gè)元素，如果存在兩個(gè)相等的相鄰元素鹤树，不交換铣焊，相對(duì)位置沒有發(fā)生變化。因此是穩(wěn)定的
具體實(shí)現(xiàn)

    public void bubbleSort(int[] nums){
        if(nums.length < 2){
            return;
        }

        for(int i=0;i<nums.length-1;i++){
            for(int j=0;j<nums.length-1-i;j++){
                if(nums[j] > nums[j+1]){
                    swap(nums,j,j+1);
                }
            }
        }
    }

優(yōu)化實(shí)現(xiàn)(創(chuàng)建判斷標(biāo)志位flag罕伯，內(nèi)層循環(huán)如果發(fā)生交換曲伊，flag = false。外層循環(huán)完成一次后追他，進(jìn)行判斷flag坟募，如果flag為true，結(jié)束排序)

    public void bubbleSort(int[] nums){
        if(nums.length < 2){
            return;
        }

        for(int i=0;i<nums.length-1;i++){
            boolean flag = true;
            for(int j=0;j<nums.length-1-i;j++){
                if(nums[j] > nums[j+1]){
                    swap(nums,j,j+1);
                    flag = false;
                }
            }
            if(flag){
                break;
            }
        }
    }

3. 選擇排序(不穩(wěn)定)：提取當(dāng)前索引作為min邑狸，遍歷從[i+1,nums.length]找到比nums[min]小的值懈糯，提取它的索引。遍歷完成后单雾，如果min不等于i赚哗，交換i和min的值

時(shí)間復(fù)雜度；O(n2)
空間復(fù)雜度：O(1)
不穩(wěn)定：因?yàn)橐崛』鶞?zhǔn)值作為判斷標(biāo)準(zhǔn)硅堆，如果比基準(zhǔn)值小屿储，基準(zhǔn)值和j要進(jìn)行交換，相對(duì)位置可能會(huì)發(fā)生變化渐逃。如[5,8,5,2,10]

    private static void selectSort(int[] nums) {
        //1. 判斷
        if(nums.length < 2){
            return;
        }

        for(int i=0;i<nums.length;i++){
            int min = i;

            //往后搜
            for(int j=i+1;j<nums.length;j++){
                if(nums[j] < nums[min]){
                    min = j;
                }
            }

            if(min != i){
                swap(nums,i,min);
            }
        }
    }

4. 歸并排序(穩(wěn)定)：將數(shù)組分成兩半([0,middle]和[middle+1,len])

時(shí)間復(fù)雜度：
1. 平均O(nlogn)
2. 最好O(nlogn)
3. 最壞O(nlogn)
空間復(fù)雜度：O(n)
穩(wěn)定：相等元素在合并時(shí)并不會(huì)改變相對(duì)位置够掠。穩(wěn)定
具體實(shí)現(xiàn)：

    private static void MergeSort(int[] nums,int start,int end) {
        //1. 判斷越界
        if(start == end){
            return;
        }

        //2. 提取中點(diǎn)
        int middle = start + (end - start)/2;

        //3. 前一半排序
        MergeSort(nums,start,middle);

        //4. 后一半排序
        MergeSort(nums,middle+1,end);

        //5. 合并
        Merge(nums,start,middle,end);
    }

    private static void Merge(int[] nums, int start, int middle, int end) {
        //1. 創(chuàng)建end - start + 1長度的數(shù)組，存放本次合并結(jié)果
        int[] temp = new int[end - start + 1];
        int index = 0;

        //2. 提取左半和右半的起點(diǎn)
        int index1 = start;
        int index2 = middle+1;

        //3. while合并
        while(index1 <= middle && index2 <= end){
            if(nums[index1] < nums[index2]){
                temp[index++] = nums[index1++];
            }else{
                temp[index++] = nums[index2++];
            }
        }

        //4. 補(bǔ)錄
        while(index1 <= middle){
            temp[index++] = nums[index1++];
        }
        while(index2 <= end){
            temp[index++] = nums[index2++];
        }

        //5. 重新存回到nums朴乖，從start開始
        for(int i=0;i<temp.length;i++){
            nums[i+start] = temp[i];
        }
    }

5. 快排(不穩(wěn)定)：

時(shí)間復(fù)雜度：Onlogn祖屏，最壞On2
空間復(fù)雜度：O(logn) //pivot斷點(diǎn)空間O(logn)
最好情況O(n*logn)助赞，二叉樹≡祝——Partition函數(shù)每次恰好能均分序列雹食，其遞歸樹的深度就為.log2n.+1（.x.表示不大于x的最大整數(shù)），即僅需遞歸log2n次期丰；最壞情況O（n^2）群叶，單鏈表，每次劃分只能將序列分為一個(gè)元素與其他元素兩部分钝荡，這時(shí)的快速排序退化為冒泡排序街立，如果用數(shù)畫出來，得到的將會(huì)是一棵單斜樹埠通，也就是說所有所有的節(jié)點(diǎn)只有左（右）節(jié)點(diǎn)的樹
不穩(wěn)定：因?yàn)榭炫乓M(jìn)行交換赎离，可能會(huì)改變兩個(gè)相等元素的象對(duì)位置
具體實(shí)現(xiàn)

    private static void quickSort(int[] nums, int start, int end) {
        //1. 判斷越界
        if(start > end){
            return;
        }

        //2. 提取基準(zhǔn)數(shù)
        int pivot = getPivot(nums,start,end);

        //3. 遞歸左半部分
        quickSort(nums,start,pivot-1);

        //4. 遞歸右半部分
        quickSort(nums,pivot+1,end);
    }

    private static int getPivot(int[] nums, int start, int end) {
        //1. 提取基準(zhǔn)數(shù)為nums[start]
        int pivot = nums[start];

        //2. 左右指針
        int left = start;
        int right = end;

        //3. while循環(huán)
        while(left <= right){
            while (left <= right && nums[left] <= pivot){
                left++;
            }
            while(left <= right && nums[right] > pivot){
                right--;
            }

            if(left < right){
                swap(nums,left,right);
            }
        }

        //4. 基準(zhǔn)數(shù)歸位
        swap(nums,start,right);
        return right;
    }

6. 快速選擇quickselect：TOPK找單一元素問題首選，遞歸排序結(jié)束后端辱，nums[0]就是TOPK

時(shí)間復(fù)雜度:On
空間復(fù)雜度：On

    private static void quickSort(int[] nums, int start, int end,int k) {
        //1. 判斷越界
        if(start == end){
            return;
        }

        //2. 提取基準(zhǔn)數(shù)
        int pivot = nums[start];

        //3. 左右指針
        int left = start;
        int right = end;

        //3. while循環(huán)
        while(left <= right){
            while (left <= right && nums[left] < pivot){
                left++;
            }
            while (left <= right && nums[right] > pivot){
                right--;
            }
            if(left <= right){
                swap(nums,left,right);
                left++;
                right--;
            }
        }

        //4. 繼續(xù)遞歸
        if(start <= k && k <= right){
            quickSort(nums,start,right,k);
        }
        if(left <= k && k <= end){
            quickSort(nums,left,end,k);
        }
    }

7. 堆排(O(nlogn))(不穩(wěn)定)

時(shí)間復(fù)雜度：Onlogn
空間復(fù)雜度：O(1)
基本原理：是將待排序記錄看作完全二叉樹梁剔，可以建立大根堆或小根堆。
以大根堆為例舞蔽，
1. 建堆：提取當(dāng)前下標(biāo)荣病，while true循環(huán)交換父節(jié)點(diǎn)和當(dāng)前下標(biāo)。如果能夠交換渗柿，將當(dāng)前下標(biāo)替換為父節(jié)點(diǎn)下標(biāo)
2. 彈出：暫存根節(jié)點(diǎn)个盆。根節(jié)點(diǎn)與最后一個(gè)節(jié)點(diǎn)交換。while true循環(huán)朵栖。左右節(jié)點(diǎn)下標(biāo)颊亮。如果左節(jié)點(diǎn)越界，break陨溅。否則將maxIndex設(shè)置為left编兄，maxIndex與right比較，如果小声登，交換。交換后的maxIndex與根節(jié)點(diǎn)比較揣苏，如果比根節(jié)點(diǎn)大悯嗓，交換，將跟節(jié)點(diǎn)下標(biāo)替換為maxIndex

        //構(gòu)建堆結(jié)構(gòu)
        for(int i=0;i<nums.length;i++){
            createHeap(nums,i);
        }

        //倒序彈出大根堆形成從小到大排序
        int size = nums.length;
        for(int i=nums.length-1;i>=0;i--){
            nums[i] = HeapPoll(nums,size--);
        }

        for(int i=0;i<nums.length;i++){
            System.out.println(nums[i]);
        }
    }

    private static int HeapPoll(int[] nums, int index) {
        //1. 暫存根節(jié)點(diǎn)nums[0]
        int result = nums[0];

        //2. 最后一個(gè)節(jié)點(diǎn)替換nums[0]
        nums[0] = nums[index-1];

        int curIndex = 0;

        //3. while true循環(huán)交換
        while (true){
            //左節(jié)點(diǎn)下標(biāo)
            int left = curIndex * 2 + 1;
            //右節(jié)點(diǎn)下標(biāo)
            int right = curIndex * 2 + 2;

            //1. 如果左節(jié)點(diǎn)越界卸察，break
            if(left >= index){
                break;
            }

            //先暫存maxIndex
            int maxIndex = left;

            //2. 左右節(jié)點(diǎn)值比較
            if(right < index && nums[maxIndex] < nums[right]){
                maxIndex = right;
            }

            //3. 本次最大值與根節(jié)點(diǎn)比較
            if(nums[curIndex] < nums[maxIndex]){
                swap(nums,curIndex,maxIndex);
            }else{
                break;
            }

            //5. 將根節(jié)點(diǎn)下標(biāo)替換為maxIndex
            curIndex = maxIndex;
        }
        return result;
    }

    private static void createHeap(int[] nums, int index) {
        //1. 提取index
        int curIndex = index;

        //2. while循環(huán)
        while(curIndex > 0){
            //父節(jié)點(diǎn)下標(biāo)
            int parentIndex = (curIndex-1)/2;
            //如果父節(jié)點(diǎn)比當(dāng)前節(jié)點(diǎn)小脯厨，交換。否則break循環(huán)
            if(nums[parentIndex] < nums[curIndex]){
                swap(nums,parentIndex,curIndex);
            }else{
                break;
            }

            //提取父節(jié)點(diǎn)下標(biāo)為當(dāng)前節(jié)點(diǎn)下標(biāo)
            curIndex = parentIndex;
        }
    }

Arrays.sort()內(nèi)部實(shí)現(xiàn)

size小于60坑质，用插排
size大于60合武，用快排或歸并

海量數(shù)據(jù)處理：https://github.com/doocs/advanced-java

1. 在大量的URL中找出相同的URL

題目：給定 a临梗、b 兩個(gè)文件，各存放 50 億個(gè) URL稼跳，每個(gè) URL 各占 64B盟庞，內(nèi)存限制是 4G。請(qǐng)找出 a汤善、b 兩個(gè)文件共同的 URL什猖。
分析：
1. 內(nèi)存不足，分治策略红淡，遍歷大文件不狮，將結(jié)果存儲(chǔ)到1000個(gè)小文件中
解法：
1. 遍歷文件a，對(duì)URL求hash取余：hash(url) % 1000在旱，分成1000個(gè)數(shù)據(jù)摇零。
2. 遍歷文件b，與文件a做相同處理桶蝎。
3. 遍歷a驻仅，將url存入HashSet，然后遍歷b俊嗽，將url存入HashSet雾家。HashSet中數(shù)據(jù)就是相同的URL
總結(jié)
1. 內(nèi)存不足，分治策略
2. 遍歷大文件绍豁，對(duì)URL進(jìn)行hash取余芯咧，將結(jié)果存儲(chǔ)到1000個(gè)小文件中，每個(gè)小文件大小不超過內(nèi)存限制
3. 分別遍歷小文件竹揍，使用HashSet去重

2. 大量數(shù)據(jù)找高頻詞

題目：有一個(gè) 1GB 大小的文件敬飒，文件里每一行是一個(gè)詞，每個(gè)詞的大小不超過 16B芬位，內(nèi)存大小限制是 1MB无拗，要求返回頻數(shù)最高的 100 個(gè)詞(Top 100)。
分析：
1. 內(nèi)存不足昧碉，分治策略英染，遍歷大文件，將結(jié)果存儲(chǔ)到5000個(gè)小文件中
解法：
1. 遍歷大文件被饿，對(duì)詞求hash取余：hash(x) % 5000四康，分成5000個(gè)小文件。
2. 遍歷這5000個(gè)小文件狭握，使用HashMap統(tǒng)計(jì)詞出現(xiàn)次數(shù)闪金。
3. 大根堆，容量為100。依次遍歷小文件哎垦，比較HashMap.get(b)-HashMap.get(a)囱嫩，存入keySet，然后依次彈出即可
總結(jié)
1. 內(nèi)存不足漏设，分治策略墨闲，每個(gè)小文件不超過1MB
2. 遍歷大文件，求hash取余愿题，拆分成小文件
3. 使用HashMap統(tǒng)計(jì)出現(xiàn)次數(shù)
4. 大根堆比較出現(xiàn)次數(shù)：Map.get(b)-Map.get(a)损俭。存入keySet，彈出

3. 如何找出某一天訪問百度網(wǎng)站最多的 IP潘酗？

題目：現(xiàn)有海量日志數(shù)據(jù)保存在一個(gè)超大文件中杆兵，該文件無法直接讀入內(nèi)存，要求從中提取某天訪問百度次數(shù)最多的那個(gè) IP仔夺。
分析
1. 內(nèi)存不足琐脏，分治策略，遍歷大文件缸兔，將結(jié)果存儲(chǔ)到x個(gè)小文件中
解法
1. 遍歷大文件日裙，對(duì)ip求hash取余，hash(ip) % x惰蜜，分成x個(gè)小文件
2. 遍歷x個(gè)小文件昂拂，使用HashMap統(tǒng)計(jì)出現(xiàn)次數(shù)
3. 遍歷keySet，求出max值即可
總結(jié)
1. 內(nèi)存不足抛猖，分治策略格侯，每個(gè)小文件不超過限制
2. 遍歷小文件，求hash取余财著，拆分成小文件
3. 使用HashMap統(tǒng)計(jì)出現(xiàn)次數(shù)
4. 遍歷keySet联四，求出max

4. 如何在大量的數(shù)據(jù)中找出不重復(fù)的整數(shù)？

題目：在 2.5 億個(gè)整數(shù)中找出不重復(fù)的整數(shù)撑教。注意：內(nèi)存不足以容納這 2.5 億個(gè)整數(shù)朝墩。
分析
1. 內(nèi)存不足，分治策略伟姐，將大文件拆分為小文件
2. bit數(shù)組位圖收苏。一個(gè)或多個(gè)bit來標(biāo)記某個(gè)元素的值，bit空間小愤兵。
  1. 例如：對(duì)于0-7之間的數(shù)組(6,5,4,2,1,3)來說倒戏，可以創(chuàng)建一共8bit的數(shù)組[0,0,0,0,0,0,0,0]
  2. 遍歷數(shù)組，6恐似，對(duì)應(yīng)bit[5]標(biāo)為1，遇到5傍念，對(duì)應(yīng)bit[4]標(biāo)為1矫夷，依次標(biāo)記葛闷。最終bit數(shù)組：[0,1,1,1,1,1,1,0]。遍歷
  3. 本題：可以用兩個(gè)bit數(shù)組來標(biāo)記双藕。
    1. 00：沒出現(xiàn)過
    2. 01：出現(xiàn)一次淑趾，目標(biāo)值
    3. 10：出現(xiàn)多次
解法：
1. 分治策略同123題
2. 位圖法
  1. 2.5億個(gè)整數(shù)，1個(gè)整數(shù)4位忧陪，4 * 8bit = 32bit扣泊。需要的bit數(shù)組大小為2的32bit * 2b = 1GB。
  2. 遍歷bit數(shù)組嘶摊，將01位整數(shù)輸出
總結(jié)
1. 內(nèi)存不足延蟹，分治策略
2. 大數(shù)據(jù)找重復(fù)、不重復(fù)叶堆、目標(biāo)值阱飘。用位圖

5. 如何在大量的數(shù)據(jù)中判斷一個(gè)數(shù)是否存在？

題目：給定 40 億個(gè)不重復(fù)的沒排過序的 unsigned int 型整數(shù)虱颗，然后再給定一個(gè)數(shù)沥匈，如何快速判斷這個(gè)數(shù)是否在這 40 億個(gè)整數(shù)當(dāng)中？
分析
1. 內(nèi)存不足忘渔，分治策略高帖，將大文件拆分成小文件2
2. bit數(shù)組位圖法。
解法
1. 40億個(gè)整數(shù)畦粮，創(chuàng)建bit數(shù)組散址，bit數(shù)組大小位40億 * 2bit = 500MB。存在著設(shè)置為1锈玉，不存在設(shè)置為0爪飘。
總結(jié)
1. 內(nèi)存不足，分治策略
2. 大數(shù)據(jù)找重復(fù)值拉背、不重復(fù)值师崎、目標(biāo)值。用位圖

6. 如何查詢最熱門的查詢串椅棺？

題目：假設(shè)目前有 1000w 個(gè)記錄（這些查詢串的重復(fù)度比較高犁罩，雖然總數(shù)是 1000w，但如果除去重復(fù)后两疚，則不超過 300w 個(gè)）床估。請(qǐng)統(tǒng)計(jì)最熱門的 10 個(gè)查詢串，要求使用的內(nèi)存不能超過 1G诱渤。
分析：
1. 每個(gè)字符串255B丐巫，1000W個(gè)共2.55G。內(nèi)存不足，分治策略
2. 統(tǒng)計(jì)出現(xiàn)次數(shù)递胧，可以用HashMap
解法
1. 分治策略碑韵，劃分為多個(gè)小文件，求出每個(gè)小文件中出現(xiàn)次數(shù)前10的字符串(使用HashMap)缎脾，通過大根堆求出出現(xiàn)次數(shù)前10的字符串
2. hashMap祝闻。去重后不超過300W個(gè)，即大約需要700MB遗菠。直接使用HashMap統(tǒng)計(jì)
總結(jié)
1. 內(nèi)存不足联喘，分治策略
2. 大數(shù)據(jù)找重復(fù)字符串，重復(fù)度高的情況下辙纬，可以考慮使用HashMap直接統(tǒng)計(jì)

7. 如何統(tǒng)計(jì)不同電話號(hào)碼的個(gè)數(shù)豁遭？

題目：已知某個(gè)文件內(nèi)包含一些電話號(hào)碼，每個(gè)號(hào)碼為 8 位數(shù)字牲平，統(tǒng)計(jì)不同號(hào)碼的個(gè)數(shù)堤框。
分析
1. 數(shù)據(jù)重復(fù)問題，考慮bit位圖
解法
1. 8位電話號(hào)碼纵柿，個(gè)數(shù)位10的8次方個(gè)蜈抓，1億個(gè)。1億個(gè)Bit昂儒，大小100MB沟使。
2. 創(chuàng)建長度1億的bit數(shù)組。遍歷電話號(hào)碼渊跋，存在為1腊嗡。統(tǒng)計(jì)1的個(gè)數(shù)
總結(jié)
1. 數(shù)據(jù)重復(fù)問題，考慮位圖

8. 如何找出排名前 500 的數(shù)拾酝？

題目：有 20 個(gè)數(shù)組燕少，每個(gè)數(shù)組有 500 個(gè)元素，并且有序排列蒿囤。如何在這 20*500 個(gè)數(shù)中找出前 500 的數(shù)客们？
分析
1. 大數(shù)據(jù)TOPk問題，考慮堆排
2. 20個(gè)數(shù)組材诽，每個(gè)數(shù)組有500個(gè)元素褂萧，且有序愁铺，可以看作是二維數(shù)組走搁。
解法
1. 創(chuàng)建一個(gè)比較器扇住，用于在建堆時(shí)將每個(gè)數(shù)組最大的值存入堆。
2. 建立一個(gè)大小為20的大根堆睁枕，遍歷二維數(shù)組的行官边，假設(shè)每一行數(shù)組是降序沸手，我們可以將每一行的最大值入堆
3. while循環(huán)彈出堆頂，用一個(gè)大小500的數(shù)組接收拒逮，然后index+1將本行的后續(xù)元素入堆罐氨，重復(fù)500次，直到填滿數(shù)組為止
詳細(xì)代碼

import lombok.Data;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * @author https://github.com/yanglbme
 */
@Data
public class DataWithSource implements Comparable<DataWithSource> {
    /**
     * 數(shù)值
     */
    private int value;

    /**
     * 記錄數(shù)值來源的數(shù)組
     */
    private int source;

    /**
     * 記錄數(shù)值在數(shù)組中的索引
     */
    private int index;

    public DataWithSource(int value, int source, int index) {
        this.value = value;
        this.source = source;
        this.index = index;
    }

    /**
     *
     * 由于 PriorityQueue 使用小頂堆來實(shí)現(xiàn)滩援，這里通過修改
     * 兩個(gè)整數(shù)的比較邏輯來讓 PriorityQueue 變成大頂堆
     */
    @Override
    public int compareTo(DataWithSource o) {
        return Integer.compare(o.getValue(), this.value);
    }
}

class Test {
    public static int[] getTop(int[][] data) {
        int rowSize = data.length;
        int columnSize = data[0].length;

        // 創(chuàng)建一個(gè)columnSize大小的數(shù)組，存放結(jié)果
        int[] result = new int[columnSize];

        PriorityQueue<DataWithSource> maxHeap = new PriorityQueue<>();
        for (int i = 0; i < rowSize; ++i) {
            // 將每個(gè)數(shù)組的最大一個(gè)元素放入堆中
            DataWithSource d = new DataWithSource(data[i][0], i, 0);
            maxHeap.add(d);
        }

        int num = 0;
        while (num < columnSize) {
            // 刪除堆頂元素
            DataWithSource d = maxHeap.poll();
            result[num++] = d.getValue();
            if (num >= columnSize) {
                break;
            }

            d.setValue(data[d.getSource()][d.getIndex() + 1]);
            d.setIndex(d.getIndex() + 1);
            maxHeap.add(d);
        }
        return result;

    }

    public static void main(String[] args) {
        int[][] data = {
                {29, 17, 14, 2, 1},
                {19, 17, 16, 15, 6},
                {30, 25, 20, 14, 5},
        };

        int[] top = getTop(data);
        System.out.println(Arrays.toString(top)); // [30, 29, 25, 20, 19]
    }
}

9. 按照query的頻度排序

題目：有 10 個(gè)文件塔嬉，每個(gè)文件大小為 1G玩徊，每個(gè)文件的每一行存放的都是用戶的 query，每個(gè)文件的 query 都可能重復(fù)谨究。要求按照 query 的頻度排序恩袱。
分析
1. 如果重復(fù)度高，直接用HashMap可能不會(huì)超內(nèi)存胶哲。如果重復(fù)度不高畔塔，還是考慮分治策略
解法
1. 重復(fù)度高，使用HashMap直接統(tǒng)計(jì)出現(xiàn)次數(shù)鸯屿，按照出現(xiàn)次數(shù)排序
2. 重復(fù)度不高澈吨，分治，將大文件拆分成小文件寄摆，hash取余谅辣，使用HashMap分別統(tǒng)計(jì)小文件的query出現(xiàn)次數(shù)，然后進(jìn)行排序(如果內(nèi)存不足婶恼，可以使用歸并排序)
總結(jié)
1. 數(shù)據(jù)出現(xiàn)次數(shù)桑阶，可以使用HashMap

10. 如何從 5 億個(gè)數(shù)中找出中位數(shù)？

從 5 億個(gè)數(shù)中找出中位數(shù)勾邦。數(shù)據(jù)排序后蚣录，位置在最中間的數(shù)就是中位數(shù)。當(dāng)樣本數(shù)為奇數(shù)時(shí)眷篇，中位數(shù)為第 (N+1)/2 個(gè)數(shù)萎河；當(dāng)樣本數(shù)為偶數(shù)時(shí)，中位數(shù)為第 N/2 個(gè)數(shù)與第 1+N/2 個(gè)數(shù)的均值铅歼。
分析
1. 分治法公壤，分為正數(shù)和負(fù)數(shù)。遍歷這5億個(gè)數(shù)椎椰，轉(zhuǎn)換為二進(jìn)制符號(hào)位厦幅，如果最高位為1，是負(fù)數(shù)慨飘，存入neg數(shù)組确憨，如果最高位位0译荞，是正數(shù)，存入pos數(shù)組休弃。完成之后吞歼，如果neg數(shù)組長度為1億，那么中位數(shù)必定在pos數(shù)組的第1.5億個(gè)數(shù)與后面一個(gè)數(shù)的平均值

11. 如果一個(gè)黑名單網(wǎng)站包含100億個(gè)黑名單網(wǎng)頁塔猾，每個(gè)網(wǎng)頁最多占64B篙骡，設(shè)計(jì)一個(gè)系統(tǒng)，判斷當(dāng)前的URL是否在這個(gè)黑名單當(dāng)中丈甸，要求額外空間不超過30GB糯俗，允許誤差率為萬分之一。

分析：假設(shè)一個(gè)網(wǎng)頁黑名單有URL為100億睦擂，每個(gè)樣本為64B得湘，失誤率為0.01%，經(jīng)過布隆過濾器的公式計(jì)算后顿仇，需要布隆過濾器大小為25GB淘正，這遠(yuǎn)遠(yuǎn)小于使用哈希表的640GB的空間。并且由于是通過hash進(jìn)行查找的臼闻，所以基本都可以在O(1)的時(shí)間完成鸿吆！
解法
1. 導(dǎo)入布隆過濾器依賴
2. 創(chuàng)建布隆過濾器，遍歷存入些阅，統(tǒng)計(jì)誤判次數(shù)
3. 根據(jù)誤判次數(shù)計(jì)算誤差率

八大排序算法及海量數(shù)據(jù)處理

八大排序算法及海量數(shù)據(jù)處理

排序算法

基礎(chǔ)排序，時(shí)間復(fù)雜度O(n2)

進(jìn)階排序盛龄，時(shí)間復(fù)雜度O(nlogn)

1. 直接插入排序(穩(wěn)定)：從i=1開始遍歷饰迹，提取nums[i]作為標(biāo)準(zhǔn)芳誓，排序[insertIndex,i-1]區(qū)間，排序完成之后啊鸭，將nums[i]插入到insertIndex+1位置

2. 冒泡排序(穩(wěn)定)：j循環(huán)[0,nums.length-1-i]褥符，前后比較，如果前比后大抚垃，交換

3. 選擇排序(不穩(wěn)定)：提取當(dāng)前索引作為min邑狸，遍歷從[i+1,nums.length]找到比nums[min]小的值懈糯，提取它的索引。遍歷完成后单雾，如果min不等于i赚哗，交換i和min的值

4. 歸并排序(穩(wěn)定)：將數(shù)組分成兩半([0,middle]和[middle+1,len])

5. 快排(不穩(wěn)定)：

6. 快速選擇quickselect：TOPK找單一元素問題首選，遞歸排序結(jié)束后端辱，nums[0]就是TOPK

7. 堆排(O(nlogn))(不穩(wěn)定)

Arrays.sort()內(nèi)部實(shí)現(xiàn)

海量數(shù)據(jù)處理：https://github.com/doocs/advanced-java

1. 在大量的URL中找出相同的URL

2. 大量數(shù)據(jù)找高頻詞

3. 如何找出某一天訪問百度網(wǎng)站最多的 IP潘酗？

4. 如何在大量的數(shù)據(jù)中找出不重復(fù)的整數(shù)？

5. 如何在大量的數(shù)據(jù)中判斷一個(gè)數(shù)是否存在？

6. 如何查詢最熱門的查詢串椅棺？

7. 如何統(tǒng)計(jì)不同電話號(hào)碼的個(gè)數(shù)豁遭？

8. 如何找出排名前 500 的數(shù)拾酝？

9. 按照query的頻度排序

10. 如何從 5 億個(gè)數(shù)中找出中位數(shù)？