[算法]十大经典排序算法的Java实现

前言

排序的算法有二十几种，但常见一般是有十种或是八种。我就取其中的十种，一一介绍下。

排序算法的java实现

冒泡排序

冒泡排序介绍

1. 时间复杂度为 O(N^2)
2. 空间复杂度为 O(1)
3. 冒泡排序所需要的交换操作次数和数组中的逆序度相等

冒泡排序的Java实现

这是最基础的排序算法之一。就是循环遍历元素，从底部开始逐一比较元素大小，如果大于则交换位置

/**
 * 冒泡排序
 * @author wanxp
 */
public class BubbleSorter implements Sorter{
    @Override
    public void sort(int[] arrays, int length) {
        //比较的重点右边逐渐减小
        int maxTemp = 0;
        for (int i = length - 1;i >= 0;i--) {
            //从数组左边开始比较
            for (int j = 0;j < i;j++) {
                //比较大小，交换
                if(arrays[j] > arrays[j+1]) {
                    maxTemp = arrays[j];
                    arrays[j] = arrays[j+1];
                    arrays[j+1] = maxTemp;
                }
            }
        }
    }

    @Override
    public String name() {
        return "Bubble Sort";
    }
}

选择排序

选择排序

1. 首先通过扫描数组找到其中最小的元素
2. 然后将它与第一个元素交换（如果第一个元素就是最小元素的话那么它就和自己交换）
3. 在剩下的数组中找到最小的元素，然后将它与第二个元素交换
4. 重复1-3

选择排序特点

1. 最好、最坏和平均时间复杂度都是 O(N^2)
2. 空间复杂度是 O(1) , 它是一个原地排序算法
3. 选择排序不是一个稳定的排序算法，因为每次的交换会改变相等元素之间的相对位置
4. 运行时间与输入无关，因为每次扫描并不能为下一次扫描提供什么有用的信息
5. 数据的移动是最少的，只有 N 次，交换次数等于数组的长度，这种线性性质是很多排序方法做不到的

选择排序的Java实现

/**
 * 选择排序
 * @author wanxp
 */
public class SelectSorter implements Sorter{
    @Override
    public void sort(int[] arrays, int length) {
        //比较的重点右边逐渐减小
        int maxTemp = 0;
        int maxIndex = 0;
        for (int i = length - 1;i >= 0;i--) {
            maxIndex = i;
            //从数组左边开始比较
            for (int j = 0;j < i;j++) {
                //比较大小，交换
                if(arrays[j] > arrays[maxIndex]) {
                    maxIndex = j;
                }
            }
            maxTemp = arrays[maxIndex];
            arrays[maxIndex] = arrays[i];
            arrays[i] = maxTemp;
        }
    }

    @Override
    public String name() {
        return "Select Sort";
    }
}

插入排序

插入排序操作步骤

N为需要排序数组，长度为n

1. p = 1
2. 缓存N(p)值y
3. y与左侧元素对比，若左侧元素x大于y，则x所在位置右移一位
4. 再将x的左侧元素作为x与y对比
5. 重复 步骤3-4 直到y不大于x，y放入x右侧
6. p累加1，重复 步骤2-5

插入排序特点

1. 下标0到p-1之间的元素总是已经排序的状态
2. 位置稳定的，相等的情况下，排序的相对位置不变
3. 最坏情况有大量的位置移动

插入排序Java实现

/**
 * 插入排序
 * @author wanxp
 */
public class InsertionSorter implements Sorter{
    @Override
    public void sort(int[] arrays, int length) {
        int temp = 0;
        int i = 0;
        //下标p从1开始往上累加
        for (int p = 1;p < length;p++) {
            //缓存p处的值
            temp = arrays[p];
            //p处的值与左侧元素比较，直到遇到比其小的值，若是比其大的值则右移一格
            for (i = p;i > 0 && temp < arrays[i - 1];i--) {
                arrays[i] = arrays[i - 1];
            }
            //插入p处的值至比其小的右侧位置
            arrays[i] = temp;
        }
    }

    @Override
    public String name() {
        return "Insertion Sort";
    }
}

总结