本文的图片来源于冰狼爱魔
一、简单选择排序
1、思路
假设有x个数需要排序
1、将第
n个数与[n+1,x)范围内的数进行循环比较和交换，当n>n+1对应的数时，交换两个数；
2、重复1中的过程，直至这x个数循环结束，即n = x-1，此时得到升序排序的结果。
2、实现
/**
* 选择排序--简单选择排序
* */
val disorder:ArrayList<Int> = arrayListOf(-3,3,1,-1,2,0,7,0,5)
fun SelecteionSort(){
for (i in 0 until disorder.size){//循环1
var minValue = disorder[i]
for (j in (i+1) until disorder.size){//循环2
var value = disorder[j]
if (minValue > value){//交换值
val tmp = minValue
minValue = value
disorder[j] = tmp
}
}
disorder[i] = minValue
}
print("排序结果:${disorder.toString()}")
}
fun main(args:Array<String>){
print("排序耗时:${CodeRunTime {
SelecteionSort()
}} ms \n")
print("排序结果:$disorder \n")
}
排序耗时:3 ms
排序结果:[-3, -1, 0, 0, 1, 2, 3, 5, 7]
3、时间和空间复杂度
时间复杂度:O(n^2)
空间复杂度:O(1)
二、直接插入排序
1、思路
1、将
current与current-1比较，如果current-1>current，将current-1往后移动一个位置；
2、同时将current索引往前移动一个位置，继续开始1中的比较；
3、重复1-2中的过程，直至current达到数据开始端结束循环，将最初的currentValue插入到现在的位置；
4、循环1-3中的过程，直至current到达排序数据顶端，排序完成。
2、实现
/**
* 直接插入排序
* 必须满足至少有两个元素
* */
private val disorderList:ArrayList<Int> = arrayListOf(1,6,3,5,7,6,2,1,4,9,0,-1,-3)
fun InsertSort(disorder: ArrayList<Int>){
if (disorder.size < 2){
return
}
for (i in 1 until disorder.size){
var current = i
val currentValue = disorder[current]
//1、将current与current-1比较，如果current-1>current，将current-1往后移动一个位置
//2、同时将current索引往前移动一个位置，继续开始1中的比较
while (current >= 1 && disorder[current - 1] > currentValue){
disorder[current] = disorder[current - 1]
current -= 1
}
//3、重复1-2中的过程，直至current达到数据开始端结束循环，将最初的currentValue插入到现在的位置
disorder[current] = currentValue
}
print("**$disorder**\n")
}
**[-3, -1, 0, 1, 1, 2, 3, 4, 5, 6, 6, 7, 9]**
Process finished with exit code 0
3、时间和空间复杂度
时间复杂度:O(n^2)
空间复杂度:O(1)
三、冒泡排序
1、思路
一共有x个数据需要排序
1、将
i和i+1进行比较，如果i>i+1，则交换位置；
2、重复1中的过程，直至到达数据顶端；
3、从i+1开始，重复1-2中的过程，直至到达数据顶端，即i到达x-1的位置，结束循环。此时既是以升序方式排序的结果。
图片来自
2、实现
/**
* 冒泡排序
* 循环1控制着每次循环的起点
* 循环2控制着每次循环的终点
* */
fun BubbleSort(disorder: ArrayList<Int>){
for (i in 0 until disorder.size-1){//循环1
for (j in 0 until disorder.size-i-1){//循环2
if (disorder[j+1] < disorder[j]){
val tmp = disorder[j]
disorder[j] = disorder[j+1]
disorder[j+1] = tmp
}
}
}
print("**$disorder**\n")
}
**[-3, -1, 0, 1, 1, 2, 3, 4, 5, 6, 6, 7, 9]**
Process finished with exit code 0
3、时间和空间复杂度
时间复杂度:O(n^2)
空间复杂度:O(1)
四、快速排序
1、思路
1、在数组中选择一个基准数
pivot，一般选择第一个数作为pivot
2、将数组中大于基准数的，移动到基准数右边；小于基准数的，移动到基准数左边；
3、对基准数两边的数组子集分别重复1-2中的过程，直至每个新的数组子集中只含有一个元素。
快速排序采取“分治”的思想。分治就是将无序数组按照需求分割成若干子集进行操作，然后合并。递归是实现分治的重要方式。
2、实现
private val disorder:ArrayList<Int> = arrayListOf(-3,3,1,-1,2,0,7,0,5)
/**
* @param left 数据集从左开始查找的索引标记
* @param right 数据集从右往左开始查找的索引标记
* @param dataSource left和right要查找的数据集，也是排序的数据集
* */
fun QuickSort(left:Int,right:Int,dataSource:ArrayList<Int>){
//当left == right时表明最后需要排序的数据子集中只含有一个元素，就不用继续循环排序了
//当left < right时表明数据集中还有需要移动的数据
//所以，选择 left > right 这个作为递归出口
// print("Left:$left -- Right:$right \n")
if (left <= right){
val pivotKey = partition(left, right, dataSource)
QuickSort(left,pivotKey-1,dataSource)
QuickSort(pivotKey+1,right, dataSource)
}else{
return
}
}
/**
* @description 分割排序数组并进行移动
* @param left 数据集从左开始查找的索引标记
* @param right 数据集从右往左开始查找的索引标记
* @param dataSource 需要进行二分--分割的数据集
* @return 下一次排序的基准数对应的索引
* */
private fun partition(left:Int,right:Int,dataSource:ArrayList<Int>):Int{
//左哨兵
var left = left
//右哨兵
var right = right
//基准值 标杆值
val pivotValue = dataSource[left]
//当left和right还没有相遇
while (left != right){
//先移动right,当dataSource[right] >= pivotValue时，略过，继续移动
while (left < right && dataSource[right] >= pivotValue){
right -= 1
}
//当dataSource[right] < pivotValue时,将此时right对应的值移动到此时left的位置
dataSource[left] = dataSource[right]
//接着开始移动left，当dataSource[left]<pivotValue时，略过，继续移动
while (left < right && dataSource[left] < pivotValue){
left += 1
}
//当dataSource[left]>=pivotValue时，将此时此时left对应的值移动到right的位置
dataSource[right] = dataSource[left]
}
//此时left和right相遇，完成一次循环，将基准值移动到对应位置
dataSource[left] = pivotValue
return left
}
fun main(args:Array<String>){
print("运行时间:${CodeRunTime {
QuickSort(0, disorder.size-1, disorder)
}} ms \n")
print("排序后的结果:$disorder \n")
}
排序耗时:1
排序结果:[-3, -1, 0, 0, 1, 2, 3, 5, 7]
暂时这么多，后续会补充其它的，以及对上面几个算法的手绘图解。
网友评论