排序算法

基于比较的排序

选择排序

选择排序的思路是：从当前还未排好序的区域中找到最小的值，和这个区域的第一个值进行交换，这种交换行为一共进行n次，每次交换行为都会以O(n)的复杂度来寻找当前区间的最小值，所以选择排序的时间复杂度是O(n²)。
例如 1 3 5 4 2，将会按照以下的顺序来进行排序:

1. 在1 3 5 4 2中遍历找到1是最小值，和第0位的1交换
2. 在3 5 4 2中 遍历找到2是最小值，和第1位(原数组)的3交换
3. 在5 4 3中遍历找到3是最小值，和第2位的5交换
4. 在4 5中遍历找到4是最小值， 和第3位的4交换
5. 在5中遍历找到5是最小值，和第4位的5交换、

• 严格**O(n²)**

可以发现的是 ，无论这个数组的分布是怎么样的，选择排序的执行步骤不会因为数组数据的分布而改变，因此最优、平均、最差的时间复杂度都是O(n²) 。

• 不稳定

  当数组中有**相等**的元素的时候，选择排序是不稳定的，即原本相等元素的相对位置可能会发生变化。 

• 空间复杂度

选择排序的空间复杂度为O(1)

/*
    选择排序
    每次选出一个最小的数，与第一位进行交换
 */
public class SelectSort {
    public static void main(String[] args) {
        int[] array = new int[]{1,3,5,4,2};
        selectSort(array);
        for (int i : array) {
            System.out.print(i+" ");
        }
    }
    public static void selectSort(int[] array) {
        for (int i=0;i<array.length;i++) {
            //选出从i到array.length-1的最小值i
            int min = Integer.MAX_VALUE;
            int minIndex = i;
            for (int j=i;j<array.length;j++) {
                //把这个最小值和对应的索引位置找出来
                if (array[j] < min) {
                    min = array[j];
                    minIndex = j ;
                }
            }
            swap(array,i,minIndex);
        }
    }
    public static void swap(int[] array,int i,int j) {
        int tmp = array[i] ;
        array[i] = array[j];
        array[j] = tmp;
    }
}

冒泡排序

冒泡排序指的是每次排序都先把当前最大的数放到无序部分的尾部 ，经过n次冒泡之后达到整体有序。 每次冒泡的负责度是O(n)，冒n次泡，所以总体复杂度为O(n²)
例如 2 1 3，将会按照以下的顺序来进行排序:

1. 第一轮冒泡
   1. 发现2 > 1，二者交换，数组变为1 2 3
   2. 发现2 < 3，本轮结束 , 当前数组的最大值3已经到了**index=2**的位置上
2. 第二轮冒泡
   1. 发现1 < 2，本轮结束 ，当前部分的最大值2已经到了index = 1的位置上
3. 第三轮冒泡

只有一个元素了，排序完成了

• 严格**O(n²)**

可以发现的是 ，无论这个数组的分布是怎么样的，选择排序的执行步骤不会因为数组数据的分布而改变，因此最优、平均、最差的时间复杂度都是O(n²) 。 但是冒泡排序经过优化，最优的复杂度可以为**O(n)**。

• 稳定

冒泡排序是稳定的排序算法

• 空间复杂度

冒泡排序的空间复杂度为O(1)

public class BubbleSort {
    public static void main(String[] args) {
        int[] array = new int[]{1,3,5,4,2};
        bubbleSort(array);
        for (int i : array) {
            System.out.print(i+" ");
        }
    }
    public static void bubbleSort(int[] array) {
        for (int i=array.length-1;i>=0;i--) {
            //0到i就是每次冒泡的范围
            for (int j=0;j<i;j++) {
                //执行具体的冒泡算法
                if (array[j] > array[j+1]) {
                    swap(array,j,j+1);
                }
            }
        }
    }
    public static void swap(int[] array,int i,int j) {
        int tmp = array[i] ;
        array[i] = array[j];
        array[j] = tmp;
    }
}

插入排序

当前有有序区间A与无序区间B，在B中遍历，将每次在**B**中遍历出来的数插入到**A**中合适的位置，一个一个向前插，直到有序为止。
插入排序即从0号元素开始构建这个有序区间的过程。
例如 1 3 5 4 2，将会按照以下的顺序来进行排序：

1. 将3插入到[1]
   1. 发现array[1] < array[0] ，下一轮循环
2. 将5插入到[1,3]
   1. 发现array[1] < array[2]，下一轮循环
3. 将4插入到[1 3 5]
   1. 发现array[2] > array[3]，交换之后变为1 3 4 5
   2. 发现array[1] < array[2]，下一轮循环
4. 将2插入到[1 3 4 5]
   1. 发现array[3] > array[4]，交换变为 1 3 4 2 5
   2. array[2] > array[3]，交换变为 1 3 2 4 5
   3. array[1] > array[2], 交换变为 1 2 3 4 5
5. 排序结束

• 时间复杂度

插入排序要进行n次插入，每次插入的复杂度为O(1) - O(n)，所以插入排序的平均和最差复杂度为**O(n²)**，最优复杂度即已经排好序了，为**O(n)**。

• 稳定性

插入排序是稳定的

• 空间复杂度

插入排序的空间复杂度为O(1)

public class InsertSort {
    public static void main(String[] args) {
        int[] array = new int[]{1,3,5,4,2};
        insertSort(array);
        for (int i : array) {
            System.out.print(i+" ");
        }
    }
    public static void insertSort(int[] array) {
        //第0个元素肯定是有序的，所以从第1个元素开始插入
        for (int i=1;i<array.length;i++) {
            //向有序区间插入array[i]
            for (int j=i-1;j>=0&&array[j]>array[j+1];j--) {
                //从i-1开始，如果array[j]>array[i]说明j位置比i位置，两个应该交换，直到array[i]插入到合适的位置
                swap(array,j,j+1);
            }
        }
    }
    public static void swap(int[] array,int i,int j) {
        int tmp = array[i] ;
        array[i] = array[j];
        array[j] = tmp;
    }
}

归并排序

归并排序是分治思想在排序中的应用 ，归并排序将一个数组的排序问题分解为两个子数组的排序子问题，将问题规模降低到logn，通过递归完成排序。
以1 3 5 4 2为例，归并排序的过程如下:

归并排序的递归逻辑如下:

1. 左子区间归并排序
2. 右子区间归并排序
3. 左右子区间归并

• 时间复杂度

归并排序的时间复杂度可以表示为T(n) = 2*T(n/2) + O(n)，即一个数组的排序问题可以分解为两个规模相等的子数组排序问题再加上一个两数组合并的时间复杂度，可以用master公式进行计算，时间复杂度为O(NlogN)，同时**在任何情况下的时间复杂度也都为O(NlogN)。

• 空间复杂度

归并排序的时间复杂度为O(n),每次merge都用到了一个O(n)数组,所以是O(n)

• 稳定性

归并排序是稳定的排序算法

public class MergeSort {
    public static void main(String[] args) {
        int[] array = new int[]{10,9,8,7,6,5,4,3,2,1};
        mergeSort(array,0,array.length-1);
        for (int i : array) {
            System.out.print(i+" ");
        }
    }
    //给数组中left到right范围的子序列做归并排序
    public static void mergeSort(int[] array,int left,int right) {
        if (left == right) {
            //说明这个子数组只有一个值了，一定是有序的,直接返回即可
            return ;
        }
        //递归，再分子数组
        //先得到中间位置(mid = left + (right-left)/2)
        int mid = left + ((right-left) >> 1);
        mergeSort(array,left,mid);
        mergeSort(array,mid+1,right);
        //左右子序列排好序了，现在把左右子序列做一个归并
        merge(array,left,mid+1,right);
    }
    //index1是左子序列的起始值
    //index2是有右子序列的起始值
    //right是右子序列的终点
    public static void merge(int[] array,int index1,int index2,int right) {
        //index1是左子序列的位置
        //index2是右子序列的位置
        int left = index1;
        int[] tmp = new int[right-index1+1];
        int record = index2;
        int index = 0 ;
        while (index1 < record && index2<=right) {
            tmp[index++] = array[index1]>=array[index2]? array[index2++]:array[index1++];
        }
        while (index1 < record) {
            tmp[index++] = array[index1++];
        }
        while (index2 <= right) {
            tmp[index++] = array[index2++];
        }
        for (int i=0;i<tmp.length;i++) {
            array[left+i] = tmp[i];
        }
    }
}

快速排序

快速排序也是一种通过递归分解子问题来排序的算法，在多次递归中，每次递归都确定一个数的位置，让这个数左边的数都<=,让右边的数都>，从而确定这个数的位置。 在多次递归中确定每一个数的位置，从而有序。例如3 5 1 4 2,第一次递归就是确定3的位置，将数组变为1 2 3 5 4,然后分解子问题为1 2 和5 4。
快速排序在发展中一共有三个版本，复杂度逐渐优化

• 版本1

每一次的快速排序都只固定子序列头元素（或尾元素）的位置，经过<n次快速排序最终解决问题。 时间复杂度为O(n²)， 因为在最差数据分布情况下，每一次快排只能确定一个数的相对位置。
例如5 4 3 2 1 ，

1. 确定5的位置 ： 4 3 2 1 5，需要和之后的4个数作比较
2. 确定4的位置 ： 3 2 1 4 5，需要和之后的3个数作比较
3. 确定3的位置 ： 2 1 3 4 5，需要和之后的2个数作比较
4. 确定2的位置 ： 1 2 3 4 5，需要和之后的1个数作比较
5. 确定1的位置， 排序结束

可以发现在这种情况下，整个排序过程中，一共比较了(n+1)*n/2次，所以时间复杂度O(n²)

public class QuickSort1 {
    public static void main(String[] args) {
        int[] array = new int[]{5,4,6,7,2,3,0,1,5};
        quickSort(array,0,array.length-1);
        for (int i : array) {
            System.out.print(i + " ");
        }
    }

    //给array的left到right的序列排序
    public static void quickSort(int[] array, int left, int right) {
        if (left >= right) {
            return;
        }
        //确定元素array[left]的位置
        int index = getIndex(array,left,right);
        quickSort(array,left,index-1);
        quickSort(array,index+1,right);
    }

    public static int getIndex(int[] array, int left, int right) {
        //默认key是第一个数
        int key = array[left];
        while (left < right) {
            //找到右边第一个小于key的数字
            while (left < right && array[right] >= key) {
                right--;
            }
            //替换array[left]
            array[left] = array[right];
            //找到左边第一个大于key的数字
            while (left < right && array[left] <= key) {
                left++;
            }
            //替换array[left]
            array[right] = array[left];
        }
        //找到这个位置，然后把key赋值上去
        array[left] = key;
        return left;
    }
    public static void swap(int[] array,int i,int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
}

• 版本2

版本2在1的基础上，通过荷兰国旗问题拓展，在能够进一步提高排序的效率，但是时间复杂度仍然为**O(n²)**，问题与版本1一样，每次只选择子序列的头元素(或尾元素)来计算位置，当选中的数位置比较偏的时候，复杂度为**O(n²)**。
版本2每次寻找元素位置的时候 ，会直接把所有和这个元素相等的元素的位置都确定下来。以5 5 1 3 6为例，在第一次递归之后，数组会变为1 3 5 5 6(如果是版本1就是5 1 3 5 6)，然后再去排序子数组3 1 和 2。相比版本1有一定程度上的优化。
在算法上，这种算法需要同时维护相等元素序列的左位置和右位置。

public class QuickSort2 {
    public static void main(String[] args) {
        int[] array = new int[]{10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
        quickSort(array,0,array.length-1);
        for (int i : array) {
            System.out.print(i + " ");
        }
    }
    //给array的left到right的序列排序
    public static void quickSort(int[] array, int left, int right) {
        if (left >= right) {
            return;
        }
        //确定和元素array[left]相等的所有元素的位置
        //indexs[0]是这些连续元素的左边界 indexs[1]是右边界
        int[] indexs = getIndex(array,left,right);
        quickSort(array,left,indexs[0]-1);
        quickSort(array,indexs[1]+1,right);
    }

    public static int[] getIndex(int[] array, int left, int right) {
        int key = array[left];
        //确定key的位置
        //用三个指针来完成运算
        int index = left; //遍历子数组
        int index1 = left-1; //小于key的右边界
        int index2 = right+1; //大于key的左边界
        int[] ans = new int[2];
        while (index < index2) {
            if (array[index] < key) {
                //小于k,那就放到左边界(和左边界交换)，然后左边界右移,index右移
                swap(array,index++,++index1);
            } else if (array[index] > key) {
                //大于k,那就放到右边界（和右边界交换），然后右边界左移，因为交换过来的数不知道情况，所以index不用++,接下来还需要继续判断
                swap(array,index,--index2);
            } else {
                index++;
            }
        }
        ans[0] = index1+1;
        ans[1] = index2-1;
        return ans;
    }
    public static void swap(int[] array,int i,int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
}

• 版本3

  最终版，时间复杂度为**O(NlogN)**。 版本1与版本2时间复杂度的问题在于，每次只选择一个固定位置的元素来计算这个元素的排序位置，这样就无法排除O(n²)情况下的数据分布。
  版本3的改进在于，每次随机选择一个子序列中的元素来计算位置，这样的话最坏情况和最好情况就成为了一个概率性事件，在经过期望计算之后，可以证明算法的事件复杂度为O(NlogN)。

• 时间复杂度

快速排序的时间复杂度是**O(nlogn)**

• 空间复杂度

空间复杂度是O(logn), 快排整个流程下来分了logn级别次区域

• 稳定性

快速排序是不稳定的排序算法 , 因为在分区操作中单个元素的位置确定过程中会有交换步骤,就有可能造成不稳定

public class QuickSort2 {
    public static void main(String[] args) {
        int[] array = new int[]{5,4,6,7,2,3,0,1,5};
        quickSort(array,0,array.length-1);
        for (int i : array) {
            System.out.print(i + " ");
        }
    }

    //给array的left到right的序列排序
    public static void quickSort(int[] array, int left, int right) {
        if (left >= right) {
            return;
        }
        //确定和元素array[left]相等的所有元素的位置
        //indexs[0]是这些连续元素的左边界 indexs[1]是右边界
        int[] indexs = getIndex(array,left,right);
        quickSort(array,left,indexs[0]-1);
        quickSort(array,indexs[1]+1,right);
    }

    public static int[] getIndex(int[] array, int left, int right) {
        //随机选择一个数
        int keyIndex = (int) (left + Math.floor(Math.random() * (right-left)));
        int key = array[keyIndex];
        //确定key的位置
        //用三个指针来完成运算
        int index = left; //遍历子数组
        int index1 = left-1; //小于key的右边界
        int index2 = right+1; //大于key的左边界
        int[] ans = new int[2];
        while (index < index2) {
            if (array[index] < key) {
                //小于k,那就放到左边界(和左边界交换)，然后左边界右移,index右移
                swap(array,index++,++index1);
            } else if (array[index] > key) {
                //大于k,那就放到右边界（和右边界交换），然后右边界左移，因为交换过来的数不知道情况，所以index不用++,接下来还需要继续判断
                swap(array,index,--index2);
            } else {
                index++;
            }
        }
        ans[0] = index1+1;
        ans[1] = index2-1;
        return ans;
    }
    public static void swap(int[] array,int i,int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
}

堆排序

堆排序通过堆结构来实现,由于堆是一棵完全二叉树结构, 所以可以用数组来表示,并可以通过索引来表示父子节点之间的关系 ,假设某节点的索引为index, 则其左子节点为index*2+1,右子节点为index*2+2, 其父节点为(index-1)/2
从小到大的排序需要通过大顶堆实现,而从大到小的排序需要通过小顶堆来实现,例如3 2 1进行正序堆排序的过程如下 :

• 时间复杂度

堆排序中, 挑选出每一个堆顶,然后与末尾元素交换之后进行堆调整, 堆调整为O(logn),调整n次,所以时间复杂度为O(nlogn)

• 空间复杂度

堆排序的空间复杂度为O(1),可以发现在整个排序过程中只占用了有限个变量

• 稳定性

堆排序是不稳定的排序算法, 因为堆排序完全是按照二叉树的性质进行排序,而不是单纯地逐个比较

//从小到大排序需要通过大根堆
public class HeapSort {
    public static void main(String[] args) {
        int[] array = new int[]{1,3,5,4,2};
        heapSort(array);
        for (int i : array) {
            System.out.print(i+" ");
        }
    }
    public static void heapSort(int[] array) {
        if (array == null || array.length < 2) {
            return ;
        }
        for (int i=0;i<array.length;i++) { //逐个把元素加进来，每一次都构建一个大顶堆 O(n)
            heapInsert(array,i); //O(logn)
        }
        //每次把堆顶最大的元素抽出来放到数组的最后，然后抽n次，就有序了
        int heapSize = array.length;
        //执行第一轮，先把最大的数和末尾呼唤
        swap(array,0,--heapSize);
        while (heapSize > 0) { //O(m)
            heapify(array,0,heapSize); //O(logn)
            //每次--heapSize的意思是相当于把之前那个最大数从堆中删除，因为已经排好序了
            swap(array,0,--heapSize);
        }
    }
    //index位置插入了元素之后调整堆
    public static void heapInsert(int[] array,int index) {
        while (array[index] >  array[(index-1)/2]) {
            swap(array,index,(index-1)/2);
            index = (index-1)/2;
        }
    }
    //调整以index位置为堆顶的堆
    public static void heapify(int[] array,int index,int headpSize) {
        //先算出左子节点
        int left = index*2+1;
        while (left < headpSize) { //只要还有左子节点
            //找到两个子节点之间最大的节点
            int largest = left+1<headpSize && array[left+1]>array[left] ? left+1 : left;
            //判断当前节点和子节点的最大值谁更大
            largest = array[index] > array[largest] ? index : largest;
            //当前这个点就是最大值，那就不用动了，已经是大顶堆了
            if (largest == index) {
                break;
            }
            //说明需要移动
            swap(array,index,largest);
            index = largest;
            left = index*2+1;
        }
    }
    public static void swap(int[] array,int i,int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
}

不基于比较的排序

不基于比较的排序主要有计数排序和基数排序两种 , 不基于比较的排序的特点是 : 排序需要结合实际的数据来判断.

计数排序

计数排序就是给一个足够大的桶,然后统计数组中每个数出现的次数, 最后从这个桶中输出排序的数组 。 显然这种排序方式的时间复杂度为O(n) ,但是缺点是要排序的数组的范围不能太大。

public class CountSort {
    public static void main(String[] args) {
        int[] array = new int[]{5,5,4,4,3,3,2,2,1,1};
        countSort(array);
        for (int i : array) {
            System.out.print(i+" ");
        }
    }
    public static void countSort(int[] array) {
        int[] buckets = new int[6];
        for (int i=0;i<array.length;i++) {
            buckets[array[i]]++;
        }
        int index = 0 ;
        for (int i=0;i<buckets.length;i++) {
            while (buckets[i] > 0) {
                array[index++] = i;
                buckets[i]--;
            }
        }
    }
}

基数排序

基数排序同样能做到O(n)级别的时间复杂度,但是局限是所要排序的元素必须是有进制的数字.

public class RadixSort {
    public static void main(String[] args) {
        int[] array = new int[]{10,1,213,2134,1,44,64,112};
        countSort(array);
        for (int i : array) {
            System.out.print(i+" ");
        }
    }
    public static int getRadix(int[] array) {
        int max = Integer.MIN_VALUE;
        for (int i=0;i<array.length;i++) {
            max = Math.max(array[i],max);
        }
        int radix = 0 ;
        while (max > 0) {
            radix++;
            max /= 10;
        }
        return radix;
    }
    public static void countSort(int[] array) {
        int radix = getRadix(array);
        //从个位到十位到百位...逐个排序 ， 十进制每一位有10种可能
        List<List<Integer>> buckets = new ArrayList<>(10);
        for (int i=0;i<10;i++) {
            buckets.add(new ArrayList<>());
        }
        int mod = 10;
        int div = 1;
        //要排序radix次
        for (int d=0;d<radix;d++) {
            int index = 0 ;
            //给这个进制排好序之后放到桶里面
            for (int i=0;i<array.length;i++) {
                int num = (array[i]/div) % mod;
                buckets.get(num).add(array[i]);
            }
            //桶中的元素重新给array
            for (int i=0;i<buckets.size();i++) {
                for (int j=0;j<buckets.get(i).size();j++) {
                    array[index++] = buckets.get(i).get(j);
                }
                buckets.get(i).clear();
            }
            div *= 10;
        }
    }
}

排序总结

在排序中,目前来说效率较高的主要是三种排序方法

快排是最快的排序算法,但缺点是空间复杂度为**O(n)**同时不稳定。 当要解决的问题对空间较为敏感的时候,应该用堆排序。 而当排序需要稳定性的时候,只能使用归并排序,其他情况下可以使用快速排序。