8种排序算法 Java实现

冒泡排序 O(n2)

两个数比较大小，较大的数下沉，较小的数冒起来。

public static void bubbleSort(int[] a) {
        //临时变量
        int temp;
        //i是循环次数,也是冒泡的结果位置下标，5个数组循环5次
        for (int i = 0; i < a.length; i++) {
            //从最后向前面两两对比，j是比较中下标大的值
            for (int j = a.length - 1; j > i; j--) {
                //让小的数字排在前面
                if (a[j] < a[j - 1]) {
                    temp = a[j];
                    a[j] = a[j - 1];
                    a[j - 1] = temp;
                }
            }
        }
    }

选择排序 O(n2)

在长度为N的无序数组中，第一次遍历n-1个数，找到最小的数值与第一个元素交换；
第二次遍历n-2个数，找到最小的数值与第二个元素交换；
。。。
第n-1次遍历，找到最小的数值与第n-1个元素交换，排序完成。

public static void selectSort(int[] a) {
        //临时变量
        int temp;
        //i是循环次数,也是选择交换的结果的位置下标，5个数组循环5次
        for (int i = 0; i < a.length; i++) {
            //最小值下标
            int min = i;
            for (int j = i + 1; j < a.length; j++) {
                if (a[min] > a[j]) {
                    min = j;
                }
            }
            temp = a[i];
            a[i] = a[min];
            a[min] = temp;
        }
    }

插入排序 O(n2)

在要排序的一组数中，假定前n-1个数已经排好序，现在将第n个数插到前面的有序数列中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。

public static void insertSort(int[] a) {
        int temp;
        //i是循环次数,也是插入的队列的长度，最后一位是a[i]
        //所以一开始a[0]是排好的一个队列，比较a.length-1次，最后一次循环是a[a.length-1]插入a[0]~a[a.length-2]
        for (int i = 0; i < a.length - 1; i++) {
            //a[j]是要插入的数字，从a[j]往a[0]比较
            for (int j = i + 1; j > 0; j--) {
                //如果插入的数小，交换位置
                if (a[j] < a[j - 1]) {
                    temp = a[j];
                    a[j] = a[j - 1];
                    a[j - 1] = temp;
                } else {
                    //因为默认a[0]~a[i]是排好的，a[i+1]比a[i]大的话，就不用比较后面了
                    break;
                }
            }
        }
    }

希尔排序 O(n1.5)

在要排序的一组数中，根据某一增量分为若干子序列，并对子序列分别进行插入排序。
然后逐渐将增量减小,并重复上述过程。直至增量为1,此时数据序列基本有序,最后进行插入排序。

public static void shellSort(int[] a) {
        int temp;
        int d = a.length;
        for (; ; ) {
            d = d / 2;
            //根据差值分组为子序列
            for (int k = 0; k < d; k++) {
                //此时对每组数列进行插入排序，数组为a[k+d],a[k+2d]...a[k+n*d]
                for (int i = k + d; i < a.length; i += d) {
                    // a[j]是要插入的数字，从a[j]往a[0]比较,跨度为d
                    for (int j = i; j > k; j -= d) {
                        //如果插入的数小，交换位置
                        if (a[j] < a[j - d]) {
                            temp = a[j];
                            a[j] = a[j - d];
                            a[j - d] = temp;
                        } else {
                            //因为默认a[0]~a[i]是排好的，a[i+1]比a[i]大的话，就不用比较后面了
                            break;
                        }
                    }
                }
            }
            if (d == 1) {
                break;
            }
        }
    }

快速排序 O(N*logN)

先从数列中取出一个数作为base值；
将比这个数小的数全部放在它的左边，大于或等于它的数全部放在它的右边；
对左右两个小数列重复第二步，直至各区间只有1个数。

public void quickSort(int a[], int l, int r) {
        //左边必须大于右边
        if (l >= r) {
            return;
        }
        int i = l;
        int j = r;
        //选择第一个数为基准
        int base = a[l];
        while (i < j) {
            //从右向左找第一个小于base的值，如果大于左移一位，直到找到小值或者i/j重合
            while (i < j && a[j] > base) {
                j--;
            }
            //从左向右找第一个大于base的值,如果小于右移一位，直到找到大值或者i/j重合
            while (i < j && a[i] < base) {
                i++;
            }
            //交换
            if (i < j) {
                int temp = a[j];
                a[j] = a[i];
                a[i] = temp;
            }
        }
        //将基准值放到i右移到的位置
        a[i] = base;
        //将i左边和i右边分别排序
        quickSort(a, l, i - 1);//递归调用
        quickSort(a, i + 1, r);//递归调用
    }

归并排序 O(N*logN)

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。
首先考虑下如何将2个有序数列合并。
这个非常简单，只要从比较2个数列的第一个数，谁小就先取谁，取了后就在对应数列中删除这个数。
然后再进行比较，如果有数列为空，那直接将另一个数列的数据依次取出即可。

private static void mergeSort(int[] a, int first, int last, int temp[]) {
        if (first < last) {
            //中间值
            int middle = (first + last) / 2;
            //左半部分排序
            mergeSort(a, first, middle, temp);
            //右半部分排序
            mergeSort(a, middle + 1, last, temp);
            //合并左右部分
            mergeArray(a, first, middle, last, temp);
        }
    }

    private static void mergeArray(int a[], int first, int middle, int end, int temp[]) {
        int i = first;
        int m = middle;
        int j = middle + 1;
        int n = end;
        int k = 0;
        while (i <= m && j <= n) {
            if (a[i] <= a[j]) {
                temp[k] = a[i];
                k++;
                i++;
            } else {
                temp[k] = a[j];
                k++;
                j++;
            }
        }
        while (i <= m) {
            temp[k] = a[i];
            k++;
            i++;
        }
        while (j <= n) {
            temp[k] = a[j];
            k++;
            j++;
        }
        for (int r = 0; r < k; r++) {
            a[first + r] = temp[r];
        }
    }

堆排序 O(N*logN)

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

public static void heapSort(int a[]) {
        //堆顶最大值和数组最后（叶节点）交换 长度-1 次
        for (int i = a.length - 1; i > 0; i--) {
            //构建大顶堆（最大堆）
            buildHeap(a, i);
            //堆顶最大值和数组最后（叶节点）交换
            swap(a, 0, i);
        }
    }

    //构建大顶堆（最大堆）
    public static void buildHeap(int a[], int lastIndex) {
        //排最后的非叶节点为 长度/2-1，从第i检查到堆顶第0项，上浮大值
        for (int i = (lastIndex + 1) / 2 - 1; i >= 0; i--) {
            //必定存在的左叶节点，不一定存在的右叶节点
            int left = i * 2 + 1;
            int right = i * 2 + 2;
            //max为左右叶节点中的最大值
            int max = left;
            if (right <= lastIndex) {
                if (a[left] < a[right]) {
                    max = right;
                }
            }
            //上浮大值
            if (a[i] < a[max]) {
                swap(a, i, max);
            }
        }
    }

    //交换值
    public static void swap(int a[], int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

基数排序 O(d(n+r))

【d代表关键字有d位，n代表n个记录，r代表r个空队列】
基数排序(radix sort)，相对于常见的比较排序，基数排序是一种分配式排序，即通过将所有数字分配到应在的位置最后再覆盖到原数组完成排序的过程。

public static void radixSort(int[] a) {
        //位数
        int digit = 1;
        //作为排序后数组的新下标
        int newIndex = 0;
        //供基数排序使用的二维数组，第一维度固定10位0~9，第二维度根据下标依次存放每次基数排序的结果
        int[][] container = new int[10][a.length];
        //第一维度每个数组的内容计数，最少为10，防止数组全是个位数时越界，例如五位数组最大值为8，counter.length=5 ，counter[8]就越界
        int counterLength = 10;
        if (a.length > 10) {
            counterLength = a.length;
        }
        int[] counter = new int[counterLength];
        //算出数组中最大的值，用来确定最大位
        int max = a[0];
        int maxDigit = 0;
        for (int i = 0; i < a.length; i++) {
            if (a[i] > max) {
                max = a[i];
            }
        }
        while (max > 0) {
            max /= 10;
            maxDigit++;
        }
        //对每位进行排序
        while (digit <= maxDigit) {
            //对每个数值该位取余,container[remainder]，并计数该位置上数值的下标counter[remainder]
            for (int num : a) {
                int remainder = (num / digit) % 10;
                container[remainder][counter[remainder]] = num;
                counter[remainder]++;
            }
            //将上一步放入容器的数值依次覆盖到远数组中
            for (int i = 0; i < 10; i++) {
                for (int j = 0; j < counter[i]; j++) {
                    a[newIndex] = container[i][j];
                    newIndex++;
                }
                counter[i] = 0;
            }
            digit *= 10;
            newIndex = 0;
        }
    }