資料結構-排序

說明：觀看B站視訊記錄筆記（馬士兵說）

資料結構緒論

什麼是資料結構

1. Data Structure
2. 存儲資料的不同方式（順序表、連結清單）

什麼是算法

1. 同一問題的不同解決方法
2. 算法往往是針對特定的資料結構（數組和連結清單的插入方法）

如何測算算法的優劣

1. 時間測算

   java

   中記錄算法開始的時間before=System.currentTimeMillis()，算法結束時記錄一個時間，然後相減，一次算法可能不好比較，用循環來湊。比如循環

   10000

   次。
   1. 計算算法時間差
   2. 幅度不夠循環來湊

2. 空間測算

   用到的額外空間

Big O

1. 時間 -問題（資料）規模

   1. 不考慮必須要做的操作

      循環、賦初值、程式初始化…

   2. 不考慮常數項
   3. 不考慮低次項

      

      作業：

      

      回答：O(1)、O(N)、O(N)、O(N)

排序

常見排序：

插排、堆排、快排、歸并四種必須記

選泡插， 快歸堆希統計基， 恩方恩老恩一三， 對恩加K恩乘K， 不穩穩穩不穩穩， 不穩不穩穩穩穩！

選擇排序

最簡單但是最沒用的排序算法，也有優化空間

如何計算時間和空間複雜度

算法的驗證-随機誰生成器、對數器

寫算法程式的哲學

package mashibing_class.sorts;

public class SeletcionSort {

    /*
     * 如何寫程式：
     * 1、由簡單到複雜
     *   1. 驗證一步走一步
     *   2. 多列印中間結果
     * 2、先局部後整體
     *   沒思路時先細分
     * 3、先粗糙後精細
     *   1. 變量更名
     *   2.語句合并
     *   3.邊界處理
     * */

    public static void main(String[] args) {
        int[] arr = {5, 3, 6, 8, 1, 7, 9, 4, 2};
        for(int i =0;i<arr.length-1;i++){
            int minPos=i;
            for (int j=i+1;j<arr.length;j++){
            // minPos = arr[j] < arr[minPos] ? j : minPos;
                if (arr[j]<arr[minPos])
                    minPos=j;
            }
            swap(arr,i,minPos);
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }

    public static void swap(int []arr,int i,int j){
        int temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }

    /*
    * 選擇排序還可以優化，可以一次循環找到一個最小值和最大值，最小值放到最前面，最大值放到最後面。循環次數少一半。
    * */
}

           

對數器

package mashibing_class.sorts;

import java.util.Arrays;
import java.util.Random;

public class DataChecker {
    /*
     * 驗證算法：對數器
     * 如何驗算算法是否正确？
     *   1. 肉眼觀察
     *   2. 産生足夠多的随機樣本
     *   3. 用确定正确的算法計算樣本結果
     *   4. 對比被驗證算法的結果
     * */
    static int[] generateRandomArray() {
        Random r = new Random();
        int[] arr = new int[10000];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = r.nextInt(10000);
        }
        return arr;
    }

    static void check() {
        int[] arr = generateRandomArray();
        int[] arr2 = new int[arr.length];
        System.arraycopy(arr, 0, arr2, 0, arr.length);//數組拷貝一份
        Arrays.sort(arr);
        SeletcionSort.sort(arr2);
        boolean same = true;
        for (int i = 0; i < arr2.length; i++) {
//            same = arr[i] != arr2[i] ? false : same;
            if (arr[i]!=arr2[i]) same=false;
        }
        System.out.println(same == true ? "right" : "wrong");
        SeletcionSort.printResult(arr2);
    }

    public static void main(String[] args) {
        check();
    }

}

           

選擇排序作業

冒泡排序

package mashibing_class.sorts;

public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = {9, 3, 1, 4, 6, 8, 7, 5, 2};
        sort(arr);
        //sort2(arr);
        printResult(arr);
    }
    static void sort(int[] arr) {
//        for (int i = 0; i <arr.length-1;i++)
//            //最大冒到尾部
//            for (int j=0;j<arr.length-i-1;j++){
//                if (arr[j]>arr[j+1])
//                    swap(arr,j,j+1);
//            }
        for (int i=0;i<arr.length-1;i++)
            for (int j = arr.length - 1; j > i; j--) {
                if (arr[j] < arr[j - 1]) swap(arr, j, j - 1);
            }
    }

    static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    static void printResult(int[] arr) {
        for (int i=0;i<arr.length;i++)
            System.out.print(arr[i]+" ");
    }
	 static void sort2(int[]arr){
	        for(int i=arr.length-1;i>0;i--)
	            findMax(arr,i);
	    }
    static void findMax(int[]arr,int n){
        //前n個數求最大值
        for(int i=0;i<n;i++)
            if (arr[i]>arr[i+1]) swap(arr,i,i+1);
    }

}
           

冒泡排序最好的時間複雜度是O(n),以上算法分析均是O(n^2),是以冒泡

還有優化代碼

。

答：加入判斷數組是否已經有序，直接周遊一次，不交換即是O(n)

插入排序(簡單排序中最後一種排序)

對于基本有序的數組最好用

穩定

package mashibing_class.sorts;

public class InsertSort {
    public static void main(String[] args) {
        int[] arr = {9, 3, 1, 4, 6, 8, 7, 5, 2};
        sort(arr);
        printResult(arr);
    }
    static void sort(int[] arr) {
        //從index=1開始比較前面一個數大小，index之前都有序
        //arr[index]<arr[index-1],arr[index-1]往後挪;index--,直到arr[index]>=arr[index-1]
        int i, j;
        for (i = 1; i < arr.length; i++) {
            int insertNum = arr[i];
//            System.out.println("i: " + i + " inserNum: " + insertNum);
            for (j = i; j > 0; j--)
                if (insertNum < arr[j - 1])
                    arr[j] = arr[j - 1];
                else break;
//            System.out.println("j="+j);
            arr[j] = insertNum;
        }

//        馬老師代碼
//        for (int m=1;m<arr.length;m++)
//            for (int n=m;n>0;n--)
//                if (arr[n]<arr[n-1])
//                    swap(arr,n,n-1);
    }
    static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    static void printResult(int[] arr) {
        for (int i = 0; i < arr.length; i++)
            System.out.print(arr[i] + " ");
    }
}
           

插入排序作業

插入排序比冒泡快一半，一般也比選擇排序好

簡單排序算法總結

1. 冒泡

   基本不用，太慢；最好O(n),最差(n^2).

2. 選擇

   基本不用，不穩

3. 插入

   樣本小且基本有序的時候效率比較高

希爾排序

更加進階的排序，希爾排序是插入排序的一個改進版

package mashibing_class.sorts;

public class ShellSort {
    public static void main(String[] args) {
        //間隔大時，移動次數少
        //間隔小時，移動距離短
        //是以比插入排序好
        /*
         * 希爾排序
         *   1.選擇一個間隔，每一個組排好序
         *   2.選擇更小的間隔，每個組排好序
         *   3.直到間隔為1，插入排序（此時基本有序，插入排序效率高）
         * */
        int[] arr = {9, 6, 11, 3, 5, 12, 8, 7, 10, 15, 14, 4, 1, 13, 2};
//        sort(arr);
        sort(arr);
        printResult(arr);
    }

    static void sort(int[] arr) {
//        int gap = 4;
//        for (int gap = 4; gap > 0; gap /= 2)
        for (int gap = arr.length >> 1; gap > 0; gap /= 2)
            //普通插入排序-->有間隔排序
            for (int i = gap; i < arr.length; i++) {
                for (int j = i; j > gap - 1; j -= gap) {
                    if (arr[j] < arr[j - gap])
                        swap(arr, j, j - gap);
                }
            }
    }

    static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    static void printResult(int[] arr) {
        for (int i = 0; i < arr.length; i++)
            System.out.print(arr[i] + " ");
    }
}
           

Knuth序列

寫程式時，不熟悉可以先試試固定間隔gap,然後二分（希爾思想）===》進一步改進的序列

Knuth序列

。

1. h=1 最小為1

2. h=3*h+1 後面的序列

   1,4,13…

static void sort(int[] arr) {
//        int gap = 4;
//        for (int gap = 4; gap > 0; gap /= 2)
//        for (int gap = arr.length >> 1; gap > 0; gap /= 2)
        int h = 1;
        while (h <= arr.length / 3) {
            h = h * 3 + 1;
        }
        //普通插入排序-->有間隔排序
        for (int gap=h;gap>0;gap=(gap-1)/3)
        for (int i = gap; i < arr.length; i++) {
            for (int j = i; j > gap - 1; j -= gap) {
                if (arr[j] < arr[j - gap])
                    swap(arr, j, j - gap);
            }
        }
    }
           

希爾排序複雜度

時間複雜度 最好O(n^1.3)

空間複雜度O(1)

希爾排序作業

歸并排序

遞歸

package mashibing_class.sorts;

public class Recursion {
    public static void main(String[] args) {
        //遞歸
        System.out.println();
    }
    static long f(int n) {
        if (n < 1)
            return -1;
        if (n == 1)
            return 1;
        return n + f(n - 1);
    }
}
           

歸并排序

static void merge(int[] arr) {
        int mid = arr.length >> 1;
        int i = 0, j = mid + 1;
        int[] helpArray = new int[arr.length];
        int k = 0;
        while (i <= mid && j < =arr.length) {
//            if (arr[i] <= arr[j])
//                helpArray[k++] = arr[i++];
//            else helpArray[k++] = arr[j++];
            helpArray[k++]=arr[i]<arr[j]?arr[i++]:arr[j++];
        }
        while (i <= mid) helpArray[k++] = arr[i++];
        while (j < arr.length) helpArray[k++] = arr[j++];
        System.out.println("\nmerge後：");
        printResult(helpArray);
        System.out.println();
    }
           

package mashibing_class.sorts;
public class MergeSort {
    //TIM Sort
    //Java 内置排序
    public static void main(String[] args) {
        int[] arr = {1, 4, 6, 7, 10, 11, 3, 5, 8, 9};
//        int[] arr = {1,4,7,8,3,6,9};
        System.out.println("merge前：");
        printResult(arr);
//        sort(arr);
        sort(arr,0,arr.length);
        System.out.println("\nmerge後：");
        printResult(arr);

    }
    static void sort(int[] arr,int left,int right) {
//        merge(arr);
//        merge2(arr,0,arr.length>>1,arr.length);
        //base case
        if (left==right)    return;
        //分成兩半，
        int mid=left+(right-left)/2;//防止越界
        // 左邊排序，
        sort(arr,left,mid);
        // 右邊排序
        sort(arr,mid+1,right);
        merge2(arr,left,mid,right);
    }
    static void merge(int[] arr) {
        int mid = arr.length >> 1;
        int i = 0, j = mid + 1;
        int[] helpArray = new int[arr.length];
        int k = 0;
        while (i <= mid && j < arr.length) {
//            if (arr[i] <= arr[j])
//                helpArray[k++] = arr[i++];
//            else helpArray[k++] = arr[j++];
            helpArray[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
        }
        while (i <= mid) helpArray[k++] = arr[i++];
        while (j < arr.length) helpArray[k++] = arr[j++];
        System.out.println("\nmerge後：");
        printResult(helpArray);
        System.out.println();
    }

    static void merge2(int[]arr,int left,int mid,int right){
        //上面merge不夠靈活
        int []helpArray=new int[right-left];
        int i=left,j=mid+1,k=0;
        while (i<=mid&&j<right)
            helpArray[k++]=arr[i]<arr[j]?arr[i++]:arr[j++];
        while (i<=mid) helpArray[k++]=arr[i++];
        while (j<right) helpArray[k++]=arr[j++];
//        System.out.println("\nmerge後：");
//        printResult(helpArray);
//        System.out.println();

        for (int m=0;m<helpArray.length;m++){
            arr[left+m]=helpArray[m];
        }
    }
    static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    static void printResult(int[] arr) {
        for (int i = 0; i < arr.length; i++)
            System.out.print(arr[i] + " ");
    }
}
           

java對象排序

1. 對象排序一般要求穩定（TimSort改進的排序）

   

快速排序

package mashibing_class.sorts;

public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {9, 3, 1, 4, 10, 6, 8, 7, 5, 11};
        System.out.println("排序前：");
        printArray(arr);
        sort(arr, 0, arr.length - 1);
        System.out.println("\n排序後:");
        printArray(arr);
    }

    static void sort(int[] arr, int left, int right) {
        if (left > right) return;
        int mid = partition(arr,left,right);
//        System.out.println("mid"+mid);;
        sort(arr,left,mid-1);
        sort(arr,mid+1,right);

    }

    static int  partition(int[] arr, int left, int right) {
//        int pivot = arr[mid];
        int pivot=arr[right];
        int rightBound=right;
//        System.out.println("\nrightBound:"+rightBound);
//        System.out.println("pivot:" + pivot);
        while (left < right) {
            while (left < right && arr[left] <= pivot) left++;
            while (left < right && arr[right] >= pivot) right--;
            if (left<right)
                swap(arr, left, right);
//            System.out.println("left:"+left+" right:"+right);
        }
//        System.out.println(arr[left]+"  "+arr[rightBound]);
        swap(arr,left,rightBound);
        return left;
    }

    static void swap(int[] arr, int i, int j) {
        int temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
        //異或運算交換兩個數
//        arr[i] = arr[i] ^ arr[j];
//        arr[j] = arr[i] ^ arr[j];
//        arr[i] = arr[j] ^ arr[i];
    }

    static void printArray(int[] arr) {
        for (int i = 0; i < arr.length; i++)
            System.out.print(arr[i] + " ");
    }
}

           

雙軸快排

選兩個數，第一個數比第二數小。分為三個區域，小于第一個區域的數，介于中間的區域，大于第二個數的區域

less,mid,more

計數排序

1. 非比較排序
2. 桶思想的一種

算法思想

1. 量大但是範圍小
   1. 某大型企業數萬名員工年齡排序
   2. 如何快速得知聯考名次（騰訊面試）

      

package mashibing_class.sorts;

import java.util.Arrays;

public class CountSort {
    public static void main(String[] args) {
        int[] arr = {2, 4, 2, 3, 7, 1, 1, 0, 0, 5, 6, 9, 8, 5, 7, 4, 0, 9};
        int[] result = sort(arr);
        System.out.println(Arrays.toString(result));
    }
    static int[] sort(int[] arr) {
        int[] result = new int[arr.length];
        int[] count = new int[10];
        for (int i = 0; i < arr.length; i++) {
            count[arr[i]]++;
        }
        System.out.println(Arrays.toString(count));
        for (int i = 0, j = 0; i < count.length && j < result.length; i++) {
            while ((count[i]--)>0)
                result[j++]=i;
        }
        return result;
    }
}
           

現在程式有兩個小bug：

1. 範圍不是從零開始
2. 穩定性，現在是不穩定的。（用累加數組進行排序）

static int[] sort(int[] arr) {
        int[] result = new int[arr.length];
        int[] count = new int[10];
        int[] reverseCount = new int[10];

        for (int i = 0; i < arr.length; i++) {
            count[arr[i]]++;
        }
        System.out.println(Arrays.toString(count));
        //累加數組
        for (int j = 1; j < count.length; j++) {
            count[j] = count[j] + count[j - 1];
        }
        System.out.println(Arrays.toString(count));
        for (int k = arr.length-1; k >= 0; k--) {
            result[--count[arr[k]]]=arr[k];
        }
        return result;
    }
           

總結：

1. 計數排序是非比較排序
2. 适用于特定問題，也就是對源資料有要求
3. O(n+k)

基數排序

1. 非比較排序
2. 桶思想的一種
3. 多關鍵字排序

package mashibing_class.sorts;

import java.util.Arrays;

public class RadixSort {
    public static void main(String[] args) {
        int[] arr = {421, 240, 115, 532, 305, 430, 124};
        //判斷最高位數
        int levels = 0;
        for (int i = 0; i < arr.length; i++) {
            levels = 0;
            for (int temp = arr[i]; temp > 0; temp /= 10)
                levels++;
        }
        System.out.println(levels);
        int[] result = sort(arr, levels);
        System.out.println(Arrays.toString(result));
    }

    static int[] sort(int[] arr, int levels) {
        int[] result = new int[arr.length];
        int[] count = new int[10];
        for (int level = 0; level < levels; level++) {
            int division = (int) Math.pow(10, level);
            System.out.println(division);
            for (int i = 0; i < arr.length; i++) {
                int num = arr[i] / division % 10;
                System.out.print(num + " ");
                count[num]++;
            }
            System.out.println();
            System.out.println(Arrays.toString(count));
            for (int j = 1; j < count.length; j++)
                count[j] = count[j] + count[j - 1];
            for (int k = arr.length - 1; k >= 0; k--) {
                int num = arr[k] / division % 10;
                System.out.println("num:" + num);
                result[--count[num]] = arr[k];
            }
            System.arraycopy(result, 0, arr, 0, arr.length);
//            System.out.println(Arrays.toString(arr));

            Arrays.fill(count, 0);//count數組置為0
        }
        return result;
    }
}
           

總結：

1. 本質是一種多關鍵字排序
2. 有低位優先和高位優先兩種
   1. LSD MSD（Least Significant Digit first） (Most)
   2. MSD屬于分治的思想
3. 百度百科的程式有問題
   1. 空間複雜度變高

桶排序

桶排序的算法思想：

1. 求出待排序列最小和最大資料，作差，求出桶的範圍。
2. 然後周遊整個序列，放入各範圍桶。
3. 每個桶進行排序。

   省了時間，空間就省不了，省了空間，時間就省不了