十大排序（JAVA语言）代码 冒泡排序、插入排序、希尔排序、选择排序、快速排序、归并排序、堆排序、桶排序、计数排序、基数排序

0. 排序算法动画演示地址

https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html

1. 冒泡排序

原理简述：从前到后依次比较相邻元素的值，若发现逆序则交换位置，使值较大的元素逐渐从前移向后部。

代码讲解地址：https://www.bilibili.com/video/BV19K411e7dZ/

public class BubbleSort {
    public void swap(int[] array, int index1, int index2){
        array[index1] = array[index1] ^ array[index2];
        array[index2] = array[index1] ^ array[index2];
        array[index1] = array[index1] ^ array[index2];
    }
    public void sortFunction(int[] array){
        for (int i = 0; i < array.length - 1; i++) {
            int count = 0;
            for (int j = 0; j < array.length - i - 1; j++) {
                if(array[j] > array[j + 1]){
                    swap(array, j, j + 1);
                    count++;
                }
            }
            if(count == 0){
                break;
            }
        }
    }
}

2. 插入排序

原理简述：将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增1的有序表。

代码讲解地址：https://www.bilibili.com/video/BV1K5411B7jj

public class InsertSort {
    public void sortFunction(int[] array) {
        int i, j;
        for (i = 1; i < array.length; i++) {
            int temp = array[i];
            for (j = i - 1; j >= 0; j--) {
                if (temp < array[j]) {
                    array[j + 1] = array[j];
                }else {
                    break;
                }
            }
            array[j + 1] = temp;
        }
    }
}

3. 希尔排序

原理简述：先取定一个小于数组长度Array.length 的整数 gap（gap = Array.length / 2）作为第一个增量，把表的全部元素分成 gap 个组，所有相互之间距离为 gap 的倍数的元素放在同一个组中，在各组内进行直接插入排序。然后，减小增量 gap（gap = gap /2），重复上述的分组和排序过程，直至增量减小为 0，即所有元素放在同一组中进行直接插入排序。

代码讲解地址：https://www.bilibili.com/video/BV1Ac411t76T

public class ShellSort {
    public void sortFunction(int[] array) {
        int gap = array.length;
        while (gap > 1) {
            int i, j;
            gap = gap >> 1;
            for (i = 0; i < array.length - gap; i++) {
                int temp = array[i + gap];
                for (j = i; j >= 0; j -= gap) {
                    if (temp < array[j]) {
                        array[j + gap] = array[j];
                    } else {
                        break;
                    }
                }
                array[j + gap] = temp;
            }
        }
    }
}

4. 选择排序

原理简述：从待排序的数据元素中选出最小的一个元素，将其与待排序部分的第一个元素交换位置，然后再从剩余的待排序元素中寻找到最小元素，将其与待排序部分的第一个元素交换位置 。以此类推，直到全部待排序的数据元素的个数为零。

代码讲解地址：https://www.bilibili.com/video/BV125411v7DK

public class SelectSort {
    public void swap(int[] array, int index1, int index2){
        array[index1] = array[index1] ^ array[index2];
        array[index2] = array[index1] ^ array[index2];
        array[index1] = array[index1] ^ array[index2];
    }
    public void sortFunction(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            int minNumIndex = i;
            for (int j = i + 1; j < array.length; j++) {
                if (array[j] < array[minNumIndex]) {
                    minNumIndex = j;
                }
            }
            if (minNumIndex != i){
                swap(array, minNumIndex, i);
            }
        }
    }
}

5. 快速排序

原理简述：快速排序在每一轮挑选一个基准元素，并让其他比它大的元素移动到数列一边，比它小的元素移动到数列的另一边，从而把数列拆解成了两个部分。

代码讲解地址：https://www.bilibili.com/video/BV12e411e7cF

public class QuickSort {
    public void sortFunction(int[] array, int low, int high) {
        if (low < high) {
            int pivot = array[low];
            int i = low;
            int j = high;
            while (i < j) {
                while ((i < j) && array[j] > pivot) {
                    j--;
                }
                if (i < j) {
                    array[i] = array[j];
                    i++;
                }
                while ((i < j) && array[i] < pivot) {
                    i++;
                }
                if (i < j) {
                    array[j] = array[i];
                    j--;
                }
            }
            array[i] = pivot;
            sortFunction(array, low, i - 1);
            sortFunction(array, i + 1, high);
        }
    }
}

6. 归并排序

原理简述：把长度为n的输入序列分成两个长度为n/2的子序列，对这两个子序列分别采用归并排序，将两个排序好的子序列合并成一个最终的排序序列。

代码讲解地址：https://www.bilibili.com/video/BV1iC4y1Y7Wy

public class MergeSort {
    public void sortFunction(int[] array) {
        int[] tempArray = new int[array.length];
        mergeSortFunction(array, tempArray, 0, array.length - 1);
    }
    public void mergeSortFunction(int[] array, int[] tempArray, int begin, int end) {
        if (begin < end) {
            int mid = begin + ((end - begin) >> 1);
            mergeSortFunction(array, tempArray, begin, mid);
            mergeSortFunction(array, tempArray, mid + 1, end);
            merge(array, tempArray, begin, mid, end);
        }
    }
    public void merge(int[] array, int[] tempArray, int begin, int mid, int end) {
        int leftPos = begin;
        int rightPos = mid + 1;
        int tempArrayPos = begin;
        while (leftPos <= mid && rightPos <= end) {
            if (array[leftPos] < array[rightPos]) {
                tempArray[tempArrayPos++] = array[leftPos++];
            } else {
                tempArray[tempArrayPos++] = array[rightPos++];
            }
        }
        while (leftPos <= mid) {
            tempArray[tempArrayPos++] = array[leftPos++];
        }
        while (rightPos <= end) {
            tempArray[tempArrayPos++] = array[rightPos++];
        }
        for (int i = begin; i <= end; i++) {
            array[i] = tempArray[i];
        }
    }
}

7. 堆排序

原理简述：将待排序的序列构造成一个大顶堆，根据大顶堆的性质，当前堆的根节点（堆顶）就是序列中最大的元素，将堆顶元素和最后一个元素交换，然后将剩下的节点重新构造成一个大顶堆，如此反复，从第一次构建大顶堆开始，每一次构建，我们都能获得一个序列的最大值，然后把它放到大顶堆的尾部。最后，就得到一个有序的序列了。

代码讲解地址：https://www.bilibili.com/video/BV1pa4y117zp

public class HeapSort {
    public void swap(int[] array, int index1, int index2) {
        array[index1] = array[index1] ^ array[index2];
        array[index2] = array[index1] ^ array[index2];
        array[index1] = array[index1] ^ array[index2];
    }
    public void downAdjust(int[] array, int index, int arrayLength) {
        if (index > (arrayLength - 2) >> 1) {
            return;
        } else if ((index * 2) + 2 >= arrayLength) {
            if (array[(index * 2) + 1] > array[index]) {
                swap(array, (index * 2) + 1, index);
            }
        } else {
            if (array[(index * 2) + 2] > array[index] && array[(index * 2) + 2] >= array[(index * 2) + 1]) {
                swap(array, (index * 2) + 2, index);
                downAdjust(array, (index * 2) + 2, arrayLength);
            } else if (array[(index * 2) + 1] > array[index] && array[(index * 2) + 1] > array[(index * 2) + 2]) {
                swap(array, (index * 2) + 1, index);
                downAdjust(array, (index * 2) + 1, arrayLength);
            }
        }
    }
    public void initHeap(int[] array, int arrayLength) {
        boolean hasTwochild = (arrayLength % 2) == 1 ? true : false;
        for (int i = (arrayLength - 2) >> 1; i >= 0; i--) {
            if (hasTwochild) {
                if (array[(i * 2) + 2] > array[i] && array[(i * 2) + 2] >= array[(i * 2) + 1]) {
                    swap(array, (i * 2) + 2, i);
                    downAdjust(array, (i * 2) + 2, arrayLength);
                } else if (array[(i * 2) + 1] > array[i] && array[(i * 2) + 1] > array[(i * 2) + 2]) {
                    swap(array, (i * 2) + 1, i);
                    downAdjust(array, (i * 2) + 1, arrayLength);
                }
            } else {
                if (array[(i * 2) + 1] > array[i]) {
                    swap(array, (i * 2) + 1, i);
                }
                hasTwochild = true;
            }
        }
    }
    public void sortFunction(int[] array) {
        int arrayLength = array.length;
        for (int i = array.length - 1; i > 0; i--) {
            initHeap(array, arrayLength);
            swap(array, i, 0);
            arrayLength--;
        }
    }
}

8. 桶排序

原理简述：将数组元素分到有限数量的桶里。每个桶再个别排序，最后依次把各个桶中的记录列出来记得到有序序列。

代码讲解地址：https://www.bilibili.com/video/BV1ZN4y1v7hQ

public class BucketSort {
    public void sortFunction(int[] array, int bucketNum) {
        int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
        for (int i : array) {
            max = Math.max(max, i);
            min = Math.min(min, i);
        }
        List<List<Integer>> bucketList = new ArrayList<List<Integer>>();
        for (int i = 0; i < bucketNum; i++) {
            bucketList.add(new ArrayList<Integer>());
        }
        for (int i : array) {
            int bucketIndex = (i - min) * (bucketNum - 1) / (max - min);
            List<Integer> list = bucketList.get(bucketIndex);
            list.add(i);
        }
        for (int i = 0, arrIndex = 0; i < bucketList.size(); i++) {
            List<Integer> bucket = bucketList.get(i);
            Collections.sort(bucket);
            for (int num : bucket) {
                array[arrIndex++] = num;
            }
        }

    }
}

9. 计数排序

原理简述：利用数组的索引是有序的，通过将序列中的元素作为索引，其个数作为值放入数组，遍历数组来排序。

代码讲解地址：https://www.bilibili.com/video/BV1ut4y1R7Yk

public class CountSort {
    public void sortFucntion(int[] array) {
        int max = Integer.MIN_VALUE;
        for (int i : array) {
            max = Math.max(max, i);
        }
        int[] numCountArray = new int[max + 1];
        for (int i = 0; i < array.length; i++) {
            numCountArray[array[i]]++;
        }
        int arrayIndex = 0;
        for (int i = 0; i < numCountArray.length; i++) {
            for (int j = 0; j < numCountArray[i]; j++) {
                array[arrayIndex++] = i;
            }
        }
    }
}

10. 基数排序

原理简述：将整数按位数切割成不同的数字，然后按每个位数分别比较。

代码讲解地址：https://www.bilibili.com/video/BV1UT4y187bk

public class RadixSort {
    private void sortFunction(int[] array) {
        int max = Integer.MIN_VALUE;
        for (int i : array) {
            max = Math.max(max, i);
        }
        int maxLength = String.valueOf(max).length();
        LinkedList<Integer>[] radixList = new LinkedList[10];
        for (int i = 0; i < radixList.length; i++) {
            radixList[i] = new LinkedList<Integer>();
        }
        for (int i = 1; i <= maxLength ; i++) {
            for (int j = 0; j < array.length; j++) {
                radixList[getRadix(array[j], i)].add(array[j]);
            }
            int index = 0;
            for (int j = 0; j < radixList.length; j++) {
                while (radixList[j].isEmpty() == false) {
                    array[index++] = radixList[j].remove();
                }
            }
        }
    }
    public int getRadix(int num, int pos) {
        int result = 0;
        for (int i = 1; i <= pos; i++) {
            result = num % 10;
            num /= 10;
        }
        return result;
    }
}

比较（个人电脑测试，仅供参考）

	100	1000	10000	100000
冒泡排序	0ms	3ms	86ms	12962ms
插入排序	0ms	1ms	9ms	442ms
希尔排序	0ms	0ms	3ms	11ms
选择排序	0ms	1ms	38ms	2253ms
快速排序	0ms	0ms	1ms	11ms
归并排序	0ms	0ms	2ms	10ms
堆排序	0ms	2ms	36ms	1986ms
桶排序	0ms	1ms	7ms	37ms
计数排序	0ms	0ms	1ms	6ms
基数排序	0ms	1ms	5ms	34ms

	最好时间复杂度	最坏时间复杂度	平均时间复杂度	空间复杂度	稳定性
冒泡排序	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	稳定
插入排序	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	稳定
希尔排序	$O(n)$	$O(n^2)$	$O(nlo{g}_{2}n)$	$O(1)$	不稳定
选择排序	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	不稳定
快速排序	$O(nlo{g}_{2}n)$	$O(n^2)$	$O(nlo{g}_{2}n)$	$O(lo{g}_{2}n)$	不稳定
归并排序	$O(nlo{g}_{2}n)$	$O(nlo{g}_{2}n)$	$O(nlo{g}_{2}n)$	$O(n)$	稳定
堆排序	$O(n)$	$O(nlo{g}_{2}n)$	$O(nlo{g}_{2}n)$	$O(1)$	不稳定
桶排序	$O(n+k)$	$O(n^2)$	$O(n+k)$	$O(n+k)$	稳定
计数排序	$O(n+k)$	$O(n+k)$	$O(n+k)$	$O(k)$	稳定
基数排序	$O(n?k)$	$O(n?k)$	$O(n?k)$	$O(n+k)$	稳定