十个经典排序

1

排序是什么

百度百科：排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。分内部排序和外部排序，若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序。反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。内部排序的过程是一个逐步扩大记录的有序序列长度的过程。

排序是将一组“无序”的记录序列调整为“有序”的记录序列，分内部排序和外部排序。本文主要介绍内部排序

稳定排序：假设在待排序的文件中，存在两个或两个以上的记录具有相同的关键字，在用某种排序法排序后，若这些相同关键字的元素的相对次序仍然不变，则这种排序方法是稳定的。其中冒泡，插入，基数，归并属于稳定排序，选择，快速，希尔，归属于不稳定排序。

就地排序：若排序算法所需的辅助空间并不依赖于问题的规模n，即辅助空间为O（1）则称为就地排序。

冒泡排序

冒泡排序，顾名思义就是

1. 两两比较，如果左边元素大于右边元素，则交换两个元素
2. 重复直到交换到最右边界，则当前区间最大元素被移到最右边，区间-1
3. 重复1-2，每一轮排序后最大的数将移动到数据序列的最后，直到所有元素都移到有序的位置上，排序完成

这样一个个元素按序冒到最后，就像冒泡一样的排序称为冒泡排序

复杂度：

O（n^2)，稳定排序

代码：

import java.util.Arrays;
public class BubbleSort {

    static void swap(int[] arr, int i, int j) {
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

    static void bubbleSort(int[] arr) {
        int n = arr.length;
        for (int i = n - 1; i > 0; i --)  //控制区间右边界
            for (int j = 0; j < i; j ++)  //当前冒的元素的位置
                if (arr[j] > arr[j + 1])
                    swap(arr, j, j + 1);    //两两交换
    }

    public static void main(String[] args) {
        int[] arr = new int[]{1, 3, 3, 6, 123, 34, 9, 10, 8, 4, 1};
        bubbleSort(arr);	//冒泡排序
        System.out.println(Arrays.toString(arr));
    }
}

选择排序

• 每一趟从待排序的数据元素中，选出最小的元素放在已排序的元素列的最后面
• 重复，直到待排序数据元素为空，排序完成

复杂度：

O(n^2)，可以分为稳定和不稳定两种实现

代码：

import java.util.Arrays;
public class SelectSort {
    
    static void swap(int[] arr, int i, int j) {
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

    static void selectSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n; i ++) {
            int t = i;  //第i小的元素的下标
            for (int j = i + 1; j < n; j ++) {
                if (arr[j] < arr[t])
                    t = j;
            }
            swap(arr, i, t);
        }
    }
    public static void main(String[] args) {
        int[] arr = new int[]{1, 3, 3, 6, 123, 34, 9, 10, 8, 4, 1};
        selectSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

插入排序

• 将待插入的元素，与已排序好的元素逐个比较，找到一个合适的位置插入，该位置后的所有元素后移一位。
• 直到所有元素插入完毕，排序完成

复杂度：

O(n^2)，稳定排序

代码：

import java.util.Arrays;
public class InsertionSort {

    static void swap(int[] arr, int i, int j) {
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

    static void insertionSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n; i ++) {
            int t = i;  //第i小的元素的下标
            for (int j = i - 1; j >= 0; j --) {
                if (arr[t] < arr[j]) swap(arr, t--, j); //如果t比j小，说明j要往后挪一位，t往前挪一位
                else break;
            }
        }
    }
    public static void main(String[] args) {
        int[] arr = new int[]{1, 3, 3, 6, 123, 34, 9, 10, 8, 4, 1};
        insertionSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

希尔排序

是直接插入排序的优化

-