十大常见排序算法

十大常见排序算法

差异比较

排序方法	时间复杂度(平均)	时间复杂度(最好)	时间复杂度(最坏)	空间复杂度	稳定性
冒泡排序	O(n²)	O(n)	O(n²)	O(1)	稳定
快速排序	O(nlog₂n)	O(nlog₂n)	O(n²)	O(nlog₂n)	不稳定
插入排序	O(n²)	O(n)	O(n²)	O(1)	稳定
选择排序	O(n²)	O(n²)	O(n²)	O(1)	不稳定
希尔排序	O(n¹˙³)	O(n)	O(n²)	O(1)	不稳定
堆排序	O(nlog₂n)	O(nlog₂n)	O(nlog₂n)	O(1)	不稳定
归并排序	O(nlog₂n)	O(nlog₂n)	O(nlog₂n)	O(n)	稳定
桶排序	O(n+k)	O(n)	O(n²)	O(n+k)	稳定
基数排序	O(n*k)	O(n*k)	O(n*k)	O(n+k)	稳定
计数排序	O(n+k)	O(n+k)	O(n+k)	O(n+k)	稳定

代码实现

一、冒泡排序

/**
     * 冒泡排序
     *
     * @param arr 数组
     */
public static void bubbleSort(int[] arr) {

    for (int i = 0; i < arr.length - 1; i++) {
        // 标志位
        boolean flag = false;
        for (int j = 0; j < arr.length - i - 1; j++) {
            int temp = 0;
            if (arr[j] > arr[j + 1]) {
                flag = true;
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
        // 一次未发生比较，直接终止
        if (!flag) {
            break;
        }
    }
}

二、快速排序

  /**
     * 快速排序
     *
     * @param arr   数组
     * @param begin 快排开始位
     * @param end   快排结束位
     */
public static void quickSort(int[] arr, int begin, int end) {
    if (begin < end) {
        int key = arr[begin];
        int i = begin, j = end;
        while (i < j) {
            // 左指针右移
            while (i < j && arr[j] >= key) {
                j--;
            }
            // 先用右边的替换左边的，反正右边的的值已经赋值给key了
            if (i < j) {
                arr[i] = arr[j];
                i++;
            }
            // 右指针左移
            while (i < j && arr[i] <= key) {
                i++;
            }
            // 再用左边的替换右边的，邮编的值为小于key的值
            if (i < j) {
                arr[j] = arr[i];
                j--;
            }
            // 替换左指针位置为key
            arr[i] = key;
            // 递归，分而治之
            quickSort(arr, begin, i - 1);
            quickSort(arr, i + 1, end);
        }
    }
}

三、插入排序

/**
     * 插入排序
     *
     * @param arr 待排序数组
     */
public static void insertSort(int[] arr) {
    int len = arr.length;
    int i, j, k;
    for (i = 1; i < len; i++) {
        for (j = i - 1; j >= 0; j--) {
            if (arr[j] > arr[i]) {
                break;
            }
        }
        if (j != i - 1) {
            int temp = arr[i];
            for (k = i - 1; k > j; k--) {
                arr[k + 1] = arr[k];
            }
            arr[k + 1] = temp;
        }
    }
}

四、希尔排序

/**
     * 希尔排序
     *
     * @param arr 待排数组
     */
public static void shellSort(int[] arr) {
    int len = arr.length;
    int temp;
    for (int step = len / 2; step >= 1; step /= 2) {
        for (int i = step; i < len; i++) {
            temp = arr[i];
            int j = i - step;
            while (j >= 0 && arr[j] > temp) {
                arr[j + step] = arr[j];
                j -= step;
            }
            arr[j + step] = temp;
        }
    }
}

五、选择排序

/**
     * 选择排序
     *
     * @param arr 待排数组
     */
public static void selectSort(int[] arr) {
    // i:有序区末尾位置,j:无序区开始位置,min:无序区最小元素位置
    int i, j, min;
    int len = arr.length;
    for (i = 0; i < len; i++) {
        min = i;
        // 找出arr[i+1]-arr[len-1]中最小元素
        for (j = i + 1; j < len; j++) {
            if (arr[j] < arr[min]) {
                min = j;
            }
        }
        // 若min!=i则说明找到了最下的元素，进行交换，保证arr[0]-arr[i]之间有序
        if (min != i) {
            int temp = arr[i];
            arr[i] = arr[min];
            arr[min] = temp;
        }
    }

}

六、堆排序

/**
 	* 堆排序
 	*
 	* @param arr 待排数组
 	*/
public static void heapSort(int[] arr) {
    int i, temp, len = arr.length;
    // 从2/n-1到0依次遍历，遍历之后，得到的数组实际上是一个最大二叉堆
    for (i = len / 2 - 1; i >= 0; i--) {
        maxHeapDown(arr, i, len - 1);
    }
    // 从最后一个元素开始对序列进行调整，不断缩小调整的范围直到第一个元素
    for (i = len - 1; i > 0; i--) {
        // 交换arr[0]和arr[i]。交换后，arr[i]是arr[0...i]中最大值。
        temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        // 调整arr[0...i-1]，使得arr[0...i-1]任然是一个最大堆。
        maxHeapDown(arr, 0, i - 1);
    }
}

/**
     * 最大堆的向下调整算法
     * 数组实现的堆中，第N个节点的左孩子是2*N+1，右孩子是2*N+2
     * 其中N为数组下标的索引值，数组中第一个数的N对应的值为0
     *
     * @param arr   待排数组
     * @param start 被下调节点的起始位置(一般为0，表示从第一个开始)
     * @param end   截至范围，一般为数组中最后一个元素的索引
     */
private static void maxHeapDown(int[] arr, int start, int end) {
    int c = start, l = 2 * c + 1;
    int temp = arr[c];
    for (; l <= end; c = l, l = 2 * l + 1) {
        // l是左孩子，l+1是右孩子
        if (l < end && arr[l] < arr[l + 1]) {
            l++;
        }
        if (temp >= arr[l]) {
            break;
        } else {
            arr[c] = arr[l];
            arr[l] = temp;
        }
    }
}

七、 归并排序

/**
     * 归并排序，从上往下
     *
     * @param arr   待排数组
     * @param start 起始位置
     * @param end   结束位置（len-1）
     */
public static void mergeSortUp2Down(int[] arr, int start, int end) {
    if (arr == null || start >= end) {
        return;
    }
    int mid = (start + end) / 2;
    // 递归排序前半部分
    mergeSortUp2Down(arr, start, mid);
    // 递归排序后半部分
    mergeSortUp2Down(arr, mid + 1, end);
    // a[start...mid] 和 a[mid...end]是两个有序空间，
    // 将它们排序成一个有序空间a[start...end]
    merge(arr, start, mid, end);
}

/**
     * 归并排序，从下往上
     *
     * @param arr 待排数组
     */
public static void mergeSortDown2Up(int[] arr) {
    if (arr == null) {
        return;
    }
    int len = arr.length;
    for (int i = 1; i < len; i *= 2) {
        int j;
        // 将"每2个相邻的子数组" 进行合并排序。
        for (j = 0; j + 2 * i - 1 < len; j += (2 * i))
            merge(arr, j, j + i - 1, j + 2 * i - 1);

        // 若 i+gap-1 < len-1，则剩余一个子数组没有配对。
        // 将该子数组合并到已排序的数组中。
        if (j + i - 1 < len - 1)
            merge(arr, j, j + i - 1, len - 1);
    }
}


/**
     * 将一个数组中两个相邻区域合并成一个
     *
     * @param arr   待排数组
     * @param start 第一个数组的起始位置
     * @param mid   第一个数组的结束位置，也是第二个数组的开始位置
     * @param end   第二个数组的结束位置
     */
private static void merge(int[] arr, int start, int mid, int end) {
    // 汇总两个数组的临时区域
    int[] temp = new int[end - start + 1];
    // 第一个有序区索引，第二个有序区索引，临时区索引
    int i = start, j = mid + 1, k = 0;
    while (i <= mid && j <= end) {
        if (arr[i] < arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }
    while (i <= mid) {
        temp[k++] = arr[i++];
    }
    while (j <= end) {
        temp[k++] = arr[j++];
    }
    // 将排好序的数组全部整合到数组a中
    for (i = 0; i < k; i++) {
        arr[start + i] = temp[i];
    }
    temp = null;
}

八、桶排序

/**
     * 桶排序
     *
     * @param arr 待排数组
     */
public static void bucketSort(int[] arr) {
    if (arr == null) {
        return;
    }
    int max = arr[0];
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    max++;
    if (max <= 1) {
        return;
    }
    // 存储数据的桶，桶容量为待排数组中的最大值
    int[] buckets = new int[max];
    // 计数
    for (int i = 0; i < arr.length; i++) {
        buckets[arr[i]]++;
    }
    // 排序
    for (int i = 0, j = 0; i < max; i++) {
        while (buckets[i]-- > 0) {
            arr[j++] = i;
        }
    }
    buckets = null;
}

九、基数排序

/**
     * 基数排序
     *
     * @param arr 待排数组
     */
public static void radixSort(int[] arr) {
    if (arr == null) {
        return;
    }
    int max = arr[0], len = arr.length;
    for (int i = 0; i < len; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    // 指数，当exp=1时按个位排序，当exp=10时按十位排序，当exp=100时按百位排序
    for (int exp = 1; max / exp > 0; exp *= 10) {
        countSort(arr, exp);
    }
}

private static void countSort(int[] arr, int exp) {
    int len = arr.length;
    // 存储被排序数组的临时数组
    int[] outputs = new int[len];
    int[] buckets = new int[10];
    // 将数据出现的次数存储再bucket中
    for (int i = 0; i < len; i++) {
        buckets[(arr[i] / exp) % 10]++;
    }
    // 更改buckets[i]，目的是让更改后的值是改数据再putput[]中的值
    for (int i = 1; i < 10; i++) {
        buckets[i] += buckets[i - 1];
    }
    // 将数组存储到临时数据outputs中
    for (int i = len - 1; i >= 0; i--) {
        outputs[buckets[(arr[i] / exp) % 10] - 1] = arr[i];
        buckets[(arr[i] / exp) % 10]--;
    }
    // 见排序好的数组赋值给arr
    for (int i = 0; i < len; i++) {
        arr[i] = outputs[i];
    }
    outputs = null;
    buckets = null;
}

十、计数排序

/**
     * 计数排序
     *
     * @param arr 待排数组
     */
public static void countSort(int[] arr) {
    if (arr == null) {
        return;
    }
    // 求出arr中数据的差值
    int max = arr[0], len = arr.length;
    for (int i = 0; i < len; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    max = max + 1;
    int[] res = new int[len];
    // 桶数组
    int[] buckets = new int[max];
    for (int i = 0; i < len; i++) {
        buckets[arr[i]]++;
    }
    for (int i = 1; i < max; i++) {
        buckets[i] += buckets[i - 1];
    }
    for (int i = len - 1; i >= 0; i--) {
        int a = arr[i];
        res[buckets[a] - 1] = a;
        buckets[a] -= 1;
    }
    for (int i = 0; i < len; i++) {
        arr[i] = res[i];
    }
    res = null;
}