java數(shù)據(jù)結(jié)構(gòu)與算法(1)

數(shù)組

如何插入一條新的數(shù)據(jù)項
如何尋找某一特定的數(shù)據(jù)項
如何刪除某一特定的數(shù)據(jù)項
如何迭代的訪問各個數(shù)據(jù)項，以便進行顯示或其他操作

無序數(shù)組

public class HighArray {
    private Long[] arr;
    private int item;

    public HighArray(int length) {
        arr = new Long[length];
        item = 0;
    }

    public int find(long param) {
        for (int i = 0; i < item; i++) {
            if (arr[i] == param) {
                return i;
            }
        }
        return -1;
    }

    public boolean delete(long param) {
        int j = find(param);
        if (j == -1) {
            return false;
        }
        for (int i = j; i < item - 1; i++) {
            arr[i] = arr[i + 1];
        }
        item--;
        return true;
    }

    public void insert(long param) {
        arr[item] = param;
        item++;
    }

    public void dispaly() {
        System.out.print("[");
        for (int i = 0; i < item; i++) {
            System.out.print(arr[i]);
            if (i != item - 1) {
                System.out.print(",");
            }
        }
        System.out.println("]");
    }
}

有序數(shù)組

有序數(shù)組的查找速度比無序數(shù)組快得多,不好的方面是在插入操作中由于所有靠后的數(shù)據(jù)都需要移動以騰開控件,所以速度較慢

public class OrderArray {
    private Long[] arr;
    private int item;

    public int find(long param) {
        int begin = 0;
        int end = item - 1;
        int z;
        while (true) {
            z = (begin + end) / 2;
            System.out.print(begin + " ");
            System.out.print(end + " ");
            System.out.println(z);
            if (begin > end) {
                return -1;
            }
            if (arr[z] > param) {
                end = z - 1;
            } else if (arr[z] < param) {
                begin = z + 1;
            } else {
                return z;
            }
        }
    }
    public void insert(long param) {
        int j;
        for (j = 0; j < item; j++) {
            if (param < arr[j]) {
                break;
            }
        }
        for (int i = item; i > j; i--) {
            arr[i] = arr[i - 1];
        }
        arr[j] = param;
        item++;
    }

}

線性查找

二分查找

image.png

①罢维、插入快壳坪，對于無序數(shù)組俊卤，上面我們實現(xiàn)的數(shù)組就是無序的伸但，即元素沒有按照從大到小或者某個特定的順序排列籽御，只是按照插入的順序排列肢执。無序數(shù)組增加一個元素很簡單枉阵，只需要在數(shù)組末尾添加元素即可，但是有序數(shù)組卻不一定了预茄，它需要在指定的位置插入兴溜。

②、查找慢耻陕，當然如果根據(jù)下標來查找是很快的拙徽。但是通常我們都是根據(jù)元素值來查找，給定一個元素值诗宣，對于無序數(shù)組膘怕，我們需要從數(shù)組第一個元素開始遍歷，直到找到那個元素召庞。有序數(shù)組通過特定的算法查找的速度會比無需數(shù)組快岛心。

③、刪除慢篮灼，根據(jù)元素值刪除忘古，我們要先找到該元素所處的位置，然后將元素后面的值整體向前面移動一個位置诅诱。也需要比較多的時間髓堪。

④、數(shù)組一旦創(chuàng)建后，大小就固定了旦袋，不能動態(tài)擴展數(shù)組的元素個數(shù)骤菠。如果初始化你給一個很大的數(shù)組大小它改，那會白白浪費內(nèi)存空間疤孕，如果給小了，后面數(shù)據(jù)個數(shù)增加了又添加不進去了央拖。

排序算法

冒泡排序

1120165-20171127133255253-740132953.gif

　　冒泡算法的運作規(guī)律如下：
①祭阀、比較相鄰的元素。如果第一個比第二個大鲜戒，就交換他們兩個专控。
②、對每一對相鄰元素作同樣的工作遏餐，從開始第一對到結(jié)尾的最后一對伦腐。這步做完后，最后的元素會是最大的數(shù)（也就是第一波冒泡完成）失都。
③柏蘑、針對所有的元素重復(fù)以上的步驟，除了最后一個粹庞。
④咳焚、持續(xù)每次對越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對數(shù)字需要比較庞溜。

image.png

    public void sort() {
        for (int i = item; i > 0; i--) {
            for (int j = 1; j < i; j++) {
                if (arr[j] < arr[j - 1]) {
                    swap(j, j - 1);
                }
            }
            dispaly();
        }
    }

    private void swap(int in, int out) {
        long temp = arr[in];
        arr[in] = arr[out];
        arr[out] = temp;
    }

[2,7,5,8,9,1,4,6,3,0]
第0輪   [2,5,7,8,1,4,6,3,0,9]
第1輪   [2,5,7,1,4,6,3,0,8,9]
第2輪   [2,5,1,4,6,3,0,7,8,9]
第3輪   [2,1,4,5,3,0,6,7,8,9]
第4輪   [1,2,4,3,0,5,6,7,8,9]
第5輪   [1,2,3,0,4,5,6,7,8,9]
第6輪   [1,2,0,3,4,5,6,7,8,9]
第7輪   [1,0,2,3,4,5,6,7,8,9]
第8輪   [0,1,2,3,4,5,6,7,8,9]
第9輪   [0,1,2,3,4,5,6,7,8,9]

冒泡排序性能分析：

假設(shè)參與比較的數(shù)組元素個數(shù)為 N革半，則第一輪排序有 N-1 次比較，第二輪有 N-2 次流码，如此類推又官，這種序列的求和公式為：

（N-1）+（N-2）+...+1 = N*（N-1）/2
　　交換和比較次數(shù)都和N2 成正比。由于常數(shù)不算大 O 表示法中漫试，忽略 2 和 4赏胚，那么冒泡排序運行都需要 O(N2) 時間級別。

![1120165-20171127155327269-315485975.gif](https://upload-images.jianshu.io/upload_images/18860946-02d0f643149fda20.gif?imageMogr2/auto-orient/strip)

選擇排序

1120165-20171127155256315-1517098862.gif

　　選擇排序是每一次從待排序的數(shù)據(jù)元素中選出最小的一個元素商虐，存放在序列的起始位置觉阅，直到全部待排序的數(shù)據(jù)元素排完。

分為三步：

①秘车、從待排序序列中典勇，找到關(guān)鍵字最小的元素
②、如果最小元素不是待排序序列的第一個元素叮趴，將其和第一個元素互換
③割笙、從余下的 N - 1 個元素中，找出關(guān)鍵字最小的元素，重復(fù)(1)伤溉、(2)步般码，直到排序結(jié)束

image.png

    public void sort() {
        for (int i = 0; i < item; i++) {
            int min = i;
            for (int j = i + 1; j < item; j++) {
                if (arr[j] < arr[min]) {
                    min = j;
                }
            }
            swap(i, min);

            dispaly();
        }
    }

[2,7,5,8,9,1,4,6,3,0]
第0輪   [0,7,5,8,9,1,4,6,3,2]
第1輪   [0,1,5,8,9,7,4,6,3,2]
第2輪   [0,1,2,8,9,7,4,6,3,5]
第3輪   [0,1,2,3,9,7,4,6,8,5]
第4輪   [0,1,2,3,4,7,9,6,8,5]
第5輪   [0,1,2,3,4,5,9,6,8,7]
第6輪   [0,1,2,3,4,5,6,9,8,7]
第7輪   [0,1,2,3,4,5,6,7,8,9]
第8輪   [0,1,2,3,4,5,6,7,8,9]
第9輪   [0,1,2,3,4,5,6,7,8,9]

選擇排序性能分析：

選擇排序和冒泡排序執(zhí)行了相同次數(shù)的比較：N*（N-1）/2，但是至多只進行了N次交換乱顾。

當 N 值很大時板祝，比較次數(shù)是主要的，所以和冒泡排序一樣走净，用大O表示是O(N2) 時間級別券时。但是由于選擇排序交換的次數(shù)少，所以選擇排序無疑是比冒泡排序快的伏伯。當 N 值較小時橘洞，如果交換時間比選擇時間大的多，那么選擇排序是相當快的说搅。

插入排序

1120165-20171127155327269-315485975.gif

直接插入排序基本思想是每一步將一個待排序的記錄炸枣，插入到前面已經(jīng)排好序的有序序列中去，直到插完所有元素為止

image.png

   public void sort() {
        //從下標1開始循環(huán)
        for (int i = 1; i < item; i++) {
            long temp = arr[i];//記錄要插入的值
            int j = i;
            while (j > 0 && arr[j - 1] >= temp) {//找到比要插入的值要大的數(shù)
                arr[j] = arr[j - 1];//大數(shù)向后移動
                j--;
            }
            arr[j] = temp;//插入數(shù)據(jù)

            dispaly();
        }
    }

[2,7,5,8,9,1,4,6,3,0]
第1輪   [2,7,5,8,9,1,4,6,3,0]
第2輪   [2,5,7,8,9,1,4,6,3,0]
第3輪   [2,5,7,8,9,1,4,6,3,0]
第4輪   [2,5,7,8,9,1,4,6,3,0]
第5輪   [1,2,5,7,8,9,4,6,3,0]
第6輪   [1,2,4,5,7,8,9,6,3,0]
第7輪   [1,2,4,5,6,7,8,9,3,0]
第8輪   [1,2,3,4,5,6,7,8,9,0]
第9輪   [0,1,2,3,4,5,6,7,8,9]

插入排序性能分析：

在第一輪排序中弄唧，它最多比較一次适肠，第二輪最多比較兩次，一次類推套才，第N輪迂猴，最多比較N-1次。因此有 1+2+3+...+N-1 = N*（N-1）/2背伴。

假設(shè)在每一輪排序發(fā)現(xiàn)插入點時沸毁，平均只有全體數(shù)據(jù)項的一半真的進行了比較，我們除以2得到：N*（N-1）/4傻寂。用大O表示法大致需要需要 O(N2) 時間級別息尺。

復(fù)制的次數(shù)大致等于比較的次數(shù)，但是一次復(fù)制與一次交換的時間耗時不同疾掰，所以相對于隨機數(shù)據(jù)搂誉，插入排序比冒泡快一倍，比選擇排序略快静檬。

這里需要注意的是炭懊，如果要進行逆序排列，那么每次比較和移動都會進行拂檩，這時候并不會比冒泡排序快侮腹。

快速排序

1258817-20190325195811497-310078615.jpg

快速排序的基本思路
　　一、先通過第一趟排序稻励，將數(shù)組原地劃分為兩部分父阻，其中一部分的所有數(shù)據(jù)都小于另一部分的所有數(shù)據(jù)。原數(shù)組被劃分為2份

二、通過遞歸的處理加矛，再對原數(shù)組分割的兩部分分別劃分為兩部分履婉，同樣是使得其中一部分的所有數(shù)據(jù)都小于另一部分的所有數(shù)據(jù)。這個時候原數(shù)組被劃分為了4份

三斟览、就1,2被劃分后的最小單元子數(shù)組來看毁腿，它們?nèi)匀皇菬o序的，但是趣惠！它們所組成的原數(shù)組卻逐漸向有序的方向前進狸棍。

四身害、這樣不斷劃分到最后味悄，數(shù)組就被劃分為多個由一個元素或多個相同元素組成的單元，這樣數(shù)組就有序了塌鸯。

![1258817-20190325195811497-310078615.jpg](https://upload-images.jianshu.io/upload_images/18860946-aee76c6a4f4dc287.jpg?imageMogr2/auto-orient/strip)

private void quickSort(int start, int end) {
        long temp = arr[start];
        int i = start;
        int j = end;
        System.out.println("start:"  +  start + " end:" + end);
        while (i < j) {
            while (i < j && arr[j] > temp) {
                j--;
            }
            while (i < j && arr[i] < temp) {
                i++;
            }
            if (i < j && arr[i] == arr[j]) {
                i++;
            } else {
                swap(i, j);
            }
        }
        dispaly();
        if (i - 1 > start) {
            quickSort(start, i - 1);
        }
        if (j + 1 < end) {
            quickSort(j + 1, end);
        }
    }

[2,7,5,8,9,1,4,6,3,0]
start:0 end:9
[0,1,2,8,9,5,4,6,3,7]
start:0 end:1
[0,1,2,8,9,5,4,6,3,7]
start:3 end:9
[0,1,2,7,3,5,4,6,8,9]
start:3 end:7
[0,1,2,6,3,5,4,7,8,9]
start:3 end:6
[0,1,2,4,3,5,6,7,8,9]
start:3 end:5
[0,1,2,3,4,5,6,7,8,9]

希爾排序

1940317-0f04f8b6aec097bb.gif

希爾排序應(yīng)運而生了侍瑟，希爾排序通過加大插入排序中元素的間隔，并在這些有間隔的元素中進行插入排序丙猬，從而使數(shù)據(jù)項能夠大跨度的移動涨颜。當這些數(shù)據(jù)項排過一趟序后，希爾排序算法減小數(shù)據(jù)項的間隔再進行排序茧球，依次進行下去庭瑰，最后間隔為1時，就是我們上面說的簡單的直接插入排序抢埋。

image.png

public void sort() {
        int gap = item;
        while (true) {
            gap /= 2.2;   //增量每次減半
            for (int i = 0; i < gap; i++) {
                for (int j = i + gap; j < item; j += gap) {//這個循環(huán)里其實就是一個插入排序
                    long temp = arr[j];
                    int k = j - gap;
                    while (k >= 0 && arr[k] > temp) {
                        arr[k + gap] = arr[k];
                        k -= gap;
                    }
                    arr[k + gap] = temp;
                }

            }
            System.out.println("增量為 "+gap);
            dispaly();
            if (gap == 1)
                break;
        }
    }

[2,7,5,8,9,1,4,6,3,0]
增量為 4
[2,0,4,6,3,1,5,8,9,7]
增量為 1
[0,1,2,3,4,5,6,7,8,9]

地精排序

號稱最簡單的排序算法,只有一層循環(huán),默認情況下前進冒泡,一旦遇到冒泡的情況發(fā)生就往回冒,直到把這個數(shù)字放好為止

    public void sort() {
        int j = 1;
        while (j < item) {
            if (j == 0 || arr[j] > arr[j - 1]) {
                j++;
            } else {
                swap(j, j - 1);
                j--;
            }
        }
    }