排序算法

排序算法算是我们学习算法的入门篇，在正式介绍各种排序算法前，先介绍一下要用到的一些术语：

• 稳定排序：如果a本来在b的前面，且a==b，排序以后a依旧在b的前面，那就是稳定排序，否在是非稳定排序
• 原地排序：就是在排序过程中不申请多于的存储空间，只利用原来存储待排数据的存储空间进行比较和交换的数据排序。而非原地排序就是需要利用额外的数组来辅助排序。

总览：

选择排序

代码思路

首先找到数组中最小的元素，其次将其与数组中第一个元素交换位置，然后在剩下的数组中找到最小的元素，然后和第二个元素交换，以此类推，直到交换完毕。

特点

数据移动最少，运行时间与数据输入时的顺序无关

复杂度与排序特点

• 时间复杂度：O(n²)
• 空间复杂度：O(1)
• 非稳定排序
• 原地排序

使用环境

数据量少

算法代码

 // 从小到大
private static void sort(int[] nums){
        int n=nums.length;
        int minIndex,temp;
        for(int i=0;i<n-1;i++){
            minIndex=i;
            for(int j=i+1;j<n;j++){
                if(nums[j]<nums[minIndex]){
                    minIndex=j;
                }
            }
            temp=nums[i];
            nums[i]=nums[minIndex];
            nums[minIndex]=temp;
        }
    }

插入排序

代码思路

像抓牌一样，将牌暂时放入现在的适当的位置。当到最后一个元素时就排序完成了。就像把一个无序数组中的数据整合到一个有序数组中。

特点

运行时间与输入情况有关，对于一个部分有序（数组中元素离最终位置都不远，或者一个有序的大数组加一个小数组）来说速度比较快

复杂度

• 时间复杂度：O(n²)
• 空间复杂度：O(1)
• 稳定排序
• 原地排序

使用环境

数组基本有序，或者一个有序的大数组中添加一些小数据。

算法代码

// 从小到大排序
private static void sort(int[] nums) {
        int n=nums.length;
        int preIndex,current;
        for(int i=1;i<n;i++){
            preIndex=i-1;
            current=nums[i];
            while (preIndex>=0&&nums[preIndex]>current){
                nums[preIndex+1]=nums[preIndex];
                preIndex--;
            }
            nums[preIndex+1]=current;
        }
    }

冒泡排序

代码思路

十分简单，重复访问，依次比较进行交换，交换过多

• 比较相邻元素，大就交换
• 从第一对开始，到最后一对，一次排序后保证最大的位于末尾
• 重复n次

特点

思路简单

复杂度

• 时间复杂度：O(n2)
• 空间复杂度：O(1)
• 稳定排序
• 原地排序

使用环境

无适用场景一般用于学习算法。

算法代码

private static void sort(int[] nums) {
        int n=nums.length;
        for(int i=0;i<n-1;i++){
            for(int j=0;j<n-i-1;j++){
                if(nums[j]>nums[j+1]){
                    int temp=nums[j];
                    nums[j]=nums[j+1];
                    nums[j+1]=temp;
                }
            }
        }
    }

改良冒泡排序算法

在我们遍历的过程中，会发现从开始第一队到最后一对都没有发生交换，此时意味着，剩下这些待排序的元素已经是有序的数据，无序再次排序，所以我们可以引入一个标志，当遇到此情况的时候，直接跳出循环。减少无意义的比较和缩短排序时间。

希尔排序（缩小增量排序）

代码思路

希尔排序是插入排序的一种变种，原来插入排序的优势在于数据基本有序的情况下性能很好，但是如果原数组中的元素距离其正确位置很远的话，效率就不是很高，而希尔排序正是优化了这一点。

希尔排序就是为了加快速度简单的改进了插入排序，交换不相邻的元素以对数据的局部进行排序。

先使数组中任意间隔为h的元素是有序的。最后对于一个以1结尾的的h序列我们都能够将其排序。

具体步骤：

• 先将整个待排序的记录序列分隔成若干子序列，分别进行直接插入排序

• • 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
  • 按增量序列个数k，对序列进行k 趟排序；
  • 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

特点

基于插入排序的快速排序

复杂度

• 时间复杂度：O(nlogn)
• 空间复杂度：O(1)
• 非稳定排序
• 原地排序

使用环境

大型数组，大多数情况下希尔排序都是比较高效且简单的算法

算法代码

 private static void sort(int[] nums) {
        int n=nums.length;
        int gap=n/2;
        while (gap>0){
            for(int j=gap;j<n;j++){
                int i=j;
                while ((i>=gap&&nums[i-gap]>nums[i])){
                    int temp=nums[i];
                    nums[i]=nums[i-gap];
                    nums[i-gap]=temp;
                    i-=gap;
                }
            }
            gap=gap/2;
        }
    }

需要注意的是，对各个分组进行插入的时候并不是先对一个组排序完了再对另一个组排序，而是轮流对每个组进行排序。

归并排序

代码思路

将一个大的无序数组有序，我们可以利用归并的思想来进行排序，即将大问题化为小问题进行解决。

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

特点

速度较快，不受输入数据的影响，所需额外空间与N成正比

复杂度

• 时间复杂度：O(nlogn)
• 空间复杂度：O(n)
• 稳定排序
• 非原地排序

使用环境

算法代码

private static void sort(int[] nums,int start,int end) {
    // 如果left==right，表明数组中只有一个元素，则不用递归排序
      if(start<end){
          // 将大数组分割成两个小数组
          int mid=(start+end)/2;
          // 分别排序
          sort(nums,start,mid);
          sort(nums,mid+1,end);
          // 进行合并
          merge(nums,start,mid,end);
      }
    }
    // 合并函数，把两个有序的数组合并起来
    private static void merge(int[] nums,int left,int mid,int right){
        int []tmp=new int[nums.length];
        int p1=left,p2=mid+1,k=0;
        while (p1<=mid && p2<=right){
            if(nums[p1]<=nums[p2])
                tmp[k++]=nums[p1++];
            else
                tmp[k++]=nums[p2++];
        }
        while (p1<=mid)
            tmp[k++]=nums[p1++];
        while (p2<=right)
            tmp[k++]=nums[p2++];
        // 把数组复制到原数组中
        for (int i=left;i<=right;i++)
            nums[i]=tmp[i];

    }

快排（三取样切分）

代码思路

我们从数组中选择一个元素，我们把这个元素称之为中轴元素吧，然后把数组中所有小于中轴元素的元素放在其左边，所有大于或等于中轴元素的元素放在其右边，显然，此时中轴元素所处的位置的是有序的。也就是说，我们无需再移动中轴元素的位置。

从中轴元素那里开始把大的数组切割成两个小的数组(两个数组都不包含中轴元素)，接着我们通过递归的方式，让中轴元素左边的数组和右边的数组也重复同样的操作，直到数组的大小为1，此时每个元素都处于有序的位置。

特点

应用广泛，原地排序，几乎不需要额外的空间

复杂度

• 时间复杂度：O(nlogn)
• 空间复杂度：O(logn)
• 非稳定排序
• 原地排序

使用环境

广泛

算法代码

    private static void sort(int[] nums,int start,int end) {
     if(nums.length<0)
         return;
     if(start>=end)
         return;
     int left=start;
     int right=end;
     int temp=nums[left];
     while (left<right){
         while (left<right && nums[right]>=temp)
             right--;
         nums[left]=nums[right];
         while (left<right && nums[left]<=temp)
             left++;
         nums[right]=nums[left];
     }
     nums[left]=temp;
     sort(nums,start,left-1);
     sort(nums,left+1,end);
    }

堆排序

代码思路

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

• 将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
• 将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
• 由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。

复杂度

• 时间复杂度：O(nlogn)
• 空间复杂度：O(1)
• 非稳定排序
• 原地排序

算法代码

public static void sort(int[] list) {
        //构造初始堆,从第一个非叶子节点开始调整,左右孩子节点中较大的交换到父节点中
        for (int i = (list.length) / 2 - 1; i >= 0; i--) {
            headAdjust(list, list.length, i);
        }
        //排序，将最大的节点放在堆尾，然后从根节点重新调整
        for (int i = list.length - 1; i >= 1; i--) {
            int temp = list[0];
            list[0] = list[i];
            list[i] = temp;
            headAdjust(list, i, 0);
        }
    }

    private static void headAdjust(int[] list, int len, int i) {
        int k = i, temp = list[i], index = 2 * k + 1;
        while (index < len) {
            if (index + 1 < len) {
                if (list[index] < list[index + 1]) {
                    index = index + 1;
                }
            }
            if (list[index] > temp) {
                list[k] = list[index];
                k = index;
                index = 2 * k + 1;
            } else {
                break;
            }
        }
        list[k] = temp;
    }

计数排序

代码思路

计数排序是一种适合于最大值和最小值的差值不是不是很大的排序。

基本思想：就是把数组元素作为数组的下标，然后用一个临时数组统计该元素出现的次数，例如 temp[i] = m, 表示元素 i 一共出现了 m 次。最后再把临时数组统计的数据从小到大汇总起来，此时汇总起来是数据是有序的。

复杂度

• 时间复杂度：O(n+k)
• 空间复杂度：O(n+k)
• 稳定排序
• 非原地排序

使用环境

其排序速度快于任何比较排序算法。当k不是很大并且序列比较集中时，计数排序是一个很有效的排序算法。

算法代码

 public static void sortCount(int[] arr, int min, int max) {
        int len = arr.length;
        int[] tem = new int[max - min + 1];
        for(int i = 0; i < len; i++) {
            tem[arr[i] - min] += 1;
        }
        for(int i = 0, index = 0; i < tem.length; i++) {
            int item = tem[i];
            while(item-- != 0) {
                arr[index++] = i + min;
            }
        }
    }

桶排序

代码思路

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。

• 设置一个定量的数组当作空桶；
• 遍历输入数据，并且把数据一个一个放到对应的桶里去；
• 对每个不是空的桶进行排序；
• 从不是空的桶里把排好序的数据拼接起来。

复杂度

• 桶排序最好情况下使用线性时间O(n)，桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度，因为其它部分的时间复杂度都为O(n)。很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。但相应的空间消耗就会增大
• 时间复杂度：O(n+k)
• 空间复杂度：O(n+k)
• 稳定排序
• 非原地排序

算法代码

    public static void main(String[] args) {
        // 输入元素均在 [0, 10) 这个区间内
        float[] arr = new float[] { 0.12f, 2.6f, 8.8f, 7.6f, 7.2f, 6.3f, 9.0f, 1.6f, 5.6f, 2.4f };
        bucketSort(arr);
        System.out.println(Arrays.toString(arr));

    }
    public static void bucketSort(float[] arr) {
        // 新建一个桶的集合
        ArrayList<LinkedList<Float>> buckets = new ArrayList<LinkedList<Float>>();
        for (int i = 0; i < 10; i++) {
            // 新建一个桶，并将其添加到桶的集合中去。
            // 由于桶内元素会频繁的插入，所以选择 LinkedList 作为桶的数据结构
            buckets.add(new LinkedList<Float>());
        }
        // 将输入数据全部放入桶中并完成排序
        for (float data : arr) {
            int index = getBucketIndex(data);
            insertSort(buckets.get(index), data);
        }
        // 将桶中元素全部取出来并放入 arr 中输出
        int index = 0;
        for (LinkedList<Float> bucket : buckets) {
            for (Float data : bucket) {
                arr[index++] = data;
            }
        }
    }

    /**
     * 计算得到输入元素应该放到哪个桶内
     */
    public static int getBucketIndex(float data) {
        // 这里例子写的比较简单，仅使用浮点数的整数部分作为其桶的索引值
        // 实际开发中需要根据场景具体设计
        return (int) data;
    }

    /**
     * 我们选择插入排序作为桶内元素排序的方法 每当有一个新元素到来时，我们都调用该方法将其插入到恰当的位置
     */
    public static void insertSort(List<Float> bucket, float data) {
        ListIterator<Float> it = bucket.listIterator();
        boolean insertFlag = true;
        while (it.hasNext()) {
            if (data <= it.next()) {
                it.previous(); // 把迭代器的位置偏移回上一个位置
                it.add(data); // 把数据插入到迭代器的当前位置
                insertFlag = false;
                break;
            }
        }
        if (insertFlag) {
            bucket.add(data); // 否则把数据插入到链表末端
        }
    }

基数排序

代码思路

基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。

• 取得数组中的最大数，并取得位数；
• arr为原始数组，从最低位开始取每个位组成radix数组；
• 对radix进行计数排序（利用计数排序适用于小范围数的特点）；

特点

针对计数排序进行优化的一种算法。

复杂度

• 时间复杂度：O(kn)
• 空间复杂度：O(n+k)
• 稳定排序
• 非原地排序

算法代码

public static void main(String[] args) {

        int[] arr = new int[] { 5,789,2138,456,3,1,9,1,13,4984,3 };
        radixSort(arr,10000);
        System.out.println(Arrays.toString(arr));

    }
    private static void radixSort(int[] array,int d)
    {
        int n=1;//代表位数对应的数：1,10,100...
        int k=0;//保存每一位排序后的结果用于下一位的排序输入
        int length=array.length;
        int[][] bucket=new int[10][length];//排序桶用于保存每次排序后的结果，这一位上排序结果相同的数字放在同一个桶里
        int[] order=new int[length];//用于保存每个桶里有多少个数字
        while(n<d)
        {
            for(int num:array) //将数组array里的每个数字放在相应的桶里
            {
                int digit=(num/n)%10;
                bucket[digit][order[digit]]=num;
                order[digit]++;
            }
            for(int i=0;i<length;i++)//将前一个循环生成的桶里的数据覆盖到原数组中用于保存这一位的排序结果
            {
                if(order[i]!=0)//这个桶里有数据，从上到下遍历这个桶并将数据保存到原数组中
                {
                    for(int j=0;j<order[i];j++)
                    {
                        array[k]=bucket[i][j];
                        k++;
                    }
                }
                order[i]=0;//将桶里计数器置0，用于下一次位排序
            }
            n*=10;
            k=0;//将k置0，用于下一轮保存位排序结果
        }

    }

睡眠排序

代码思路

代码思路倒是很简单，就是利用线程睡眠来进行排序，让线程睡眠、

特点

娱乐算法，没啥特点就是好玩

算法代码

public static void sleepSort(int[] array) {
        for (int i : array) {
            new Thread(()->{
                try {
                    Thread.sleep(i);
                } catch (Exception e) {
                    e.printStackTrace();
                }
                System.out.println(i);
            }).start();
        }
    }

    public static void main(String[] args) {
        int[] array = { 10, 30, 50, 60, 100, 40, 150, 200, 70 };
        sleepSort(array);
    }

随机排序排序

代码思路

就是让系统随机排序，然后验证是否有序

特点

巨复杂，看命

算法代码

  public static void randSortX(int [] array){
        List<Integer> list=new ArrayList<>();
        for (Integer integer : array) {
            list.add(integer);
        }
        int pre=0;
        int index=0;
        while(true){
            pre=0;
            for (index = 1; index < list.size(); index++) {
                if(list.get(index)>list.get(pre)){
                    pre++;
                }else{
                    break;
                }
            }
            if(pre+1==list.size()){
                break;
            }
            Collections.shuffle(list);
        }
        System.out.println(list.toString());
    }
    public static void main(String[] args) {
        int[] array = { 10, 30, 50, 60, 100, 40, 150, 200, 70 };
        randSortX(array);
    }

来源：https://www.cnblogs.com/javazhonghu/p/14230299.html