Java常用的八种排序

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        return quickSort(nums);
    }

    // 冒泡排序（超时）
    vector<int> bubbleSort(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            for (int j = n-2; j >= i; --j) {
                if (nums[j] > nums[j+1]) {
                    swap(nums[j], nums[j+1]);
                }
            }
        }
        return nums;
    }

    // 选择排序（超时）
    vector<int> selectSort(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            int idx = i;
            for (int j = i; j < n; ++j) {
                if (nums[j] < nums[idx]) {
                    idx = j;
                }
            }
            swap(nums[i], nums[idx]);
        }
        return nums;
    }

    // 插入排序（超时）
    vector<int> insertSort(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            for (int j = i; j > 0 && nums[j] < nums[j-1]; --j) {
                swap(nums[j], nums[j-1]);
            }
        }
        return nums;
    }

    // 快速排序（24 ms）
    void qSort(vector<int>& nums, int l, int r) {
        if (l >= r) return;
        int m = l;
        for (int i = l; i < r; ++i) {
            if (nums[i] < nums[r]) {
                swap(nums[m++], nums[i]);
            }
        }
        swap(nums[m], nums[r]);
        qSort(nums, l, m-1);
        qSort(nums, m+1, r);
    }

    vector<int> quickSort(vector<int>& nums) {
        int n = nums.size();
        qSort(nums, 0, n-1);
        return nums;
    }

    // 归并排序（192 ms）
    vector<int> mSort(vector<int>& nums, int l, int r) {
        if (l >= r) return {nums[l]};
        int m = l+(r-l)/2;
        vector<int> lnums = mSort(nums, l, m);
        vector<int> rnums = mSort(nums, m+1, r);
        vector<int> res;
        int i = 0, j = 0;
        while (i <= m-l && j <= r-m-1) {
            if (lnums[i] < rnums[j]) {
                res.push_back(lnums[i++]);
            } else {
                res.push_back(rnums[j++]);
            }
        }
        while (i <= m-l) {
            res.push_back(lnums[i++]);
        }
        while (j <= r-m-1) {
            res.push_back(rnums[j++]);
        }
        return res;
    }

    vector<int> mergeSort(vector<int>& nums) {
        int n = nums.size();
        nums = mSort(nums, 0, n-1);
        return nums;
    }

    // 归并排序 + 非递归（80 ms）
    vector<int> mergeSortNR(vector<int>& nums) {
        int n = nums.size();
        for (int len = 1; len < n; len <<= 1) {
            for (int l = 0; l < n-len; l += 2*len) {
                int m = l+len-1;
                int r = min(n-1, l+2*len-1);
                vector<int> res;
                int i = l, j = m+1;
                while (i <= m && j <= r) {
                    if (nums[i] < nums[j]) {
                        res.push_back(nums[i++]);
                    } else {
                        res.push_back(nums[j++]);
                    }
                }
                while (i <= m) {
                    res.push_back(nums[i++]);
                }
                while (j <= r) {
                    res.push_back(nums[j++]);
                }
                for (int i = l; i <= r; ++i) {
                    nums[i] = res[i-l];
                }
            }
        }
        return nums;
    }

    // 希尔排序（40 ms）
    vector<int> shellSort(vector<int>& nums) {
        int n = nums.size();
        for (int gap = n/2; gap > 0; gap /= 2) {
            for (int i = gap; i < n; ++i) {
                for (int j = i; j-gap >= 0 && nums[j-gap] > nums[j]; j -= gap) {
                    swap(nums[j-gap], nums[j]);
                }
            }
        }
        return nums;
    }

    // 计数排序（32 ms）
    vector<int> countSort(vector<int>& nums) {
        int n = nums.size();
        if (!n) return {};
        int minv = *min_element(nums.begin(), nums.end());
        int maxv = *max_element(nums.begin(), nums.end());
        int m = maxv-minv+1;
        vector<int> count(m, 0);
        for (int i = 0; i < n; ++i) {
            count[nums[i]-minv]++;
        }
        vector<int> res;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < count[i]; ++j) {
                res.push_back(i+minv);
            }
        }
        return res;
    }

    // 基数排序（不适用于负数）
    vector<int> radixSort(vector<int>& nums) {
        int n = nums.size();
        int maxv = *max_element(nums.begin(), nums.end());
        int maxd = 0;
        while (maxv > 0) {
            maxv /= 10;
            maxd++;
        }
        vector<int> count(10, 0), rank(n, 0);
        int base = 1;
        while (maxd > 0) {
            count.assign(10, 0);
            for (int i = 0; i < n; ++i) {
                count[(nums[i]/base)%10]++;
            }
            for (int i = 1; i < 10; ++i) {
                count[i] += count[i-1];
            }
            for (int i = n-1; i >= 0; --i) {
                rank[--count[(nums[i]/base)%10]] = nums[i];
            }
            for (int i = 0; i < n; ++i) {
                nums[i] = rank[i];
            }
            maxd--;
            base *= 10;
        }
        return nums;
    }

    // 桶排序 (20 ms)
    vector<int> bucketSort(vector<int>& nums) {
        int n = nums.size();
        int maxv = *max_element(nums.begin(), nums.end());
        int minv = *min_element(nums.begin(), nums.end());
        int bs = 1000;
        int m = (maxv-minv)/bs+1;
        vector<vector<int> > bucket(m);
        for (int i = 0; i < n; ++i) {
            bucket[(nums[i]-minv)/bs].push_back(nums[i]);
        }
        int idx = 0;
        for (int i = 0; i < m; ++i) {
            int sz = bucket[i].size();
            bucket[i] = quickSort(bucket[i]);
            for (int j = 0; j < sz; ++j) {
                nums[idx++] = bucket[i][j];
            }
        }
        return nums;
    }

    // 堆排序（32 ms）
    void adjust(vector<int>& nums, int p, int s) {
        while (2*p+1 < s) {
            int c1 = 2*p+1;
            int c2 = 2*p+2;
            int c = (c2<s && nums[c2]>nums[c1]) ? c2 : c1;
            if (nums[c] > nums[p]) swap(nums[c], nums[p]);
            else break;
            p = c;
        }
    }

    vector<int> heapSort(vector<int>& nums) {
        int n = nums.size();
        for (int i = n/2-1; i >= 0; --i) {
            adjust(nums, i, n);
        }
        for (int i = n-1; i > 0; --i) {
            swap(nums[0], nums[i]);
            adjust(nums, 0, i);
        }
        return nums;
    }
};

算法	最好	最坏	平均	空间	稳定性	是否基于比较
冒泡排序	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	$\checkmark$	$\checkmark$
选择排序	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	$\times$	$\checkmark$
插入排序	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	$\checkmark$	$\checkmark$
快速排序	$O(n\log n)$	$O(n^2)$	$O(n\log n)$	$O(\log n)$~$O(n)$	$\times$	$\checkmark$
归并排序	$O(n\log n)$	$O(n\log n)$	$O(n\log n)$	$O(n)$	$\checkmark$	$\checkmark$
希尔排序	$O(n^{1.3})$	$O(n^2)$	$O(n\log n)$~$O(n^2)$	$O(1)$	$\times$	$\checkmark$
计数排序	$O(n+k)$	$O(n+k)$	$O(n+k)$	$O(n+k)$	$\checkmark$	$\times$
基数排序	$O(nk)$	$O(nk)$	$O(nk)$	$O(n+k)$	$\checkmark$	$\times$
桶排序	$O(n)$	$O(n)$	$O(n)$	$O(n+m)$	$\checkmark$	$\times$
堆排序	$O(n\log n)$	$O(n\log n)$	$O(n\log n)$	$O(1)$	$\times$	$\checkmark$

维基百科

我觉得还是英文维基百科讲的比较详细、严谨。如果大家看的比较累的话，可以自己百度搜索相应的教程。

冒泡排序
https://en.wikipedia.org/wiki/Bubble_sort

选择排序
https://en.wikipedia.org/wiki/Selection_sort

插入排序
https://en.wikipedia.org/wiki/Insertion_sort

快速排序
https://en.wikipedia.org/wiki/Quicksort

归并排序
https://en.wikipedia.org/wiki/Merge_sort

希尔排序
https://en.wikipedia.org/wiki/Shellsort

计数排序
https://en.wikipedia.org/wiki/Counting_sort

基数排序
https://en.wikipedia.org/wiki/Radix_sort

桶排序
https://en.wikipedia.org/wiki/Bucket_sort

堆排序
https://en.wikipedia.org/wiki/Heapsort

代码实现

直接插入排序

经常碰到这样一类排序问题：把新的数据插入到已经排好的数据列中。

将第一个数和第二个数排序，然后构成一个有序序列

将第三个数插入进去，构成一个新的有序序列。

对第四个数、第五个数……直到最后一个数，重复第二步。

如何写成代码：

首先设定插入次数，即循环次数，for(int i=1;i<length;i++)，1个数的那次不用插入。

设定插入数和得到已经排好序列的最后一个数的位数。insertNum和j=i-1。

从最后一个数开始向前循环，如果插入数小于当前数，就将当前数向后移动一位。

将当前数放置到空着的位置，即j+1。

代码实现如下：

希尔排序

对于直接插入排序问题，数据量巨大时。

将数的个数设为n，取奇数k=n/2，将下标差值为k的书分为一组，构成有序序列。

再取k=k/2 ，将下标差值为k的书分为一组，构成有序序列。

重复第二步，直到k=1执行简单插入排序。

如何写成代码：

首先确定分的组数。

然后对组中元素进行插入排序。

然后将length/2，重复1,2步，直到length=0为止。

代码实现如下：

简单选择排序

常用于取序列中最大最小的几个数时。

(如果每次比较都交换，那么就是交换排序；如果每次比较完一个循环再交换，就是简单选择排序。)

遍历整个序列，将最小的数放在最前面。

遍历剩下的序列，将最小的数放在最前面。

重复第二步，直到只剩下一个数。

如何写成代码：

首先确定循环次数，并且记住当前数字和当前位置。

将当前位置后面所有的数与当前数字进行对比，小数赋值给key，并记住小数的位置。

比对完成后，将最小的值与第一个数的值交换。

重复2、3步。

代码实现如下：

堆排序

对简单选择排序的优化。

将序列构建成大顶堆。

将根节点与最后一个节点交换，然后断开最后一个节点。

重复第一、二步，直到所有节点断开。

代码实现如下：

public void heapSort(int[] a){
    System.out.println("开始排序");
    int arrayLength=a.length;
    //循环建堆
    for(int i=0;i<arrayLength-1;i++){
        //建堆

        buildMaxHeap(a,arrayLength-1-i);
        //交换堆顶和最后一个元素
        swap(a,0,arrayLength-1-i);
        System.out.println(Arrays.toString(a));
    }
}
private void swap(int[] data, int i, int j) {
    // TODO Auto-generated method stub
    int tmp=data[i];
    data[i]=data[j];
    data[j]=tmp;
}
//对data数组从0到lastIndex建大顶堆
private void buildMaxHeap(int[] data, int lastIndex) {
    // TODO Auto-generated method stub
    //从lastIndex处节点（最后一个节点）的父节点开始
    for(int i=(lastIndex-1)/2;i>=0;i--){
        //k保存正在判断的节点
        int k=i;
        //如果当前k节点的子节点存在
        while(k*2+1<=lastIndex){
            //k节点的左子节点的索引
            int biggerIndex=2*k+1;
            //如果biggerIndex小于lastIndex，即biggerIndex+1代表的k节点的右子节点存在
            if(biggerIndex<lastIndex){
                //若果右子节点的值较大
                if(data[biggerIndex]<data[biggerIndex+1]){
                    //biggerIndex总是记录较大子节点的索引
                    biggerIndex++;
                }
            }
            //如果k节点的值小于其较大的子节点的值
            if(data[k]<data[biggerIndex]){
                //交换他们
                swap(data,k,biggerIndex);
                //将biggerIndex赋予k，开始while循环的下一次循环，重新保证k节点的值大于其左右子节点的值
                k=biggerIndex;
            }else{
                break;
            }
        }
    }
}

冒泡排序

一般不用。

将序列中所有元素两两比较，将最大的放在最后面。

将剩余序列中所有元素两两比较，将最大的放在最后面。

重复第二步，直到只剩下一个数。

如何写成代码：

设置循环次数。

设置开始比较的位数，和结束的位数。

两两比较，将最小的放到前面去。

重复2、3步，直到循环次数完毕。

代码实现如下：

6.快速排序

快速排序

要求时间最快时。

选择第一个数为p，小于p的数放在左边，大于p的数放在右边。

递归的将p左边和右边的数都按照第一步进行，直到不能递归。

代码实现如下：

归并排序

速度仅次于快排，内存少的时候使用，可以进行并行计算的时候使用。

选择相邻两个数组成一个有序序列。

选择相邻的两个有序序列组成一个有序序列。

重复第二步，直到全部组成一个有序序列。

代码实现如下：

public static void mergeSort(int[] numbers, int left, int right) {
    int t = 1;// 每组元素个数
    int size = right - left + 1;
    while (t < size) {
        int s = t;// 本次循环每组元素个数
        t = 2 * s;
        int i = left;
        while (i + (t - 1) < size) {
            merge(numbers, i, i + (s - 1), i + (t - 1));
            i += t;
        }
        if (i + (s - 1) < right)
            merge(numbers, i, i + (s - 1), right);
    }
}
private static void merge(int[] data, int p, int q, int r) {
    int[] B = new int[data.length];
    int s = p;
    int t = q + 1;
    int k = p;
    while (s <= q && t <= r) {
        if (data[s] <= data[t]) {
            B[k] = data[s];
            s++;
        } else {
            B[k] = data[t];
            t++;
        }
        k++;
    }
    if (s == q + 1)
        B[k++] = data[t++];
    else
        B[k++] = data[s++];
    for (int i = p; i <= r; i++)
        data[i] = B[i];
}

基数排序

用于大量数，很长的数进行排序时。

将所有的数的个位数取出，按照个位数进行排序，构成一个序列。

将新构成的所有的数的十位数取出，按照十位数进行排序，构成一个序列。

代码实现如下：

public void sort(int[] array) {
    //首先确定排序的趟数;
    int max = array[0];
    for (int i = 1; i < array.length; i++) {
        if (array[i] > max) {
            max = array[i];
        }
    }
    int time = 0;
    //判断位数;
    while (max > 0) {
        max /= 10;
        time++;
    }
    //建立10个队列;
    List<ArrayList> queue = new ArrayList<ArrayList>();
    for (int i = 0; i < 10; i++) {
        ArrayList<Integer> queue1 = new ArrayList<Integer>();
        queue.add(queue1);
    }
    //进行time次分配和收集;
    for (int i = 0; i < time; i++) {
        //分配数组元素;
        for (int j = 0; j < array.length; j++) {
            //得到数字的第time+1位数;
            int x = array[j] % (int) Math.pow(10, i + 1) / (int) Math.pow(10, i);
            ArrayList<Integer> queue2 = queue.get(x);
            queue2.add(array[j]);
            queue.set(x, queue2);
        }
        int count = 0;//元素计数器;
        //收集队列元素;
        for (int k = 0; k < 10; k++) {
            while (queue.get(k).size() > 0) {
                ArrayList<Integer> queue3 = queue.get(k);
                array[count] = queue3.get(0);
                queue3.remove(0);
                count++;
            }
        }
    }