十大经典排序算法Java版

参考链接

定义

• 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
• 不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
• 时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
• 空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。
  

1、冒泡排序（Bubble Sort）

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

     /**
     * 冒泡排序
     */
    private int[] bubbleSort(int[] ints) {
        int temp;
        for (int i = 0; i < ints.length; i++) {
            for (int j = 1; j < ints.length - i; j++) {
                if (ints[j - 1] > ints[j]) {
                    temp = ints[j - 1];
                    ints[j - 1] = ints[j];
                    ints[j] = temp;
                }
            }
        }
        return ints;
    }

2、选择排序(Selection Sort)

选择排序是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

     /**
     * 选择排序
     */
    private int[] selectionSort(int[] ints) {
        int min, temp;
        for (int i = 0; i < ints.length; i++) {
            min = i;
            for (int j = i + 1; j < ints.length; j++) {
                if (ints[min] > ints[j]) {
                    min = j;
                }
            }
            temp = ints[i];
            ints[i] = ints[min];
            ints[min] = temp;
        }
        return ints;
    }

3、插入排序（Insertion Sort）

插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

     /**
     * 插入排序
     */
    private int[] insertionSort(int[] ints) {
        int current, preIndex;
        for (int i = 1; i < ints.length; i++) {
            current = ints[i];
            preIndex = i - 1;
            while (preIndex >= 0 && current < ints[preIndex]) {
                ints[preIndex + 1] = ints[preIndex];
                preIndex--;
            }
            ints[preIndex + 1] = current;
        }
        return ints;
    }

4、快速排序（Quick Sort）

快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

    /**
     * 快速排序
     */
    private int[] quickSort(int[] ints, int left, int right) {
        if (left < right) {
            int flag = partition(ints, left, right);
            quickSort(ints, left, flag - 1);
            quickSort(ints, flag + 1, right);
        }
        return ints;
    }

    private int partition(int[] ints, int left, int right) {
        int index = left + 1;
        for (int i = index; i <= right; i++) {
            if (ints[left] > ints[i]) {
                exchange(ints, i, index);
                index++;
            }
        }
        exchange(ints, left, index - 1);
        System.out.println(Arrays.toString(ints));
        return index - 1;
    }

    private void exchange(int[] ints, int a, int b) {
        int temp = ints[a];
        ints[a] = ints[b];
        ints[b] = temp;
    }

5、希尔排序（Shell Sort）

希尔排序是简单插入排序的改进版，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。

    /**
     * 希尔排序
     */
    private int[] shellSort(int[] ints) {
        int length = ints.length;
        for (int i = length / 2; i > 0; i = i / 2) {
            for (int j = i; j < length; j++) {
                int k = j;
                int current = ints[j];
                while (k - i >= 0 && current < ints[k - i]) {
                    ints[k] = ints[k - i];
                    k = k - i;
                }
                ints[k] = current;
            }
        }
        return ints;
    }

6、归并排序（Merge Sort）

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

    /**
     * 归并排序
     */
    private int[] mergeSort(int[] ints) {
        if (ints.length < 2) {
            return ints;
        }
        int mid = ints.length / 2;
        int[] left = Arrays.copyOfRange(ints, 0, mid);
        int[] right = Arrays.copyOfRange(ints, mid,  ints.length);
        return merge(mergeSort(left), mergeSort(right));
    }

    private int[] merge(int[] left, int[] right) {
        int[] merge = new int[left.length + right.length];
        for (int index = 0, leftIndex = 0, rightIndex = 0; index < merge.length; index ++) {
            if (leftIndex < left.length && rightIndex < right.length) {
                if (left[leftIndex] < right[rightIndex]) {
                    merge[index] = left[leftIndex++];
                } else {
                    merge[index] = right[rightIndex++];
                }
            } else if (leftIndex < left.length) {
                merge[index] = left[leftIndex++];
            } else {
                merge[index] = right[rightIndex++];
            }
            System.out.println(Arrays.toString(merge));
        }
        return merge;
    }

7、堆排序（Heap Sort）

堆排序是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

    /**
     * 堆排序
     */
    int len;
    private int[] heapSort(int[] ints) {
        len = ints.length;
        if (len < 1) return ints;

        buildMaxHeap(ints);

        for (int i = len - 1; i > 0; i--) {
            exchange(ints, 0, i);
            len--;
            adjustHeap(ints, 0);
        }
        return ints;
    }

    private void buildMaxHeap(int[] ints) {
        for (int i = (len / 2 - 1); i >= 0; i--) {
            adjustHeap(ints, i);
        }
    }

    private void adjustHeap(int[] ints, int i) {
        int left = 2 * i;
        int right = 2 * i + 1;
        int max = i;
        if (left < len && ints[left] > ints[max]) {
            max = left;
        }
        if (right < len && ints[right] > ints[max]) {
            max = right;
        }
        if (max != i) {
            exchange(ints, i, max);
            adjustHeap(ints, max);
        }
    }

8、计数排序（Counting Sort）

计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
计数排序使用一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。它只能对整数进行排序。

    /**
     * 计数排序
     */
    private int[] countingSort(int[] ints) {
        int min = ints[0], max = ints[0];
        // 求出最大值最小值
        for (int i = 1; i < ints.length; i++) {
            if (min > ints[i]) {
                min = ints[i];
            }
            if (max < ints[i]) {
                max = ints[i];
            }
        }
        int[] arr = new int[max - min + 1];
        // 计数
        for (int i = 0; i < ints.length; i++) {
            arr[ints[i] - min]++;
        }
        int index = 0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > 0) {
                ints[index++] = i + min;
            }
        }
        return ints;
    }

9、桶排序（Bucket sort）

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。

    /**
     * 桶排序
     */
    private ArrayList<Integer> bucketSort(ArrayList<Integer> arrayList, int bucketSize) {
        if (arrayList.size() == 0) {
            return arrayList;
        }
        int min = arrayList.get(0), max = arrayList.get(0);
        // 求出最大值最小值
        for (int i = 1; i < arrayList.size(); i++) {
            if (min > arrayList.get(i)) {
                min = arrayList.get(i);
            }
            if (max < arrayList.get(i)) {
                max = arrayList.get(i);
            }
        }
        // 桶数量
        int bucketCount = (max - min) / bucketSize + 1;
        ArrayList<ArrayList<Integer>> lists = new ArrayList<>();

        for (int i = 0; i < bucketCount; i++) {
            lists.add(new ArrayList<>());
        }
        for (int i = 0; i < arrayList.size(); i++) {
            int current = (arrayList.get(i) - min) / bucketSize;
            lists.get(current).add(arrayList.get(i));
        }
        ArrayList<Integer> result = new ArrayList<>();
        for (int i = 0; i < lists.size(); i++) {
            if (bucketSize == 1) {
                // 也可以用addAll
                for (int j = 0; j < lists.get(i).size(); j++) {
                    result.add(lists.get(i).get(j));
                }
            } else {
                if (bucketCount == 1) {
                    bucketSize--;
                }
                ArrayList<Integer> bucketList = bucketSort(lists.get(i), bucketSize);
                // 也可以用addAll
                for (int j = 0; j < bucketList.size(); j++) {
                    result.add(bucketList.get(j));
                }
            }
        }
        return result;
    }

10、基数排序（Radix Sort）

基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。

    /**
     * 基数排序
     */
    private int[] radixSort(int[] ints) {
        // 求出最大值得位数
        int max = ints[0];
        for (int i = 1; i < ints.length; i++) {
            if (ints[i] > max) {
                max = ints[i];
            }
        }
        int digit = 1;
        while (max / 10 > 0) {
            max = max / 10;
            digit++;
        }

        ArrayList<ArrayList<Integer>> list = new ArrayList<>();

        for (int j = 0; j < 10; j++) {
            list.add(new ArrayList<>());
        }

        int a = 10, b = 1;
        for (int i = 0; i < digit; a *= 10, b *= 10, i++) {
            for (int j = 0; j < ints.length; j++) {
                int count = ints[j] % a / b;
                list.get(count).add(ints[j]);
            }
            int index = 0;
            for (int j = 0; j < list.size(); j++) {
                for (int k = 0; k < list.get(j).size(); k++) {
                    ints[index++] = list.get(j).get(k);
                }
                list.get(j).clear();
            }
        }
        return ints;
    }