前言
在很多的业务场景中，我们都会使用到排序算法，常用的有冒泡排序，快速排序等等。在此我会将排序算法进行一个总结。
冒泡排序
冒泡排序，这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。
原理
- 比较相邻的元素，如果第一个比第二个大，则交换他们两个。
- 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
算法分析
时间复杂度
冒泡排序做理想的情况就是现有的数据已经是有序的了，那我们只需要循环一次就可以知道其是有序的，所以最好的情况为O(n)，最差的情况就是现有的数据是倒序的，那么我们需要进行(n-1)+(n-2)+....+2+1次比较，其时间复杂度为[n(n-1)]/2 = n^2/2-n/2 = O(n^2)，所以平均时间复杂度为O(n^2)。
稳定性
如果在一个待排序的序列中，存在2个相等的数，在排序后这2个数的相对位置保持不变，那么该排序算法是稳定的；否则是不稳定的。所以我们可以看出，冒泡排序是稳定的，因为如果我们有两个相同的数据，其在排序之后两个元素的先后顺序是不会被改变的。
代码
public class BubbleSort {
public static void main(String[] args) {
int[] ints = new int[]{4,1,5,2,6,0,7,10,8,9};
sort(ints);
System.out.println(Arrays.toString(ints));
}
private static void sort(int[] array){
int n = array.length;
for (int i = 0; i < n; i++){
int temp;
boolean flag = true;
for (int j = 0; j < n-i-1; j++){
if (array[j] > array[j+1]){
temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
flag = false;
}
}
if (flag){
break;
}
}
}
} 快速排序
快速排序是改进版的冒泡排序，它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
原理
- 首先设定一个分界值，通过该分界值将数组分成左右两部分。
- 将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。
- 然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
- 重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。
算法分析
时间复杂度
快速排序的一次划分算法从两头交替搜索，直到low和high重合，因此其时间复杂度是O(n)；而整个快速排序算法的时间复杂度与划分的趟数有关。
理想的情况是，每次划分所选择的中间数恰好将当前序列几乎等分，经过log2n趟划分，便可得到长度为1的子表。这样，整个算法的时间复杂度为O(nlog2n)。
最坏的情况是，每次所选的中间数是当前序列中的最大或最小元素，这使得每次划分所得的子表中一个为空表，另一子表的长度为原表的长度-1。这样，长度为n的数据表的快速排序需要经过n趟划分，使得整个排序算法的时间复杂度为O(n2)。可以证明，快速排序的平均时间复杂度也是O(nlog2n)。因此，该排序方法被认为是目前最好的一种内部排序方法。
稳定性
快速排序是不稳定的。
代码
public class QuickSort{
public static void main(String[] args){
int[] ints = new int[]{4,1,5,2,6,0,7,10,8,9};
sort(ints, 0, ints.length-1);
System.out.println(Arrays.toString(ints));
}
private static void sort(int[] array, int low, int high){
if(low < high){
int index = getIndex(array, low, high);
sort(array, 0, index-1);
sort(array, index+1, high);
}
}
private static int getIndex(int[] array, int low, int high){
int temp = array[low];
while(low < high){
while(low < high && array[high] >= temp){
high--;
}
array[low] = array[high];
while(low < high && array[low] <= temp){
low++;
}
array[high] = array[low];
}
array[low] = temp;
return low;
}
} 直接插入排序
直接插入排序（Straight Insertion Sort）是一种最简单的排序方法，其基本操作是将一条记录插入到已排好的有序表中，从而得到一个新的、记录数量增1的有序表。
原理
插入排序的基本方法是：每一步将一个待排序的元素，按其排序码的大小，插入到前面已经排好序的一组元素的适当位置上去，直到元素全部插入为止。可以选择不同的方法在已经排好序数据表中寻找插入位置。
算法分析
时间复杂度
最好的情况为：要插入的元素和只和有序序列中最后一个元素作比较，假如有n个元素，那么进行n-1次插入，每次插入只需遍历有序列表1次。故时间复杂度为O(n)。
最差的情况为：要插入的元素需要和有序列表中的元素依次比较，直到最后那一个元素，假如有n个元素，那么进行n-1次插入，总的遍历次数为1+2+...+(n-1) = (n^2 - 1)/2，时间复杂度为：O(n^2)。
综合为：O(n^2)
稳定性
直接插入排序是稳定的。
代码
public class StraightInsertionSort {
public static void main(String[] args) {
int[] ints = new int[]{4,1,5,2,6,0,7,10,8,9};
sort(ints);
System.out.println(Arrays.toString(ints));
}
private static void sort(int[] array){
int temp;
for (int i = 1; i < array.length; i++){
if (array[i] < array[i-1]){
temp = array[i];
for (int j = i; j >= 0; j--){
if (j > 0 && array[j-1] > temp){
array[j] = array[j-1];
} else {
array[j] = temp;
break;
}
}
}
}
}
} 选择排序
选择排序（Selection sort）是一种简单直观的排序算法。
原理
第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。
算法分析
时间复杂度
选择排序是表现最稳定的排序算法之一，因为无论什么数据进去都是O(n2)的时间复杂度。
稳定性
选择排序是稳定的。
代码
public class SelectionSort {
public static void main(String[] args) {
int[] ints = new int[]{4,1,5,2,6,0,7,10,8,9};
sort(ints);
System.out.println(Arrays.toString(ints));
}
private static void sort(int[] array){
for (int i = 0; i < array.length; i++){
int minIndex = i;
for (int j = i; j < array.length; j++){
if (array[j] < array[minIndex]){
minIndex = j;
}
}
int temp = array[minIndex];
array[minIndex] = array[i];
array[i] = temp;
}
}
} 希尔排序
希尔排序是希尔（Donald Shell） 于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。
原理
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
算法分析
时间复杂度
希尔排序O(n^（1.3—2）)
稳定性
选择排序是不稳定的。
代码
public class ShellSort {
public static void main(String[] args) {
int[] ints = new int[]{4,1,5,2,6,0,7,10,8,9};
sort(ints);
System.out.println(Arrays.toString(ints));
}
private static void sort(int[] array){
int len = array.length;
int temp, gap = len / 2;
while(gap > 0) {
for(int i=gap; i<len; i++){
temp = array[i];
int preIndex = i - gap;
while(preIndex >=0 && array[preIndex] > temp){
array[preIndex + gap] = array[preIndex];
preIndex -= gap;
}
array[preIndex + gap] = temp;
}
gap /= 2;
}
}
} 归并排序
和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(n log n）的时间复杂度。代价是需要额外的内存空间。归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。
原理
- 把长度为n的输入序列分成两个长度为n/2的子序列；
- 对这两个子序列分别采用归并排序；
- 将两个排序好的子序列合并成一个最终的排序序列。
算法分析
时间复杂度
归并排序的时间复杂度为O(nlog2n)
稳定性
归并排序是稳定的
代码
public class MergeSort {
public static void main(String[] args) {
int[] ints = new int[]{4,1,5,2,6,0,7,10,8,9};
int[] result = mergeSort(ints);
System.out.println(Arrays.toString(result));
}
private static int[] mergeSort(int[] array){
if (array.length < 2) return array;
int mid = array.length / 2;
int[] left = Arrays.copyOfRange(array, 0, mid);
int[] right = Arrays.copyOfRange(array, mid, array.length);
return merge(mergeSort(left), mergeSort(right));
}
private static int[] merge(int[] left, int[] right){
int[] result = new int[left.length + right.length];
for (int i = 0, j = 0, index = 0; index < result.length; index++){
if (i >= left.length){
result[index] = right[j++];
} else if (j >= right.length) {
result[index] = left[i++];
} else if (left[i] > right[j]) {
result[index] = right[j++];
} else {
result[index] = left[i++];
}
}
return result;
}
} 堆排序
堆排序（英语：Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
原理
堆
什么是堆，堆是具有以下性质的完全二叉树：
- 每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；
- 每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
同时，我们对堆中的结点按层进行编号，将这种逻辑结构映射到数组中就是下面这个样子
该数组从逻辑上讲就是一个堆结构，我们用简单的公式来描述一下堆的定义就是：
大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]
了解了这些定义。接下来，我们来看看堆排序的基本思想及基本步骤：
排序流程
将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。
- 将无需序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆（一般升序采用大顶堆，降序采用小顶堆);
- 将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;
- 重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。
算法分析
时间复杂度
在构建堆时的时间复杂度为O(n)，排序重建堆的时间复杂度为nlog(n)，所以总的时间复杂度为O(n+nlogn)=O(nlogn)。
稳定性
堆排序是不稳定的。
代码
public class HeapSort {
public static void main(String[] args) {
int[] ints = new int[]{4,1,5,2,6,0,7,10,8,9};
sort(ints);
System.out.println(Arrays.toString(ints));
}
/**
* 堆排序入口
* @param array 数组
* @return void
* @date 2020/3/10 12:52
*/
private static void sort(int[] array){
// 首先构建堆
buildHeap(array, array.length);
int length = array.length;
// 到这一步，一个堆就构建好了，此时要做的就是将最后一个节点和根节点做交换
for (int i = length - 1; i >= 0; i--){
swap(array, i, 0);
// 交换后重新构建堆，只需将前length-i个节点构建为堆，这样就完成了排序
heapify(array, i, 0);
}
}
/**
* 对某一个子树构建堆
* @param array 数组
* @param i 起始点
* @param length 堆的大小
* @return void
* @date 2020/3/10 12:31
*/
private static void heapify(int[] array, int length, int i){
// 首先判断这个递归的出口，当这个结点越界了，则直接返回
if (i >= length) return;
// 该节点的左子节点下标
int c1 = 2 * i + 1;
// 该节点的右子节点下标
int c2 = 2 * i + 2;
// 在这个子树中的最大值的下标
int max = i;
// 如果左子节点存在并且大于根节点，则将max修改为左子节点的下标
if (c1 < length && array[c1] > array[max]){
max = c1;
}
// 如果右子节点存在并且大于根节点，则将max修改为右子节点的下标
if (c2 < length && array[c2] > array[max]){
max = c2;
}
// 如果最大值不是根节点，则将根节点和最大值进行交换，交换后对下面的子树再进行重新构建堆，递归操作。
if (max != i){
swap(array, max, i);
heapify(array, length, max);
}
}
/**
* 构建堆
* @param array 需要构建堆的数组
* @param len 数组的长度
* @return void
* @date 2020/3/10 13:03
*/
private static void buildHeap(int[] array, int len){
// 构建堆需要从最后一个非叶子节点开始进行构建堆
int parent = (len - 2) >> 1;
for (int i = parent; i >= 0; i--){
// 对某个节点及其左右子节点进行构建堆
heapify(array, len, i);
}
}
/**
* 交换数组中两个下标中的元素
* @param array
* @param i
* @param j
* @return void
* @date 2020/3/10 13:03
*/
private static void swap(int[] array, int i, int j){
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
} 计数排序
计数排序是一个非基于比较的排序算法，该算法于1954年由 Harold H. Seward 提出。它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中k是整数的范围），快于任何比较排序算法。 [1] 当然这是一种牺牲空间换取时间的做法，而且当O(k)>O(nlog(n))的时候其效率反而不如基于比较的排序（基于比较的排序的时间复杂度在理论上的下限是O(nlog(n)), 如归并排序，堆排序）。
原理
计数排序 的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。计数排序使用一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。它只能对整数进行排序。
- 找出待排序的数组中最大和最小的元素；
- 统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
- 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
- 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。
算法分析
时间复杂度
时间复杂度为Ο(n+k)（其中k是整数的范围）
稳定性
计数排序是稳定的
代码
public class CountingSort {
public static void main(String[] args) {
int[] ints = new int[]{4,1,5,2,6,0,7,10,8,9,-1};
sort(ints);
System.out.println(Arrays.toString(ints));
}
private static void sort(int[] array){
if (array.length < 2) return;
// bias主要考虑到最小值为负数
int min = array[0], max = array[0], bias;
for (int i = 1; i < array.length; i++){
if (min > array[i]) {
min = array[i];
}
if (max < array[i]){
max = array[i];
}
}
bias = 0 -min;
int[] bucket = new int[max - min + 1];
Arrays.fill(bucket, 0);
for (int i = 0; i < array.length; i++){
bucket[array[i] + bias]++;
}
int index = 0, i = 0;
while (index < array.length) {
if (bucket[i] != 0){
array[index] = i - bias;
bucket[i]--;
index++;
} else {
i++;
}
}
}
} 基数排序
基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。
原理
基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以是稳定的。
- 取得数组中的最大数，并取得位数；
- arr为原始数组，从最低位开始取每个位组成radix数组；
- 对radix进行计数排序（利用计数排序适用于小范围数的特点）；
算法分析
时间复杂度
基数排序的时间复杂度为O(kn),n为数组长度，k为数组中的数的最大的位数；
稳定性
基数排序基于分别排序，分别收集，所以是稳定的。
代码
public class RadixSort {
public static void main(String[] args) {
int[] ints = new int[]{4,1,5,2,6,0,7,10,8,9,-3,-1};
int min = ints[0];
for (int i = 0; i < ints.length; i++){
min = Math.min(min, ints[i]);
}
int increment = Math.abs(min);
// 此处是考虑到包含负数
for (int i = 0; i < ints.length; i++){
ints[i] += increment;
}
sort(ints);
for (int i = 0; i < ints.length; i++){
ints[i] -= increment;
}
System.out.println(Arrays.toString(ints));
}
private static void sort(int[] array){
if (array == null || array.length < 2)
return;
int max = array[0], min = array[0];
for (int i = 0; i < array.length; i++){
max = Math.max(max, array[i]);
}
int maxDigit = 0;
while (max != 0){
max /= 10;
maxDigit++;
}
int mod = 10, div = 1;
ArrayList<ArrayList<Integer>> bucketList = new ArrayList<>();
for (int i = 0; i < 10; i++){
bucketList.add(new ArrayList<>());
}
for (int i = 0; i < maxDigit; i++, mod *= 10, div *= 10){
for (int j = 0; j < array.length; j++){
int num = (array[j] % mod) / div;
bucketList.get(num).add(array[j]);
}
int index = 0;
for (int j = 0; j < bucketList.size(); j++){
for (int k = 0; k < bucketList.get(j).size(); k++){
array[index++] = bucketList.get(j).get(k);
}
bucketList.get(j).clear();
}
}
}
} 
京公网安备 11010502036488号