排序
一、选择排序
话不多说，上代码
/**
* 选择排序
* 定义：找到数组中最小的元素，把它和index为0的元素交互，然后找到剩余中最小的元素，把它和index为1的交换，一直到最后一个
* 解释：使用双层for循环，外循环是控制比较的次数，内循环是作对比，交换位置
*/
fun AlagorithmsActivity.sort(arr : Array<Int>){
printArr(arr)
for (i in arr.indices){
for (j in i+1 until arr.size){
if (arr[i] > arr[j]){
exch(arr, i, j)
}
}
}
println("----------------排序前后对比---------------------")
printArr(arr)
}
/**
* 交换两个数
*/
private fun exch(arr: Array<Int>, i: Int, j: Int) {
val temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
}
/**
* 打印数据
*/
private fun printArr(arr: Array<Int>){
for (element in arr){
print(element)
}
println()
}
看下输出
I/System.out: 38292832343758104
----------------排序前后对比---------------------
I/System.out: 01222333344578889
二、插入排序
/**
* 插入排序
* 思路：默认第一个是排序好的，从第二个开始，和前面排序好的比较，插入到对应的位置，一直到最后一个，前面的都是排序好了的，插入到对应位置即可
* 解释：插入，就像打扑克牌一样，第一张牌放到一个位置，然后第二张牌对比下第一张，插入到对应位置，第三张对比前两张，继续插入到对应位置。。
* 一直到最后一张，插入到前面所有牌对应的位置
*/
fun AlagorithmsActivity.insertSort(arr : Array<Int>){
for (i in 1 until arr.size){
//for(int j = i; j > 0 && arr[j] < arr[j-1] ; j--) kotlin 的for循环用不了表达式，这个有些尴尬
var j = i
//因为之前的数组都是有序的，所以如果i对应的元素大于前一个，那么说明他比前面所有数都大，while结束。
//如果j对应的元素小于前一个，交换，继续跟前面的数比较，一直到大于就借宿while
while (j > 0 && arr[j] < arr[j-1] ){
exch(arr,j,j-1)
j--
}
}
}
就是这么任性～.jpeg
比较适合使用插入排序的有下面几种：
1.数组中每个元素距离它的最终位置不远；
2.一个有序的大数组接一个小数组
3.数组中只有那么几个元素不确定
对于上面的插入排序速度还可以优化一下，只要在内循环中将较大的元素都向右移动而不是交换两个元素。
那么这两种排序那种更快？都是Log（n*n）效率都不高，相对而言插入排序会好点
还有很多排序算法，未完待续～
2020/06/26
我又回来啦.jpg
三、希尔排序
这个希尔排序有点难，我裸写了一波，犯了三个错误，不过debug都看出来了。
思路和说明直接看注释
/**
* 希尔排序 学习的前提是学会插入排序
* 希尔排序是基于插入排序的改进。因为插入排序需要对比每一个元素，对于大量的数据排序，这个效率十分的低
* 希尔排序理解起来有些困难，它是把间隔h个数的所有数先排成有序的，然后再把h缩小到之前的1/3，一直到h=1 最终所有数都变成了有序数列
* 举例： 例如 0123456789 假设h=3 那么先把0 4 8 、 1 5 9 、 2 6 、 3 7 这几个小数组进行排序
* （当然我给的是一个有序的数组，你可以想象我给的数的位置上换任意其他的数），然后 h = 1 进行插入排序
*/
fun AlagorithmsActivity.shellSort(arr: Array<Int>){
val N = arr.size
var h = 1
//根据数组的长度来确定到底间隔多少个数来排序 即确定h的值
while (h < N /3) h = 3 * h +1
println("对应的h是$h")
while (h >= 1){
var i = h;
while (i < N){
var j = i;
while (j >= h && arr[j] < arr[j - h]){
exch(arr, j, j-h)
j -= h
}
i++
}
h /= 3
}
}
希尔排序看起来更复杂了，那么为什么会有这个算法呢？中级或者大量级别的数据，希尔排序基本是比较高效的算法了。数据量越大，他比插入排序效率越高。
四、归并排序
这个就更难理解了（对我来说这个是排序里面最难理解的）。没有递归思维的，建议先学习递归。
我也是第一次学习这个算法，如果有写的不对的地方，还请各位大佬扶正。
没有什么是一张动图解决不了的，如果有，那就看个小视频吧~
https://pic1.zhimg.com/v2-a29c0dd0186d1f8cef3c5ebdedf3e5a3_b.webp
fun sort(array: Array<Int>, lo: Int, hi: Int) {
if (hi <= lo) {
return
}
val mid = lo + (hi - lo) / 2
sort(array, lo, mid)
sort(array, mid + 1, hi)
merge(array, lo, mid, hi)
}
fun merge(array: Array<Int>, lo: Int, mid: Int, hi: Int) {
var i = lo
var j = mid + 1
var aux: Array<Int>? = Array(array.size){
array[it]
}
for (k in lo..hi) {
if (i > mid) {
array[k] = aux?.get(j++)!!
} else if (j > hi) {
array[k] = aux?.get(i++)!!
} else if (aux?.get(j)!! < aux[i]) {
array[k] = aux?.get(j++)!!
} else {
array[k] = aux?.get(i++)!!
}
}
}
归并排序最大的优点是排序时间是O（N logN）
最大的缺陷是需要的空间很多，和n成正比
五、快速排序
这个算法其实还好，那数组的第一个作为value，把整个数组与他对比，比他小的挪到左边，比他大的挪到右边，左后在交叉的位置把他放到中间。使用递归，对左右两个数组重复此操作，直到最后所有的数都是排序。
/**
* 快速排序
*/
fun quickSort(array: Array<Int>, lo: Int, hi: Int) {
if (lo >= hi) return
var partition = partition(array, lo, hi)
quickSort(array, lo, partition - 1)
quickSort(array, partition + 1, hi)
}
fun partition(array: Array<Int>, lo: Int, hi: Int): Int {
var i = lo
var j = hi + 1;
val v = array[i]
while (true) {
while (array[++i] < v) if (i == hi) break
while (v < array[--j]) if (j == lo) break
if (i >= j)break
exch(array, i, j)
}
exch(array, lo, j)
return j
}
fun exch(array: Array<Int>, i: Int, j : Int){
var temp: Int
if (array[i] > array[j]){
temp = array[i]
array[i] = array[j]
array[j] = temp
}
}
快速排序时间复杂度也是O(NlogN)
应该是排序里面比较好的算法了。主要是因为快速排序的内循环比其他排序的算法都要短。
比较常见的排序算法都在这了。当然这些都是最基本的，还有很多改进的算法。
