InterviewBit-Day3

发表于 | 分类于
| 字数统计 770 | 阅读时长 4

Sorting

Selection Sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class SelectionSort{
    public static void main(String[] args) {
        int[] A = {3, 4, 2, 5, 8, 1};
        int[] B = selectionSort(A);
        for (int b : B) {
            System.out.print(b + " ");
        }
    }

    private static int[] selectionSort(int[] A) {
        int len = A.length;
        for (int i = 0; i < len - 1; i++) {
            int iMin = i;
            for (int j = i + 1; j < len; j++) {
                if (A[j] < A[iMin]) {
                    iMin = j;
                }
            }

            int temp = A[i];
            A[i] = A[iMin];
            A[iMin] = temp;
        }
        return A;
    }
}

时间复杂度分析：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
for (int i = 0; i < len - 1; i++)  --> c1

for (int j = i + 1; j < len; j++)  --> c2
    -->  i = 0  ==>  n - 1
    -->  i = 1  ==>  n - 2
     .     .     .     .
    -->  i = n - 1  ==>  1

int temp = A[i];
A[i] = A[iMin];                   --> c3
A[iMin] = temp;

T(n) = n * c1 + n(n-1)/2 * c2 + n * c3
     = an^2 + bn + c
     = O(n^2)

Bubble Sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
private static int[] bubbleSort(int[] A) {
    int len = A.length;
    for (int i = 1; i < len; i++) {
        int flag = 0;
        for (int j = 0; j < len - i; j++) {
            if (A[j] > A[j + 1]) {
                int temp = A[j + 1];
                A[j + 1] = A[j];
                A[j] = temp;
                flag = 1;
            }
        }
        if (flag == 0) {
            break;
        }
    }
    return A;
}

时间复杂度分析：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// worst
int temp = A[j + 1];
A[j + 1] = A[j];                        --> c
A[j] = temp;
  -->  i = 1  ==>  n - 1
  -->  i = 2  ==>  n - 1
   .     .     .     .
  -->  i = n - 1  ==>  n - 1

T(n) = (n - 1)*(n - 1)*c
     = cn^2 - 2cn - c
     = O(n^2)

// best
T(n) = O(n)
      
// average
T(n) = O(n^2)

Insertion Sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
private static int[] insertionSort(int[] A) {
    int len = A.length;
    for (int i = 1; i < len; i++) {
        int value = A[i];
        int hole = i;
        while (hole > 0 && A[hole - 1] > value) {
            A[hole] = A[hole -1];
            hole--;
        }
        A[hole] = value;
    }
    
    return A;
}

时间复杂度分析：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int value = A[i];
int hole = i;                      -->  c1

A[hole] = A[hole - 1];
hole--;                            -->  c2

A[hole] = value;                   -->  c3

// best
T(n) = (c1 + c3)*(n - 1)
     = an + b
     = O(n)
    
// worst
T(n) = (c1 + c3)*(n - 1) + [1 + 2 + 3 + ... + (n - 1)]*c2
     = an^2 + bn + c
     = O(n^2)
    
// average
T(n) = O(n^2)

Merge Sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
private static int[] mergeSort(int[] A) {
    int n = A.length;
    if (n < 2) {
        return A;
    }
    int mid = n / 2;
    int[] left = new int[mid];
    int[] right = new int[n - mid];
    for (int i = 0; i < mid; i++) {
        left[i] = A[i];
    }
    for (int j = mid; j < n; j++) {
        right[j - mid] = A[j];
    }
    mergeSort(left);
    mergeSort(right);
    merge(left, right, A);
    return A;
}

private static int[] merge(int[] left, int[] right, int[] A) {
    int leftLen = left.length, rightLen = right.length;
    int i = 0, j = 0, k = 0;
    while (i < leftLen && j < rightLen){
        if (left[i] < right[j]){
            A[k] = left[i];
            i++;
        } else {
            A[k] = right[j];
            j++;
        }
        k++;
    }
    while (i < leftLen) {
        A[k] = left[i];
        i++;
        k++;
    }
    while (j < rightLen) {
        A[k] = right[j];
        j++;
        k++;
    }
    
    return A;
}

时间复杂度分析：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
int n = A.length;
if (n < 2) {
    return A;
}                                        -->  c1
int mid = n / 2;
int[] left = new int[mid];
int[] right = new int[n - mid];


for (int i = 0; i < mid; i++) {
    left[i] = A[i];
}                                       -->  n*c2
for (int j = mid; j < n; j++) {
    right[j - mid] = A[j];
}

mergeSort(left);                        -->  T(n/2)
mergeSort(right);                       -->  T(n/2)
    
merge(left, right, A);                  -->  n*c3 + c4

T(n) = c1 + n*c2 + 2T(n/2) + n*c3 + c4
     = 2T(n/2) + n*(c2 + c3) + (c1 + c4)
     = 2T(n/2) + n*c  (n >= 2)
T(n) = c (n = 1)

T(n) = 2T(n/2) + n*c
     = 2[2T(n/4) + n/2*c] + n*c
     = 4T(n/4) + 2n*c
     = 4[2T(n/8) + n/4*c] + 2n*c
     = 8T(n/8) + 3n*c
     ...
     = 2^k*T(n/(2^k)) + k*n*c
     
令 n/(2^k) = 1 则： 2^k = n，k = log2n
T(n) = 2^(log2n)*T(1) + log2n*n*c
     = n*c + n*c*log2n
     = n*c*log2n
     = O(nlog2n)
0%