常用排序算法时间复杂度

插入排序

已知待排序的一组记录:60, 71, 49, 11, 82, 49, 3, 66
排序过程如下：

60, 71, 49, 11, 82, 49, 3, 66
[60] 71, 49, 11, 82, 49, 3, 66
[60, 71] 49, 11, 82, 49, 3, 66
[49, 60, 71] 11, 82, 49, 3, 66
[11, 49, 60, 71] 82, 49, 3, 66
[11, 49, 60, 71, 82] 49, 3, 66
[11, 49, 49, 60, 71, 82] 3, 66
[3, 11, 49, 49, 60, 71, 82] 66
[3, 11, 49, 49, 60, 66, 71, 82]

代码实现：

public void insertSort(int[] array) {
    for (int i = 1; i < array.length; i++) {
        for (int j = i; j > 0 && array[j] < array[j - 1]; j--) {
            int temp = array[j];
            array[j] = array[j - 1];
            array[j - 1] = temp;
        }
    }
}

希尔排序

已知待排序的一组记录:60, 71, 49, 11, 82, 49, 3, 66
排序过程如下：

60, 71, 49, 11, 82, 49, 3, 66
60, 49, 49, 11, 82, 71, 3, 66
60, 49, 3, 11, 82, 71, 49, 66
60, 49, 3, 11, 82, 71, 49, 66
3, 49, 60, 11, 82, 71, 49, 66
3, 11, 60, 49, 82, 71, 49, 66
3, 11, 60, 49, 82, 71, 49, 66
3, 11, 60, 49, 82, 71, 49, 66
3, 11, 49, 49, 60, 71, 82, 66
3, 11, 49, 49, 60, 66, 82, 71
3, 11, 49, 49, 60, 66, 82, 71
3, 11, 49, 49, 60, 66, 82, 71
3, 11, 49, 49, 60, 66, 82, 71
3, 11, 49, 49, 60, 66, 82, 71
3, 11, 49, 49, 60, 66, 82, 71
3, 11, 49, 49, 60, 66, 82, 71
3, 11, 49, 49, 60, 66, 71, 82

代码实现:

public void shellSort(int[] array) {
    for (int gap = array.length / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < array.length; i++) {
            int temp = array[i];
            int j;
            for (j = i - gap; j >= 0 && temp < array[j]; j -= gap) {
                array[j + gap] = array[j];
            }
            array[j + gap] = temp;
            after();
        }
    }
}

冒泡排序

已知待排序的一组记录:60, 71, 49, 11, 82, 49, 3, 66
排序过程如下：

60, 49, 11, 71, 49, 82, 3, 66
49, 11, 60, 49, 71, 3, 66, 82
11, 49, 49, 60, 3, 66, 71, 82
11, 49, 49, 3, 60, 66, 71, 82
11, 49, 3, 49, 60, 66, 71, 82
11, 3, 49, 49, 60, 66, 71, 82
3, 11, 49, 49, 60, 66, 71, 82

代码实现:

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

快速排序

已知待排序的一组记录:60, 71, 49, 11, 82, 49, 3, 66
排序过程如下：

base = 60
3, 49, 49, 11, 60, 82, 71, 66
base = 3
3, 49, 49, 11, 60, 82, 71, 66
base = 49
3, 11, 49, 49, 60, 82, 71, 66
base = 11
3, 11, 49, 49, 60, 82, 71, 66
base = 82
3, 11, 49, 49, 60, 66, 71, 82
base = 66
3, 11, 49, 49, 60, 66, 71, 82

代码实现:

public void quickSort(int[] array, int left, int right) {
    if (left < right) {
        int i = left;
        int j = right;
        int base = array[i];
        System.out.println("base = " + base);
        while (i < j) {
            while (i < j && array[j] >= base) {
                j--;
            }
            array[i] = array[j];
            while (i < j && array[i] <= base) {
                i++;
            }
            array[j] = array[i];
        }
        array[i] = base;
        after();
        quickSort(array, left, j - 1);
        quickSort(array, j + 1, right);
    }
}

选择排序

代码实现:

public void selectionSort(int[] array) {
    for (int i = 0; i < array.length - 1; i++) {
        int index = i;
        for (int j = i + 1; j < array.length; j++) {
            if (array[index] > array[j]) {
                index = j;
            }
        }
        int temp = array[index];
        array[index] = array[i];
        array[i] = temp;
    }
}

堆排序

代码实现:

public void heapSort(int[] array) {
    for (int i = array.length / 2; i >= 0; i--) {
        heapSortExchange(array, i, array.length);
    }
    for (int i = array.length - 1; i > 0; i--) {
        int temp = array[i];
        array[i] = array[0];
        array[0] = temp;
        heapSortExchange(array, 0, i);
    }
}

public void heapSortExchange(Integer[] array, int parent, int length) {
    int temp = array[parent];
    int leftChild = 2 * parent + 1;
    while (leftChild < length) {
        if (leftChild + 1 < length && array[leftChild] < array[leftChild + 1]) {
            leftChild++;
        }
        if (temp > array[leftChild]) {
            break;
        }
        array[parent] = array[leftChild];
        parent = leftChild;
        leftChild = 2 * leftChild + 1;
    }
    array[parent] = temp;
}

归并排序

已知待排序的一组记录:60, 71, 49, 11, 82, 49, 3, 66 排序过程如下：

[60, 71, 49, 11, 82, 49, 3, 66] [60, 71, 49, 11] [82, 49, 3, 66] [60, 71] [49, 11] [82, 49] [3, 66] [60] [71] [49] [11] [82] [49] [3] [66] [60, 71] [49, 11] [82, 49] [3, 66] [11, 49, 60, 71] [3, 49, 66, 82] [3, 11, 49, 49, 60, 66, 71, 82]

代码实现:

public void mergeSort(Integer[] array, int leftMargin, int rightMargin) {
    if (leftMargin < rightMargin) {
        int median = (leftMargin + rightMargin) / 2;
        mergeSort(array, leftMargin, median);
        mergeSort(array, median + 1, rightMargin);
        merge(array, leftMargin, median, rightMargin);
    }
}

public void merge(Integer[] array, int leftMargin, int median, int rightMargin) {
    int leftArray[] = new int[median - leftMargin + 1];
    int rightArray[] = new int[rightMargin - median];
    int i, j, k;
    for (i = 0, k = leftMargin; i < leftArray.length; i++, k++) {
        leftArray[i] = array[k];
    }
    for (j = 0, k = median + 1; j < rightArray.length; j++, k++) {
        rightArray[j] = array[k];
    }
    for (i = 0, j = 0, k = leftMargin; i < leftArray.length && j < rightArray.length; k++) {
        if (leftArray[i] > rightArray[j]) {
            array[k] = rightArray[j++];
        } else {
            array[k] = leftArray[i++];
        }
    }
    if (i < leftArray.length) {
        for (j = i; j < leftArray.length; j++, k++) {
            array[k] = leftArray[j];
        }
    }
    if (j < rightArray.length) {
        for (i = j; i < rightArray.length; i++, k++) {
            array[k] = rightArray[i];
        }
    }
}