数据结构之排序算法

原文链接

在实际应用中常常用到排序算法，这篇文来总结一下常用的。上面是原文链接，文章里介绍很详细，还有动图示例，形象易懂。

重复的内容不再赘述，看原文就好，这里写一写我常用到的。

冒泡排序

这个记的最深刻，也是最常用的，因为一遇到排序问题，首先想到的就是冒泡。原理很简单，一句话总结就是，每次将未排序部分的极值移动到尾端。如果是升序排列，那么每次寻找的就是最大值，反之则是最小值。这个过程，就像是在冒泡。

val arr = intArrayOf(3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48)

fun bubble() {
    for (i in arr.indices) {
    	// 每趟循环到倒数第二个即可，因为比较的时候是j和j+1
        for (j in 0 until (arr.size - i - 1)) {
            if (arr[j] > arr[j + 1]) {
                val temp = arr[j]
                arr[j] = arr[j + 1]
                arr[j + 1] = temp
            }
        }
    }
    println(arr.localString())
}

// 输出
[2,3,4,5,15,19,26,27,36,38,44,46,47,48,50]

选择排序

这个和冒泡排序很像，第一次从所有元素中找到极值放到第一位，第二次从剩下的元素中找到极值放到第二位，以此类推。

// 选择排序
fun select () {
    var temp = 0 // 临时变量
    var pointer = 0 // 用来标记当前在找的位置
    while (pointer < arr.size - 1) {
        temp = arr[pointer]
        // 通过for循环，找到本趟的极值
        for (i in pointer until arr.size) {
            if (arr[i] < temp) {
                temp = temp xor arr[i]
                arr[i] = temp xor arr[i]
                temp = temp xor arr[i]
            }
        }
        // 本趟结束，把极值赋值给当前位置
        arr[pointer++] = temp
    }
}

快速排序

• 这是个有趣的排序算法，使用递归
• 选择一个基准值，一般选左端，或者右端
• 目标是把比基准值小的放到左边，大的放到右边
• 如果选择左端则从右端指针开始判断，反之从左端指针开始
• 这里假设选择左端为基准值，所以从右端指针开始扫描
• 用临时变量存储基准值，此时可认为左指针指向的位置是空
• 如果右指针比基准值小，则将右指针的值填充到左指针，此时认为右指针位置是空
• 此时用左指针扫描
• 遇到比基准值大的时候，将左指针的值填充到右指针，此时认为左指针位置为空
• 此时用右指针扫描
• 直到两个指针相遇，将临时变量的基准值填充到任一指针
• 然后将基准值左右两部分，分别递归

  fun quick(low: Int,high: Int, array: IntArray) {
      if (low >= high) return
      var left = low
      var right = high
      val temp = array[left]
      var reverse = true
      while (left < right) {
          if (reverse) {
              // 从右指针扫描
              // 当值比基准值小时，右指针的值填充到左指针，此时认为右指针为空
              if (array[right] < temp) {
                  array[left] = array[right]
                  reverse = !reverse // 掉头
              } else {
                  right-- // 右指针左移动
              }
          } else {
              // 从左指针扫描
              // 当值比基准值大时，左指针填充到右指针，此时认为左指针为空
              if (array[left] > temp) {
                  array[right] = array[left]
                  reverse = !reverse // 调用
              } else {
                  left++ // 左指针右移动
              }
          }
      }
      // 一趟结束后，指针相遇，把基准值放到指针所在位置
      // 此时左侧都比基准值小，右侧都比基准值大
      array[left] = temp
      // 分别递归左侧和右侧
      quick(low, left - 1, array)
      quick(left + 1, high, array)
  }

插入排序

• 将序列分为两部分，左侧是已经排好顺序的，右侧是未排的
• 每次从未排序列中取一个数字，将其插入到已排好部分
• 循环至排序完成

  fun insert(array: IntArray) {
      var border = 0 // 左侧已排序部分的边界
      while (border < array.size - 1) {
          // 每次取右侧未排序部分的第一个数字，将其插入到左侧的目标位置
          for (i in border downTo 0) {
              if (array[i + 1] < array[i]) {
                  // 异或操作交换值，不用额外的临时变量
                  array[i] = array[i] xor array[i + 1]
                  array[i + 1] = array[i] xor array[i + 1]
                  array[i] = array[i] xor array[i + 1]
              } else {
                  break
              }
          }
          border++
      }
  }

https://github.com/oynix/SortAlgorithmSample