数据结构_简单排序

JI,XIAOYONG...大约 4 分钟

简单排序

所有排序顺序为 小 → 大。

时间负责度都是 O(N²)。

排序速度：插入排序>选择排序>冒泡排序

冒泡排序

时间复杂度：O(N²)

最慢的排序，但是简单

规则如下：

从左到右，比较 a 和 b，如果a>b，就交换 a 和 b 的位置
再将 a，b 中较大的那个与 c 按照 2 的规则比较，直到最后一位
重复 1，2 直到没有待排序的项目

其思想是：每次选出当前未排序的元素中最大的元素并放到队尾（每次比较最大元素都会“冒泡”到队尾），这样当连续遍历 n 次后，每个元素都会排好序。

/**
     * 冒泡排序
     * 1. 每次比较前1~（n-i）个元素（i是排序次数），每次有大的就【移动】，
     * 这样子一轮比赛完毕最大的就在后面了
     * 2. 这样子比较n次就可以完成排序
     */
    fun bubbleSort(intArray: IntArray): IntArray {
        var result = intArray
        var size = result.size
        for (index in 0 until size) {
            for (x in 0 until size - index - 1) {
                if (result[x] > result[x + 1]) {//【注意】冒泡排序，每次比较满足条件就会交换
                    var temp = result[x]
                    result[x] = result[x + 1]
                    result[x + 1] = temp
                }
            }
        }
        return result
    }

选择排序

时间复杂度：O(N²)

因为交换次数少，所以比冒泡快

规则如下：

假设第一项值最大，设其坐标为max，从左到右依次比较max和其他元素，如果遇到比max大的，将 max 坐标指向该值
每轮结束后max就表示这轮比较最大的值坐标，将其与当前未排序的最后一项交换
这样重复步骤 1，2， n次就可以排序完成

其思想是：每次比较当前最大的值，记录下其坐标，等当前比较完成就和未比较的最后一位交换，（这样子避免每次比较都要交换）。同样这样子比较 n 次就可以完成排序。

/**
 * 选择排序
 * 1. 每次比较前1~（n-i）个元素（i是排序次数），如果有大的就记录下位置，一轮比较完毕后交换他和最后一位的位置
 * 2. 这样子比较n次就可以完成排序
 */
fun selectSort(intArray: IntArray): IntArray {
    var result = intArray
    var size = result.size
    for (index in 0 until size) {
        var max = 0//假设arr[0]最大
        for (x in 0 until size - index - 1) {
            if (result[max] < result[x + 1]) {//将max与每一项比较，注意这里参与比较的是max
                max = x + 1//遇到比max大的则记录下其位置 【注意】这里并没有交换
            }
        }
        //在每轮比较完毕后max就是这轮比较出来的最大值位置，将其放到对应位置
        var temp = result[size - index - 1]
        result[size - index - 1] = result[max]
        result[max] = temp
    }
    return result
}

插入排序

时间复杂度：O(N²)

比冒泡快一倍，比选择排序快一些

思想：假设一个标记元素的左边全部是有序数组，右边全是无序数组，那么只需要将右边的元素依次拿出来插入到左边的有序数组中即可。刚开始这个标记元素可以为 0 或者 1（假设一个元素就是有序的）。

/**
 * 插入排序
 * 假设右端数组是有序的，依次从左端数组取出元素比较，插入到右边的有序数组
 */
fun insertSort(intArray: IntArray): IntArray {

    var result = intArray
    var size = result.size

    for (insertIndex in 1 until size ) {//假设arr[0]已经是有序的，所以从1开始
        var insertPoint = result[insertIndex]
        for (index in insertIndex - 1 downTo  0) {
            if (insertPoint < result[index]) {
                //默认要插入的点是有序的，如果有比插入点大的，则将该点和插入点交换
                result[index + 1] = result[index]
                result[index] = insertPoint
            } else {
            //因为左边的数组是有序的，只要有比插入点小的元素，则剩下的肯定都小于该元素，不用再比较了
                break
            }
        }
    }

    return result
}