image.png

各排序代碼如下：

一：交換排序

// 冒泡排序
@Override
public void bubbleSort(int[] data) {
    if (null == data || data.length <= 1) {
        return;
    }
    final int length = data.length;
    int temp = 0;
    // 外層循環(huán)控制比較趟數(shù) (每比較一趟，會確定一個數(shù)的最終位置, 會比較data.length - 1 趟)
    for (int i = 0; i < length - 1; i++) { // 注意下標  結(jié)尾是 length - 1
        // 內(nèi)層循環(huán)是比較第[i]元素與，[i + 1, data.length]中所有元素的比較
        for (int j = 0; j < length - 1 - i; j++) {
            if (data[j + 1] < data[j]) {
                temp = data[j + 1];
                data[j + 1] = data[j];
                data[j] = temp;
            }
        }
    }
}

// 快速排序
@Override
public void quickSort(int[] data) {
    if (null == data || data.length <= 1) {
        return;
    }
    long startTime = System.currentTimeMillis();
    inner_quickSort(data, 0, data.length - 1);
    System.out.println("快速排序時間：" + (System.currentTimeMillis() - startTime));
}

private void inner_quickSort(int[] data, int start, int end) {
    if (start < end) {
        int i = partition(data, start, end);
        inner_quickSort(data, start, i - 1);
        inner_quickSort(data, i + 1, end);
    }
}

private int partition(int[] array, int start, int end) {
    int temp = array[start]; // 用子序的第一個作為基準
    int i = start, j = end;
    while (i < j) {
        // 先遍歷右邊的數(shù)據(jù)
        while (i < j && array[j] > temp) {
            j--;
        }
        if (i < j) {
            array[i] = array[j];
            i++;
        }

        // 再遍歷左邊的數(shù)據(jù)
        while (i < j && array[i] < temp) {
            i++;
        }
        if (i < j) {
            array[j] = array[i];
            j--;
        }
        // array[i] = temp;
    }
    array[i] = temp;
    return i;
}

二：選擇排序

// 簡單選擇排序
@Override
public void simpleSelect(int[] data) {
    if (null == data || data.length <= 1) {
        return;
    }
    final int length = data.length;
    for (int i = 0; i < length; i++) {
        int target = i;
        for (int j = i + 1; j < length; j++) {
            if (data[j] < data[target]) {
                target = j;
            }
        }
        int temp = 0;
        if (target != i) {
            temp = data[target];
            data[target] = data[i];
            data[i] = temp;
        }
    }

}

// 堆排序
@Override
public void heapSort(int[] data) {
    // TODO Auto-generated method stub

}

三： 插入排序

// 直接插入排序
@Override
public void directInsertSort(int[] data) {
    for (int i = 1; i < data.length; i++) {
        inner(data, 1, i);
    }
}

// 希爾排序
@Override
public void shellSort(int[] data) {
    int length = data.length;
    for (int gap = length / 2; gap > 0; gap /= 2) {
        for(int j = gap; j < length; j++) {
            inner(data, gap, j);
        }
    }
}

private void inner(int[] data, int gap, int i) {
    int willInsert = data[i];
    int j;
    for (j = i; j >= gap && data[j - gap] > willInsert; j -= gap) {
        data[j] = data[j - gap];
    }
    data[j] = willInsert;
}

四： 歸并排序

時間復(fù)雜度：O(nlogn)
空間復(fù)雜度：O(N) ，歸并排序需要一個與原數(shù)組相同長度的數(shù)組來做輔助排序。
穩(wěn)定性：是穩(wěn)定的排序算法

@Override
public void mergeSort(int[] data) {
    if (null == data || 1 >= data.length) {
        return;
    }
    sort(data, 0, data.length - 1);
}

private void sort(int[] a, int start, int end) {
    if (start < end) {// 當子序列中只有一個元素時結(jié)束遞歸
        final int mid = (start + end) / 2;// 劃分子序列
        // 對左側(cè)子序列進行遞歸排序
        sort(a, start, mid);
        // 對右側(cè)子序列進行遞歸排序
        sort(a, mid + 1, end);
        // 合并
        merge(a, start, mid, end);
    }
}

// 兩路歸并算法，兩個排好序的子序列合并為一個子序列
private void merge(int[] a, int left, int mid, int right) {
    int[] tmp = new int[a.length];// 輔助數(shù)組
    int p1 = left, p2 = mid + 1, tmpIndex = left;// p1、p2是檢測指針，k是存放指針
    
    // 比較左右兩部分的元素，哪個小就把哪個元素填入tmp中
    while (p1 <= mid && p2 <= right) {
        tmp[tmpIndex++] = a[p1] <= a[p2] ? a[p1++] : a[p2++];
    }

    // 如果第一個序列未檢測完，直接將后面所有元素加到合并的序列中
    // (以下兩個while只有一個會執(zhí)行)
    while (p1 <= mid)
        tmp[tmpIndex++] = a[p1++];

    while (p2 <= right)
        tmp[tmpIndex++] = a[p2++];

    // 把最終的排序的結(jié)果復(fù)制給原數(shù)組
    for (int i = left; i <= right; i++)
        a[i] = tmp[i];
}