冒泡排序

说起排序，第一反应应该都是冒泡排序。很多人的算法入门都是从冒泡排序开始~
冒泡排序的英文名称‘Bubble Sort’，是最基础的交换排序。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


    fun bubbleSort(array: IntArray) {
        var tmp = 0
        for (i in 0 until array.size) {
            for (j in 0 until array.size - i - 1) {
                if (array[j] < array[j + 1]) {
                    tmp = array[j]
                    array[j] = array[j + 1]
                    array[j + 1] = tmp
                }
            }
        }
    }

冒泡排序优化

在实际应用中，某些数组中很有可能一大段数据本身就是连续的,或者进行几轮排序后有一大段数据有序，这些情况下还要继续做比较计算就很浪费效率。
比如下面俩数组：
a、[1,2,3,10,8,9]
b、[8,7,1,2,3,5,10]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


    fun bubbleSort(array: IntArray) {
        var tmp = 0

        var lastIndex = 0
        //需要比较的边界
        var sortEdge = array.size - 1
        for (i in 0 until array.size - 1) {
            var isSorted = true
            for (j in 0 until sortEdge) {
                if (array[j] > array[j + 1]) {
                    tmp = array[j]
                    array[j] = array[j + 1]
                    array[j + 1] = tmp

                    isSorted = false
                    lastIndex = j
                }
            }
            //更改需要比较的边界为最后一次交互数据的index
            sortEdge = lastIndex
            //一轮比较之后，如果还为true就表示数组已经是有序
            if (isSorted)
                break
        }
    }

冒泡排序优化

鸡尾酒排序