JAVA基礎知識点復習(五)配列と並べ替え

アウトライン

1次元配列

二次元配列

バブルソート

単純選択ソート

クイックソート

二分検索

このシリーズの博文は主に自分が前に勉強したjavaの基礎内容をまとめ、まとめています.
1 D配列
配列は、同じタイプの複数のデータを格納し、0から番号付けし、要素の操作を番号(インデックス)で完了します.
配列が定義されると、使用するメモリ領域が固定されるため、配列は可変ではありません.
1次元配列定義方式は3種類あり,2,3種類の書き方が一般的である.

// （ ）     
int[] arr = new int[]{1,2,3};
// （ ）     
int[] arr1 = {1,2,3};
// （ ）     
int[] arr2 = new int[3];

//        ，      ，             
System.out.println(arr2.length);

//   
for (Integer val : arr) {
    System.out.print(val);
}

//          
System.out.println(Arrays.toString(arr))；

2 D配列2 Dはいれつ
配列のネスト配列、2、3種類の書き方が一般的です

// （ ）     
int[][] arrs = new int[][]{{1}, {2, 3}, {4, 5, 6}};
// （ ）     
int[][] arrs1 = {{}, {}, {}};
// （ ）     
int[][] arrs2 = new int[2][3];
// （ ）                  
int[][] arrs3 = new int[3][];

System.out.println(arrs.length); //        

//   
for (int[] arr : arrs) {
    for (Integer val : arr) {
        System.out.print(val);
    }
}

//          
System.out.println(Arrays.deepToString(arrs));

2 D配列は実際には1つの行列であり、動的初期化にとってnew int[][]の最初の[]はこの2 D配列の中に何個の1次元配列があるかを表し、2番目の[]は1次元配列の容量を表し、最初の[]は空ではない
もちろんN次元配列を定義することもできます[犬頭]

int[][][][][] i = new int[2][2][2][2][2];
System.out.println(Arrays.deepToString(i));

ちょっと変な書き方

int x []; //    
int x1 [][]; //    
int [] x2 []; //    
int[] x3, y[]; // x3     ，y     

バブルソート
2つの隣接する要素を並べ替え、最大(最小)を最後に配置します.
時間複雑度O(N^2)
1回目の内サイクルはn−1回、次いでn−2回、n−3回、・・・、最後の内サイクルは1回比較される.
等差数列加算(((n−1)＋1)(n−1)／2＝n(n−1)／2((n−1)＋1)(n−1)／2＝n(n−1)／2(((n−1)＋1)(n−1)／2＝n(n−1)／2 BigO表現:最高項のみを保持し,最高項定数を除去する
最終導出はO(N^2)

private static void bubbleSort(int[] arr){
        for (int i=0; i<arr.length-1; i++) {
            for (int j=0; j<arr.length-1-i; j++) {
                if(arr[j] > arr[j+1]){
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
    }

単純選択ソート
i番目の桁数をその後のすべての数と比較し、より小さい(より大きい)ものに遭遇した場合はその角標を記憶し、各ラウンドが終了して角標が変動した場合は交換し、i番目の数は最小(最大)である
時間複雑度O(N^2)
1回目の内サイクルはn−1回、次いでn−2回、n−3回、・・・、最後の内サイクルは1回比較される.
等差数列と((n−1)+1)(n−1)/2=n(n−1)/2((n−1)+1)(n−1)/2=n(n−1)/2((n−1)+1)(n−1)/2=n(n−1)/2=n(n−1)/2を求めて最終的にO(N^2)と導いた.

private static void selectSort(int[] arr){
    for (int i = 0; i < arr.length - 1; i++) {
        int index = i;
        for (int j = i+1; j < arr.length; j++) {
            if (arr[index] > arr[j]) {
                index = j;
            }
        }
        if (index != i) {
            int temp = arr[i];
            arr[i] = arr[index];
            arr[index] = temp;
        }
    }
}

クイックソート
時間複雑度O(Nlogn)ポインタ交換法

private static void quickSort(int[] arr, int left, int right){
        if(left >= right){
            return;
        }
        //    i,    j,    pivot
        int i = left, j = right, pivot = arr[i];
    	//     j  ，  ij             ，  i            
        while(i < j){
            // j               
            while (arr[j] >= pivot && i < j) {
                j--;
            }
            // i               
            while (arr[i] <= pivot && i < j){
                i++;
            }
            //         
            if(i < j){
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        //               ，           
        arr[left] = arr[i];
        arr[i] = pivot;
        //       
        quickSort(arr, left, i - 1);
        //       
        quickSort(arr, i + 1, right);
    }

にぶんたんさく

private static int binarySearch(int[] arr, int key){

        int min = 0, mid, max = arr.length-1;
        while(min <= max){
            mid = (min + max)/2;
            if(key > arr[mid]){
                min = mid + 1;
            }else if(key < arr[mid]){
                max = mid - 1;
            }else {
                return mid;
            }
        }
        return -1;
    }