數(shù)據(jù)結構與算法簡述(下)

目錄:

  • 算法簡介
  • 排序算法
  • 遞歸與窮舉
  • 貪心與分治
  • 動態(tài)規(guī)劃和回溯

1.算法簡介

解題方案的準確而完整的描述寄摆,是一系列解決問題的清晰指令婶恼。

特征

  • 有窮性
  • 確切性
  • 輸入項
  • 輸出項
  • 可行性

算法優(yōu)劣評定

  • 時間復雜度
  • 空間復雜度
  • 正確性
  • 可讀性
  • 健壯性

2.算法排序

2.1 插入排序
  • 冒泡排序
public static void main(String [] args){
        int[] a = {49,38,65,97,23,22,76,1,5,8,2,0,-1};
        //直接插入排序開始
        for(int i = 1;i<a.length;i++){
            int temp = a[i];//新遍歷的值柏副,等待插入到前面的有序數(shù)組
            int j;
            for(j = i-1;j>=0;j--){
                //將大于temp的數(shù)往后面移一步
                if(a[j]>temp){
                    a[j+1] = a[j];
                }else{
                    break;
                }
            }
           //break數(shù)據(jù)代表j處數(shù)據(jù)小于temp割择,j之前的數(shù)據(jù)又是從小到大排列荔泳,所以temp就放在j后面
            a[j+1] = temp;
        }
        System.out.println("排序后:");
        for(int i = 0;i<a.length;i++){
            System.out.println(" "+a[i]);
        }
    }

時間復雜度:O(N^2)

  • 二分法排序

時間復雜度:O(logN)

  • 希爾排序

時間復雜度:O(N^(3/2))

2.2 選擇排序
  • 簡單選擇排序

時間復雜度:O(N^(3/2))

  • 堆排序
    //堆排序
    public static void main(String[] args){
        int[] array = {39,44,1,0,8,66,23,67,9,15,100,70,22,3,6,54};
        HeapSort heapSort = new HeapSort();
        heapSort.heapSort(array);
        for(int i = 0;i<array.length;i++){
            System.out.println(" "+array[i]);
        }
    }
    
    public void heapSort(int [] a){
        if(a == null||a.length<=1){
            return;
        }
        //創(chuàng)建大堆
        buildMaxHeap(a);
        for(int i = a.length-1;i>=1;i--){
            //最大元素已經(jīng)排在了下標為0的地方
            exchangeElements(a, 0, i);//每交換換一次玛歌,就沉淀一個大元素
            maxHeap(a, i, 0);
        }
    }

    
    private void buildMaxHeap(int[] a) {
        int half = (a.length -1)/2;//假設長度為9
        for(int i = half;i>=0;i--){
            //只需遍歷43210
            maxHeap(a,a.length,i);
        }
    }

    //length表示用于構造大堆的數(shù)組長度元素數(shù)量
    private void maxHeap(int[] a, int length, int i) {
        int left = i*2+1;
        int right = i*2+2;
        int largest = i;
        if(left<length&&a[left]>a[i]){
            largest = left;
        }
        if(right<length&&a[right]>a[largest]){
            largest = right;
        }
        if(i!=largest){
            //進行數(shù)據(jù)交換
            exchangeElements(a,i,largest);
            maxHeap(a, length, largest);
        }
    }

    //在數(shù)組a里進行兩個下標元素交換
    private void exchangeElements(int[] a, int i, int largest) {
        int temp = a[i];
        a[i] = a[largest];
        a[largest] = temp;
    }

時間復雜度:O(NlogN)

2.3 交換排序
  • 快速排序
    /**
     * 快速排序
     * 
     * @param a
     * @param i
     * @param j
     */
    private void quickSort(int[] a, int low, int high) {
        if (low < high) {
            int middle = getMiddle(a, low, high);
            quickSort(a, 0, middle - 1);
            quickSort(a, middle + 1, high);
        }
    }

    /**
     * 獲取中間下標
     * 
     * @param a
     * @param low
     * @param high
     * @return
     */
    private int getMiddle(int[] a, int low, int high) {
        int temp = a[low];// 基準元素
        while (low < high) {
            while (low < high && a[high] >= temp) {
                high--;
            }
            a[low] = a[high];
            while (low < high && a[low] <= temp) {
                low++;
            }
            a[high] = a[low];
        }
        a[low] = temp;// 插入到排序后正確的位置
        return low;
    }

    public static void main(String[] args) {
        QuickSort quickSort = new QuickSort();
        int[] a = { 19, 2, 3, 90, 67, 33, -7, 24, 3, 56, 34, 5 };
        quickSort.quickSort(a, 0, a.length - 1);
        for (int num : a) {
            System.out.println(" " + num);
        }
    }

時間復雜度:O(NlogN)

2.4 歸并排序
    //歸并排序
    public void mergeSort(int[] a, int left, int right) {
        if (left < right) {
            int middle = (left + right) / 2;
            mergeSort(a, left, middle);
            mergeSort(a, middle + 1, right);
            merge(a, left, middle, right);// 合并
        }
    }

    private void merge(int[] a, int left, int middle, int right) {
        int[] tmpArray = new int[a.length];
        int rightStart = middle + 1;
        int tmp = left;
        int third = left;
        // 比較兩個小數(shù)組相應下標位置的數(shù)組大小达舒,小的先放進新數(shù)組
        while (left <= middle && rightStart <= right) {
            if (a[left] <= a[rightStart]) {
                tmpArray[third++] = a[left++];
            } else {
                tmpArray[third++] = a[rightStart++];
            }
        }
        // 如果左邊還有數(shù)據(jù)需要拷貝巩搏,把左邊數(shù)組剩下的拷貝到新數(shù)組
        while (left <= middle) {
            tmpArray[third++] = a[left++];
        }
        // 如果右邊還有數(shù)據(jù)......
        while (rightStart <= right) {
            tmpArray[third++] = a[rightStart++];
        }
        while (tmp <= right) {
            a[tmp] = tmpArray[tmp++];
        }
    }

    public static void main(String[] args) {
        MergeSort mergeSort = new MergeSort();
        int[] a = new int[] { 90, 3, 2, 67, 44, -9, 87, 65, 11, 9, 2, 8 };
        mergeSort.mergeSort(a, 0, a.length - 1);
        for (int n : a) {
            System.out.print(" " + n);
        }
    }

時間復雜度:O(NlogN)

2.5 基數(shù)排序
    public void sort(int[] array) {
        int max = 0;// 獲取最大值
        for (int i = 0; i < array.length; i++) {
            if (max < array[i]) {
                max = array[i];
            }
        }
        int times = 0;// 獲取最大值位數(shù)
        while (max > 0) {
            max = max / 10;
            times++;
        }
        List<ArrayList> queue = new ArrayList<ArrayList>();// 多維數(shù)組
        for (int i = 0; i < 10; i++) {
            ArrayList<Object> q = new ArrayList<>();
            queue.add(q);
        }
        for (int i = 0; i < times; i++) {
            for (int j = 0; j < array.length; j++) {
                // 獲取對應的位的值(i為0是個位篙骡,1是10位丈甸,2是百位)
                int x = array[j] % (int) Math.pow(10, i + 1) / (int) Math.pow(10, i);
                ArrayList<Integer> q = queue.get(x);
                q.add(array[j]);// 把元素添加進對應下標數(shù)組
                // queue.set(x,q);//待定
            }
            // 開始收集
            int count = 0;
            for (int j = 0; j < 10; j++) {
                while (queue.get(j).size() > 0) {
                    ArrayList<Integer> q = queue.get(j);// 拿到每一個數(shù)組
                    array[count] = q.get(0);
                    q.remove(0);
                    count++;
                }
            }
        }
    }

    public static void main(String[] args) {
        BasicSort basicSort = new BasicSort();
        int[] a = { 136, 2, 6, 8, 9, 2, 8, 11, 23, 56, 34, 90, 89, 29, 145, 209, 320, 78, 3 };
        basicSort.sort(a);
        for (int n : a) {
            System.out.print(" " + n);
        }
    }

時間復雜度:O(NlogN)

3.遞歸與窮舉

  • 二分法查找

4.貪心與分治

5.動態(tài)規(guī)劃和回避

最后編輯于
?著作權歸作者所有,轉載或內容合作請聯(lián)系作者
  • 序言:七十年代末得湘,一起剝皮案震驚了整個濱河市淘正,隨后出現(xiàn)的幾起案子鸿吆,更是在濱河造成了極大的恐慌惩淳,老刑警劉巖乓搬,帶你破解...
    沈念sama閱讀 210,978評論 6 490
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場離奇詭異激蹲,居然都是意外死亡,警方通過查閱死者的電腦和手機乘瓤,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 89,954評論 2 384
  • 文/潘曉璐 我一進店門馅扣,熙熙樓的掌柜王于貴愁眉苦臉地迎上來着降,“玉大人,你說我怎么就攤上這事蓄喇∽逼” “怎么了钱骂?”我有些...
    開封第一講書人閱讀 156,623評論 0 345
  • 文/不壞的土叔 我叫張陵见秽,是天一觀的道長讨盒。 經(jīng)常有香客問我返顺,道長,這世上最難降的妖魔是什么振乏? 我笑而不...
    開封第一講書人閱讀 56,324評論 1 282
  • 正文 為了忘掉前任,我火速辦了婚禮,結果婚禮上,老公的妹妹穿的比我還像新娘脓匿。我一直安慰自己,他們只是感情好宦赠,可當我...
    茶點故事閱讀 65,390評論 5 384
  • 文/花漫 我一把揭開白布陪毡。 她就那樣靜靜地躺著,像睡著了一般勾扭。 火紅的嫁衣襯著肌膚如雪毡琉。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 49,741評論 1 289
  • 那天妙色,我揣著相機與錄音桅滋,去河邊找鬼。 笑死身辨,一個胖子當著我的面吹牛丐谋,可吹牛的內容都是我干的。 我是一名探鬼主播煌珊,決...
    沈念sama閱讀 38,892評論 3 405
  • 文/蒼蘭香墨 我猛地睜開眼号俐,長吁一口氣:“原來是場噩夢啊……” “哼定庵!你這毒婦竟也來了猪落?” 一聲冷哼從身側響起,我...
    開封第一講書人閱讀 37,655評論 0 266
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎袁余,沒想到半個月后,有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體噪漾,經(jīng)...
    沈念sama閱讀 44,104評論 1 303
  • 正文 獨居荒郊野嶺守林人離奇死亡诈胜,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內容為張勛視角 年9月15日...
    茶點故事閱讀 36,451評論 2 325
  • 正文 我和宋清朗相戀三年昵仅,在試婚紗的時候發(fā)現(xiàn)自己被綠了岩饼。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點故事閱讀 38,569評論 1 340
  • 序言:一個原本活蹦亂跳的男人離奇死亡,死狀恐怖俭茧,靈堂內的尸體忽然破棺而出尝抖,到底是詐尸還是另有隱情衙熔,我是刑警寧澤红氯,帶...
    沈念sama閱讀 34,254評論 4 328
  • 正文 年R本政府宣布,位于F島的核電站婉称,受9級特大地震影響悔据,放射性物質發(fā)生泄漏藻烤。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點故事閱讀 39,834評論 3 312
  • 文/蒙蒙 一倾芝、第九天 我趴在偏房一處隱蔽的房頂上張望晨另。 院中可真熱鬧,春花似錦路翻、人聲如沸嘹黔。這莊子的主人今日做“春日...
    開封第一講書人閱讀 30,725評論 0 21
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽拐袜。三九已至甜攀,卻和暖如春规阀,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背彤敛。 一陣腳步聲響...
    開封第一講書人閱讀 31,950評論 1 264
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留之剧,地道東北人。 一個月前我還...
    沈念sama閱讀 46,260評論 2 360
  • 正文 我出身青樓,卻偏偏與公主長得像词疼,于是被迫代替她去往敵國和親贰盗。 傳聞我的和親對象是個殘疾皇子,可洞房花燭夜當晚...
    茶點故事閱讀 43,446評論 2 348

推薦閱讀更多精彩內容

  • 貪心算法 貪心算法總是作出在當前看來最好的選擇。也就是說貪心算法并不從整體最優(yōu)考慮址遇,它所作出的選擇只是在某種意義上...
    fredal閱讀 9,221評論 3 52
  • 課程介紹 先修課:概率統(tǒng)計,程序設計實習,集合論與圖論 后續(xù)課:算法分析與設計哀九,編譯原理息裸,操作系統(tǒng),數(shù)據(jù)庫概論,人...
    ShellyWhen閱讀 2,265評論 0 3
  • 【蝸牛計劃笆搓,每天進步一點點】 2017/9/16 打卡天數(shù):第70天 (1)我今年的三個年度目標是满败? 1:每日一畫...
    梅洛的聽雨軒閱讀 536評論 0 3
  • 參加書目:《目標感:28天養(yǎng)成卓越人士的思維和行動模式》 作者:菲爾·奧萊 01 強化你的愿望 做一件事情的愿望有...
    小小_dijiu閱讀 241評論 2 6
  • 要說到自己內在男人,瞬間覺得自己能量滿滿!直接回到童年時代幻件,從小我不是在翻墻頭麸塞,就是鉆下水道哪工,逢年過節(jié)就和一幫子男...
    奔跑的的兔子2016閱讀 210評論 0 0