排序算法

常见的排序算法

1.插入排序

// 插入排序算法
// 时间复杂度：平均情况:o(n^2)  最好情况:o(n) 最坏情况:o(n^2) 
// 空间复杂度: o(1)
// 特点: 稳定
public static void insertSort(int[] array) {
    int i,j;
    for (i = 1; i < array.length; i ++) {
        int temp = array[i];
        for (j = i - 1; j >=0 && array[j] > temp; j --) {
            // 将数组中的元素后移一位
            array[j + 1] = array[j];
        }
        array[j + 1] = temp;
    }
}

2.选择排序

原理

// 选择排序算法
// 时间复杂度: 平均情况:o(n^2)  最好情况:o(n^2) 最坏情况:o(n^2)  
// 空间复杂度: o(1)
// 特点: 不稳定
public static void selectSort(int[] array) {
    for (int i = 0; i < array.length; i ++) {
        for (int j = i + 1; j < array.length; j ++) {
            if (array[i] > array[j]) {
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
    }
}

3.交换排序->冒泡排序

原理

// 冒泡排序算法
// 时间复杂度: 平均情况:o(n^2)  最好情况:o(n) 最坏情况:o(n^2)
// 空间复杂度: o(1)
// 特点：稳定
public static void bubbleSort(int[] array) {
    for (int i = 0; i < array.length; i ++) {
        for (int j = 0; j < array.length - i - 1; j ++) {
            if (array[j] > array[j + 1]) {
                int temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }
}

4.交换排序->快速排序

原理

// 快速排序算法
// 时间复杂度: 平均情况:o(nlog2^n) 最好情况:o(nlog2^n) 最坏情况:o(n^2)
// 空间复杂度: o(nlog2^n)
// 特点：不稳定
public static void fastSort(int[] array, int low, int high) {
    if (low > high) {
        return;
    }
    
    int i = low;
    int j = fast;
    int temp = array[low];
    while (i < j) {
        // 从右向左找到第一个小于temp的元素,保存其下标
        while (array[j] > temp && i < j) {
            j --;
        }
        // 从左向右找到第一个大于temp的元素，保存其下标
        while (array[i] <= temp && i < j) {
            i ++;
        }
        // 交换这两个元素
        int swap = array[i];
        array[i] = array[j];
        array[j] = swap;
    }
    // 交换temp
    array[low] = array[i];
    array[i] = temp;
    // 快排temp左半边
    fastSort(array, low, j - 1);
    // 快排temp右半边
    fastSort(array, j + 1, high);
}

5.归并排序

// 归并排序算法
// 时间复杂度: 平均情况:o(nlog2^n) 最好情况:o(nlog2^n) 最坏情况:o(nlog2^n)
// 空间复杂度：o(1)
// 特点: 稳定
public static  void sortMerge(int[] array) {
    sort(array, 0, array.length - 1);
}

public static void sort(int array[], int L, int R) {
    if (L == R) {
        return;
    }
    int mid = (R + L) / 2;
    // 排序左半部分
    sort(array, L, mid);
    // 排序右半部分
    sort(array, mid + 1, R);
    // 合并 
    merge(array, L, mid, R);
}
public static void merge(int[] array, int L, int mid, int R) {
    int[] temp = new int[R - L + 1];
    int i = 0;
    int p1 = L;
    int p2 = mid + 1;
    // 将数组排序后放入到临时数组temp中
    while (p1 <= mid && p2 <= R) {
        if (array[p1] < array[p2]) {
            temp[i++] = array[p1++];
        } else {
            temp[i++] = array[p2++];
        }
    }
    while(p1 <= mid) {
        temp[i++] = array[p1++];
    }
    while(p2 <= R) {
        temp[i++] = array[p2++];
    }
    // 将临时数组中的元素移动到array中
    for (int k = 0; k < temp.length; k ++) {
        array[L + k] = temp[k];
    }
}