经典排序算法

一、介绍

作为入门级基本算法，徒手写出是基本要求，下面列取几种基本的算法实现。

可以查看对应的动画演示，可以更好的理解排序方法

二、实现

2.1）冒泡排序

package com.banmoon.algorithm.order;

import java.util.Arrays;
import java.util.Random;

/**
 * 冒泡算法
 */
public class Demo01 {

    public static void main(String[] args) {
        int length = 10;
        int[] arr = new int[length];
        Random random = new Random();
        for (int i = 0; i < length; i++)
            arr[i] = random.nextInt(length);
        System.out.println("排序前的数组：" + Arrays.toString(arr));
        int[] sortArr = sort(arr);
        System.out.println("排序后的数组：" + Arrays.toString(sortArr));
    }

    public static int[] sort(int[] arr){
        for (int i = 0; i < arr.length-1; i++) {
            for (int j = i+1; j < arr.length; j++) {
                if(arr[i]>arr[j]){
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }
        return arr;
    }

}

比较相邻的元素。如果第一个比第二个大，就交换它们两个

对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素会是最大的数

针对所有的元素重复以上的步骤，除了最后一个

重复步骤1~3，直到排序完成

2.2）快速排序

package com.banmoon.algorithm.order;

import java.util.Arrays;
import java.util.Random;

/**
 * 快速排序
 */
public class Demo02 {

    public static void main(String[] args) {
        int length = 10;
        int[] arr = new int[length];
        Random random = new Random();
        for (int i = 0; i < length; i++)
            arr[i] = random.nextInt(length);
        System.out.println("排序前的数组：" + Arrays.toString(arr));
        int[] sortArr = sort(arr, 0 , arr.length-1);
        System.out.println("排序后的数组：" + Arrays.toString(sortArr));
    }

    private static int[] sort(int[] arr, int start, int end) {
        // 在递归过程中，会传入只有一个元素的数组，也就是start和end相等，将不做排序处理
        if(start<end){
            // 定义比较的标准数
            int standard = arr[start];
            // 定义低位和高位的下标
            int low = start;
            int high = end;
            // 循环让对应下标的值和标准数对比，进行迁移
            while (low<high){
                // 先判断高位下标的数
                while (low<high && standard<=arr[high])
                    high--;
                // 将高位的值赋值给低位
                arr[low] = arr[high];

                // 再判断低位下标的数
                while (low<high && arr[low]<=standard)
                    low++;
                arr[high] = arr[low];
            }
            arr[low] = standard;
            // 将分割左边的数组，递归进行处理
            sort(arr, start, low);
            // 将分割右边的数组，递归进行处理
            sort(arr, low+1, end);
        }
        return arr;
    }

}

定义一个标准数，作为比较

将比这个标准数小的放在左边，比标准数大的放在右边

左边放一个下标会向后移动一位，右边放一个下标会向前移动一位，直到左右两边下标重合

会根据重合的下标，重新划分高位低位，进行递归，将重复1-3

2.3）插入排序

package com.banmoon.algorithm.order;

import java.util.Arrays;
import java.util.Random;

/**
 * 插入排序
 */
public class Demo03 {

    public static void main(String[] args) {
        int length = 10;
        int[] arr = new int[length];
        Random random = new Random();
        for (int i = 0; i < length; i++)
            arr[i] = random.nextInt(length);
        System.out.println("排序前的数组：" + Arrays.toString(arr));
        int[] sortArr = sort(arr);
        System.out.println("排序后的数组：" + Arrays.toString(sortArr));
    }

    public static int[] sort(int[] arr){
        // 从第二个元素开始向后遍历
        for (int i = 1; i < arr.length; i++) {
            // 当前元素和前一个元素进行对比，如果当前元素小的话
            if(arr[i]<arr[i-1]){
                // 则记录当前元素进行记录
                int temp = arr[i];
                int j;
                // 对当前元素下标前的元素进行遍历，如果前一个元素比当前元素大，则将前一个元素向后移动位置
                for (j = i-1; j>=0 && temp<arr[j]; j--) {
                    arr[j+1] = arr[j];
                }
                // 直到结束后，将移动的下标，赋值当前元素
                arr[j+1] = temp;
            }
        }
        return arr;
    }

}

从第二个数开始向后遍历

每一个数都将向前遍历，根据自己的大小找到自己的位置

2.4）希尔排序

package com.banmoon.algorithm.order;

import java.util.Arrays;
import java.util.Random;

/**
 * 希尔排序
 */
public class Demo04 {

    public static void main(String[] args) {
        int length = 10;
        int[] arr = new int[length];
        Random random = new Random();
        for (int i = 0; i < length; i++)
            arr[i] = random.nextInt(length);
        System.out.println("排序前的数组：" + Arrays.toString(arr));
        int[] sortArr = sort(arr);
        System.out.println("排序后的数组：" + Arrays.toString(sortArr));
    }

    public static int[] sort(int[] arr){
        // 定义步长
        int step = arr.length/2;
        // 遍历步长，直到为1后执行最后一次
        while (step>0){
            // 从步长开始，遍历数组后的元素
            for (int i = step; i < arr.length; i++) {
                // 遍历同组内的元素，通过步长，从后向前遍历
                for (int j = i-step; j >= 0; j-=step) {
                    if(arr[j]>arr[j+step]){
                        int temp = arr[j];
                        arr[j] = arr[j+step];
                        arr[j+step] = temp;
                    }
                }
            }
            // 对步长进行二分缩短
            step /= 2;
        }
        return arr;
    }

}

希尔排序是插入排序的升级版，如果一个很小的数出现在了最末的位置，那只是插入排序的效率将会大大降低。

希尔排序则是，通过步长，将元素化为同一组，让他们在同组中进行插入排序

定义步长，初始步长为n/2，最后一次步长则为1

同插入排序一样，选择第二个元素，向前遍历找到他自己的位置。希尔排序这边同理，从步长位置开始，往前遍历步长个位置，找到他自己元素的位置

直到步长为1，进行最后一次插入逻辑后，完成排序

2.5）选择排序

package com.banmoon.algorithm.order;

import java.util.Arrays;
import java.util.Random;

/**
 * 选择排序
 */
public class Demo05 {

    public static void main(String[] args) {
        int length = 10;
        int[] arr = new int[length];
        Random random = new Random();
        for (int i = 0; i < length; i++)
            arr[i] = random.nextInt(length);
        System.out.println("排序前的数组：" + Arrays.toString(arr));
        int[] sortArr = sort(arr);
        System.out.println("排序后的数组：" + Arrays.toString(sortArr));
    }

    public static int[] sort(int[] arr){
        for (int i = 0; i < arr.length-1; i++) {
            int tempIndex = i;
            for (int j = i+1; j < arr.length; j++) {
                if(arr[tempIndex]>arr[j])
                    tempIndex = j;
            }
            int temp = arr[i];
            arr[i] = arr[tempIndex];
            arr[tempIndex] = temp;
        }
        return arr;
    }

}

从第0个开始向后遍历，每次初始默认自己是最小的，并记录下标

每一个元素，都会向后遍历，选择看看有没有比自己还要小的。如果有，覆盖下标

当步骤2走完，当前下标元素和最小下标元素进行替换

重复步骤1-3，玩成排序

选择排序和冒泡排序的遍历有点像，但不同出现在选择是记录最小的小标，最后开始替换；冒泡则是每次比较后，都可能会进行一次替换，保证当前下标元素永远是最小的。

2.6）归并排序

package com.banmoon.algorithm.order;

import java.util.Arrays;
import java.util.Random;

/**
 * 归并排序
 */
public class Demo06 {

    public static void main(String[] args) {
        int length = 10;
        int[] arr = new int[length];
        Random random = new Random();
        for (int i = 0; i < length; i++)
            arr[i] = random.nextInt(length);
        System.out.println("排序前的数组：" + Arrays.toString(arr));
        int[] sortArr = sort(arr, 0, arr.length-1);
        System.out.println("排序后的数组：" + Arrays.toString(sortArr));
    }

    public static int[] sort(int[] arr, int start, int end){
        if(start<end){
            // 找到中间的下标
            int mid = (start +end)/2;
            // 开始至中间，为一个数组，进行递归
            sort(arr, start, mid);
            // 中间至结束，为一个数组，进行递归
            sort(arr, mid+1, end);
            // 归并两个左右两个数组
            marge(arr, start, mid, end);
        }
        return arr;
    }

    /**
     * 归并排序
     * @param arr
     * @param start 开始元素的下标
     * @param mid   中间，左开右闭，
     * @param end   结束元素的下标
     */
    public static void marge(int[] arr, int start, int mid, int end){
        // 需要创建一个新的数组容器
        int[] tempArr = new int[end-start+1];
        // 定义下标
        int i = start;
        int j = mid+1;
        // 定义容器的下标
        int index = 0;
        while (i<=mid && j<=end){
            if(arr[i]<=arr[j]){
                tempArr[index] = arr[i];
                i++;
            }else {
                tempArr[index] = arr[j];
                j++;
            }
            index++;
        }
        // 查看还有哪部分没有遍历完
        while (i<=mid){
            tempArr[index] = arr[i];
            i++;
            index++;
        }
        while (j<=end){
            tempArr[index] = arr[j];
            j++;
            index++;
        }
        // 还要将排序好的临时容器中的数，放回到原数组中
        for (int k = 0; k < tempArr.length; k++) {
            arr[start+k] = tempArr[k];
        }
    }

}

归并排序的思想来自于，两个已经有序的数组进行有序合并。

如[1, 3, 5, 7, 9]和[2, 4, 6, 8]，将合并成[1, 2, 3, 4, 5, 6, 7, 8, 9]

对上面两个数组进行有序合并很简单

记录两个下标，左右两边的元素两两进行比较，谁小就谁先进入新数组；同时下标向后移动

直到一方下标移动完成，将另一方剩下的全部丢进新数组

经过上面的步骤，合并排序完成。但是如果是只有一个数组，且数据都还不是有序的呢，那将如何进行排序呢。

传入一个数组，只需要定义左下标，中间下标，右下标，就可以确定出两个数组了

左下标到中间下标的元素算作左数组

中间下标+1到右下标的元素算作右数组

当一个无序的数组，定义两边数组相关参数，向下递归。将它的左右数组缩小，最小为左右数组都只有一个元素时，进行上面步骤1-2有序合并

每一次递归，都可以看做将两个有序数组进行有序合并，而这次新合并出来的有序数组，将会作为上级调用者的左右有序数组

2.7）基数排序

package com.banmoon.algorithm.order;

import com.sun.jmx.remote.internal.ArrayQueue;

import java.util.*;
import java.util.function.Function;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

/**
 * 基数排序
 */
public class Demo07 {

    public static void main(String[] args) {
//        int[] arr = {128, 359, 26, 78, 98, 5, 789, 12, 6, 2};
        int[] arr = {2, 9, 7, 8, 3, 5, 4, 1, 6, 0};
        System.out.println("排序前的数组：" + Arrays.toString(arr));
        int[] sortArr = sort(arr);
        System.out.println("排序后的数组：" + Arrays.toString(sortArr));
    }

    public static int[] sort(int[] arr){
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if(max<arr[i])
                max = arr[i];
        }
        int maxLength = String.valueOf(max).length();
        Map<Integer, LinkedList> containerMap = IntStream.range(0, 10).boxed()
                .collect(Collectors.toMap(Function.identity(), a -> new LinkedList()));
        for (int i = 0, n=1; i < maxLength; i++, n*=10) {
            for (int j = 0; j < arr.length; j++) {
                int temp = arr[j]/n%10;
                containerMap.get(temp).add(arr[j]);
            }
            final int[] index = {0};
            IntStream.range(0, 10).boxed().forEach(key -> {
                LinkedList list = containerMap.get(key);
                for (int k = 0; k < list.size(); k++) {
                    arr[index[0]] = (int) list.get(k);
                    index[0]++;
                }
                containerMap.put(key, new LinkedList());
            });
        }
        return arr;
    }

}

基数排序，主要使用了分类，利用了以空间换时间的思想。

数组中的元素将，遍历他们的 $10^{n}$ 位，如个位、十位、百位……这将取决于数组中最大的那个数

每次都将对数组中的元素进行判断，判断当前位上是哪个数字，再放进对应的队列中

如果当前为个位遍历，判断123，则将放入序号为3的队列之中

这样的队列一共有10个，分别为标记为0~9

当数组中的元素都判断完成，依次从0~9的顺序从队列取数，放入到数组中

重复上面步骤1~3，直到遍历完成最大的一位，会发现数组排序完成