数据结构之八大排序

选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static void selectSort(int[] array) {
    for (int i = 0; i < array.length; i++) {
        int k = i;
        for (int j = k+1; j < array.length; j++) {
            if (array[j] < array[k]) {
                k = j;
            }
        }
        if (i != k) {
            int temp = array[i];
            array[i] = array[k];
            array[k] = temp;
        }
    }
}

public static void main(String args[]) {
    int[] array = {5, 1, 3, 0, 1, 4, 8, 9};
    selectSort(array);
    System.out.println(Arrays.toString(array));
}

简单选择排序的比较次数与序列的初始排序无关。 假设待排序的序列有 N 个元素，则比较次数永远都是N (N - 1) / 2。而移动次数与序列的初始排序有关。当序列正序时，移动次数最少，为 0。当序列反序时，移动次数最多，为3N (N - 1) / 2。

冒泡排序

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

public static void main(String[] args) {
    int[] arr = {6,3,8,2,9,1};
    bubbleSort(arr);
    System.out.println(Arrays.toString(arr));
}

快速排序

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
public static void qsort(int[] array, int low, int high) {
    if (low < high) {
        int pivot = partition(array, low, high);
        qsort(array, low, pivot- 1);
        qsort(array, pivot + 1, high);
    }
}

public static void sort(int[] array) {
    qsort(array, 0, array.length - 1);
}

public static int partition(int array[], int low, int high) {
    int pivot = array[low];
    while (low < high) {
        if (low < high && array[high] >= pivot) {
            high --;
        }
        array[low] = array[high];

        if (low < high && array[low] < pivot) {
            low ++;
        }
        array[high] = array[low];
    }
    array[low] = pivot;
    return low;
}

public static void main(String[] args) {
    int[] a = {4, 1, 9, 2, 0, 1, 3, 5};
    sort(a);
    System.out.println(Arrays.toString(a));
}

插入排序

说明

　插入排序从数组的第二个元素开始循环，将选中的元素与之前的元素一一比较，如果选中的元素小于之前的元素，则将之前的元素后移，最后再将选中的元素放在合适的位置。在这个算法执行的过程中，总是保持着索引i之前的数组是升序排列的。

时间复杂度

首先，插入排序当中有两个循环，假设数组的大小为n，则第一个循环是n－1次，第二个while循环在最坏的情况下是1到n－1次。因此插入排序的时间复杂度大约为如下形式。
1+2+3+4+…＋n－1 ＝ n（n－1）/ 2 ＝ O（n2）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static void insertSort(int[] array) {
    for (int i=1; i<array.length; i++) {
        if (array[i] < array[i-1]) {
            int j;
            int temp = array[i];
            for (j=i-1; j>=0 && temp<array[j]; j--) {
                array[j+1] = array[j];
            }
            array[j+1] = temp;
        }
    }
}

public static void main(String[] args) {
    int[] array = {6,3,8,2,9,1};
    insertSort(array);
    System.out.println(Arrays.toString(array));
}

桶排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 public static int[] bucketSort(int[] array, int max) {
    int[] sorted = new int[max + 1];

    for (int i = 0; i < array.length; i++) {
        sorted[array[i]] = array[i];
    }
    return sorted;
}

public static void main(String[] args) {
    int[] array = {4, 1, 9, 2, 0, 1, 3, 5};
    array = bucketSort(array, 9);
    for (int i=0; i < array.length; i++) {
        if (array[i] > 0) {
            System.out.println(array[i]); 
        }
    }
}

归并排序

说明

归并排序将排序问题拆分，比如分成两个较小的数组，然后对拆分后的数组分别进行排序，最后再将排序后的较小数组进行合并。

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
 public static void sort(int[] arr, int low, int high) {
        int mid = (low + high) / 2;
        if (low < high) {
            sort(arr, low, mid);
            sort(arr, mid + 1, high);
            merge(arr, low, mid, high);
        }
    }

public static void merge(int[] arr, int low, int mid, int high) {
    int[] temp = new int[high - low + 1];

    int i = low;
    int j = mid + 1;
    int k = 0;

    // 把较小的数移入新数组
    while (i <= mid && j <= high) {
        if (arr[i] < arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }
    // 把左边剩余的数移入数组
    while (i <= mid) {
        temp[k++] = arr[i++];
    }
    // 把右边边剩余的数移入数组
    while (j <= high) {
        temp[k++] = arr[j++];
    }
    // 把新数组中的数覆盖nums数组
    for(int x=0; x < temp.length; x++){
        arr[x + low] = temp[x];
    }
}

二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
static public int search(List<Integer> a, int i, int low, int hi) {
    int mid = (hi + low) / 2;
    if (low <= hi) {
        if (i < a.get(mid)) {
            return search(a, i, low, mid -1);
        }
        if (i > a.get(mid)) {
            return search(a, i, mid+1, hi);
        }
        if (i == a.get(mid)) {
            return mid;
        }
    }
    return -1;
}
public static void main(String[] args) {
    int[] a = {1, 2, 3 ,4, 5};
    List<Integer> arr = new ArrayList<>();
    for (int i=0; i < a.length; i++) {
        arr.add(a[i]);
    }
    System.out.println(search(arr, 3, 0, 4));
}