排序一个无序的数组

89 阅读 0 评论 59 点赞

我是靠谱客的博主拼搏唇彩，最近开发中收集的这篇文章主要介绍排序一个无序的数组，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

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

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


/**
* 冒泡排序，选择排序
*/
fun bubbingSort(nums: MutableList<Int>):MutableList<Int>{
//第一种方式，先找最大的，从尾部开始慢慢往开头排序
//
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<Int>()
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<Int>):List<Int>{
if (nums.size < 2){
//基线条件：为空或者只包含一个元素的数组是"有序"的
return nums
}else {
val pivot = nums[0] //递归条件
val less = nums.filterIndexed { index, i -> index > 0 && i <=pivot }
val greater = nums.filterIndexed { index, i ->
index > 0 && i > pivot}
return quickSort(less) + pivot + quickSort(greater)
}
}