排序算法 Kotlin实现

/**
 * 排序算法
 */
class AlgorithmsSort {
    companion object {
        fun swap(arr: Array<Int>, index1: Int, index2: Int) {
            val tmp = arr[index1]
            arr[index1] = arr[index2]
            arr[index2] = tmp
        }

        /**
         * 冒泡排序
         *
         * 1.从开始第一对到结尾的最后一对,每对相邻元素第一个比第二个大就交换，直到第一轮结束，最大值被排到最后。
         * 从开始第一对到倒数第n对，重复第1步操作，第n大的元素被排序到倒数第n的位置
         * 时间复杂度：最坏O（n^2） 平均O（n^2）。
         */
        fun sortByBubble(arr: Array<Int>) {
            var haveSwap = false
            for (i in 0..arr.size - 1) {
                // 对除末尾i个元素之外的部分进行排序
                var sortLength = arr.size - i
                for (j in 0..sortLength - 2) {//这里多-1 因为以下用到arr[j+1] 防止越界
                    if (arr[j] > arr[j + 1]) {
                        swap(arr, j, j + 1)
                        haveSwap = true
                    }
                }
                // 这一轮从未发生过交换，则终止循环，排序完成
                if (!haveSwap) break
            }
        }

        /**
         * 快速排序 对冒泡排序的改进
         *
         * 先选一个元素，用它把整个队列过一遍，其左边的元素都小于或等于它，其右边的元素都大于或等于它。
         * 这时排序问题就被分割为两个子区间，分别对子区间快速排序(递归)。
         *
         * 最坏时间复杂度为O(n2)   平均时间复杂度为O(nlogn)
         */
        fun sortByQuick(arr: Array<Int>) {
            quicksort(arr, 0, arr.size - 1)
        }

        fun quicksort(arr: Array<Int>, minIndex: Int, maxIndex: Int) {
            if (minIndex >= maxIndex) {
                // fromIndex==toIndex排序结束
                return
            }
            val splitIndex = partition(arr, minIndex, maxIndex)
            // 对左区间单独排序
            quicksort(arr, minIndex, splitIndex - 1)
            // 对右区间单独排序
            quicksort(arr, splitIndex + 1, maxIndex)
        }

        /**
         * 分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边
         * @return 返回分隔元素key值所在的下标
         */
        fun partition(arr: Array<Int>, lowIndex: Int, highIndex: Int): Int {
            var low = lowIndex
            var high = highIndex
            var key = arr[low]

            while (low < high) {
                // 从后向前搜索小值 放low位置上
                while (arr[high] >= key && high > low) {
                    --high
                }
                arr[low] = arr[high]

                // 从前向后搜索大值 放新的high位置
                while (arr[low] <= key && high > low) {
                    ++low
                }
                arr[high] = arr[low]
                // 新的low位置空出 接收下一轮循环右边的小值
            }
            //  循环结束 空出的low位置接收key 此时low等于high
            arr[low] = key;
            return low
        }

        /**
         * 选择排序 对冒泡排序的改进
         *
         * 简单选择排序的基本思想：
         * 第1趟，在待排序记录r[1]~r[n]中选出最小的记录，将它与r[1]交换；
         * 第2趟，在待排序记录r[2]~r[n]中选出最小的记录，将它与r[2]交换；
         * 以此类推，第i趟在待排序记录r[i]~r[n]中选出最小的记录，将它与r[i]交换，使有序序列不断增长直到全部排序完毕
         * 时间复杂度：最坏O（n^2） 平均O（n^2）。
         */
        fun sortBySelect(arr: Array<Int>) {
            var length = arr.size
            var minIndex: Int;
            for (i in 0..length - 2) //n-1趟排序
            {
                minIndex = i
                for (j in (i + 1)..length - 1) {
                    if (arr[j] <= arr[minIndex]) {
                        minIndex = j
                    }
                }
                swap(arr, i, minIndex)
            }
        }

        /**
         * 插入排序
         *
         * 检查第i个数字，如果在它的左边的数字比它大，进行交换，这个动作一直继续下去，直到这个数字的左边数字比它还要小，就可以停止了。
         * 插入排序法主要的回圈有两个变数：i和j，每一次执行这个回圈，就会将第i个数字放到左边恰当的位置去。
         * 时间复杂度：最坏O(n^2)  平均O(n^2)  最好O(N) 
         */
        fun sortByInsert(arr: Array<Int>) {
            var length = arr.size - 1
            for (i in 1..length) {
                var insertValue = arr[i]
                var insertKey = i - 1
                while (insertKey >= 0 && insertValue < arr[insertKey]) {
                    arr[insertKey + 1] = arr[insertKey]
                    insertKey--
                }
                arr[insertKey + 1] = insertValue
            }
        }

        /**
         * 归并排序
         *
         * 第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
         * 第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置
         * 第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
         *  重复步骤3直到某一指针超出序列尾将另一序列剩下的所有元素直接复制到合并序列尾
         *
         * 时间复杂度为O(nlogn) 归并排序是利用二分法实现的排序算法，是一种比较快速的排序算法
         */
        fun sortByMerge(arr: Array<Int>) {
            merge_sort(arr, 0, arr.size - 1)
        }

        fun merge_sort(arr: Array<Int>, left: Int, right: Int) {
            if (left >= right)
                return
            var mid = (left + right) / 2;
            merge_sort(arr, left, mid);
            merge_sort(arr, mid + 1, right);
            merge(arr, left, mid + 1, right + 1);//归并的实现是右开区间的
        }

        fun merge(list: Array<Int>, left: Int, mid: Int, right: Int) {    // [lo,mid)   [mi,right)
            // 初始化两个数组
            var leftLength = mid - left + 1
            var rightLength = right - mid + 1
            var leftList = ArrayList<Int>(leftLength)
            var rightList = ArrayList<Int>(rightLength)
            for (i in left until mid) {
                leftList.add(list[i])
            }
            leftList.add(Int.MAX_VALUE)         // 哨兵
            for (i in mid until right) {
                rightList.add(list[i])
            }
            rightList.add(Int.MAX_VALUE)        // 哨兵

            // 归并
            var leftIndex = 0
            var rightIndex = 0
            var idx = left
            val n = right - left                     // 循环次数
            for (i in 1..n) {
                when {
                    leftList[leftIndex] < rightList[rightIndex] -> {
                        list[idx] = leftList[leftIndex]
                        leftIndex++
                    }
                    leftList[leftIndex] >= rightList[rightIndex] -> {
                        list[idx] = rightList[rightIndex]
                        rightIndex++
                    }
                }
                idx++
            }
        }
    }
}