排序一个无序的数组

2024-06-19 13:47| 来源: 网络整理| 查看: 265

目前楼主已知有三种算法可以实现：冒泡法（暴力破解法）、二分法、快速排序（可以看作二分法的进阶版本）

冒泡法：构造一个空的数组长度一样的数组b，从0开始循环数组a（源数组），拿每个数，如果这个数大于对比的数就替换，如果小就继续直到比较完，这样子数组b中放入的数据就是都是a中剩下的最小的数据了。当循环结束的时候就完成了排列。时间复杂度：O（n^2）

/** * 冒泡排序，选择排序 */ fun bubbingSort(nums: MutableList):MutableList{ //第一种方式，先找最大的，从尾部开始慢慢往开头排序 // for (i in 1 until nums.size){ // for (j in 0 ..nums.size -1 - i){ // if (nums[j] > nums[j + 1]){ // val temp = nums[j+1] // nums[j+1] = nums[j] // nums[j] = temp // } // } // } //第二种方式，先找最小的，从头部开始慢慢往尾部移动 val list = mutableListOf() for (i in nums.indices){ var min = nums[i] var index = i for (j in i until nums.size){ if (min > nums[j]){ min = nums[j] index = j } } list.add(min) nums[index] = nums[i] } return list }

二分法：时间复杂度：n*log(n),这边需要注意一下，二分法本来的复杂度是：log(n),但是因为是乱序的需要排序，所以需要先把数组排成有序然后再二分插入值，所以需要循环n

/** * 二分法 */ fun sortArray(nums:IntArray){ val tempArray : IntArray = IntArray(nums.size) nums.forEachIndexed { index, number -> if (index == 0){ tempArray[0] = nums[0] } else if (index == 1){ if (nums[index] >= nums[index -1]){ tempArray[1] = nums[index] tempArray[0] = nums[index - 1] } else { tempArray[0] = nums[index] tempArray[1] = nums[index - 1] } }else { var m = index var n = 0 var middle = (m+ n+1) /2 for (j in 0 .. m){ if (nums[index] < tempArray[middle] && nums[index] > tempArray[n]){ //已经得到位置了 break } else if (nums[index] > tempArray[middle]) { n = middle middle = (m+ n+1) /2 } else if (nums[index] < tempArray[middle]){ m = middle middle = (m+ n+1) /2 } } var tempTwo = tempArray.copyOf() tempArray[middle] = nums[index] if (middle < index){ for (k in middle+1 ..index){ tempArray[k] = tempTwo[k - 1] } } else { tempArray[middle] = nums[index] } } } println("-----------") for (i in tempArray) { println(i) } } }

快速排序：时间复杂度：n*log(n)

/** * 快速排序 */ fun quickSort(nums: List):List{ if (nums.size < 2){ //基线条件：为空或者只包含一个元素的数组是"有序"的 return nums }else { val pivot = nums[0] //递归条件 val less = nums.filterIndexed { index, i -> index > 0 && i index > 0 && i > pivot} return quickSort(less) + pivot + quickSort(greater) } }

【本文地址】

排序一个无序的数组

排序一个无序的数组

今日新闻

推荐新闻