排序算法

2016/09/23

排序很基础，但是不同的排序算法所使用的思想不一样，还是很值得借鉴学习的。为了给自己巩固一下，手码一遍所有简单排序的代码。

快速排序

给出一个数组：

选取一个基准点，然后把小于基准点的数据放在左边，大于基准点的数据放在右边。
在基准点左边和右边的数组里重复1。

1
def quickSort(arr: Array[Int], begin: Int, end: Int): Unit = {
2
  if (end > begin) {
3
    var (i, j) = (begin, end)
4
    val pivot = arr(i)
5

6
    while (i < j) {
7
      while (j > i && arr(j) > pivot) {
8
        j -= 1
9
      }
10

11
      if (j > i) {
12
        swap(arr, i, j)
13
      }
14

15
      while (i < j && arr(i) < pivot) {
16
        i += 1
17
      }
18

19
      if (i < j) {
20
        swap(arr, i, j)
21
      }
22
    }
23

24
    quickSort(arr, begin, i-1)
25
    quickSort(arr, i+1, end)
26
  }
27
}

插入排序：

1
def insertSort(arr: Array[Int]): Unit = {
2
  arr.indices.foreach(i => {
3
    val v = arr(i)
4
    (i to 1 by -1).foreach(j => {
5
      if (arr(j-1) > arr(j)) {
6
        val temp = arr(j)
7
        arr.update(j, arr(j-1))
8
        arr.update(j-1, temp)
9
      }
10
    })
11
  })
12
}

冒泡排序

遍历所有元素，不停地将元素做交换。 n * n，很傻的算法。

1
def bubbleSort(arr: Array[Int]): Unit = {
2
  arr.indices.foreach(i => {
3
    (0 until arr.length - 1).foreach(j => {
4
      if (arr(j) > arr(j+1)) {
5
        swap(arr, j, j+1)
6
      }
7
    })
8
  })
9
}

选择排序

太傻的排序算法，不写。。。

归并排序

归并两个有序数组的思想，有序数组 = 归并（有序数组(0 -> mid), 有序数组(mid+1 -> N)），形成递归。

1
def mergeSort(arr: Array[Int], begin: Int, end: Int): Array[Int] = {
2
  if (begin == end) Array(arr(begin))
3
  else {
4
    val mid = (begin + end) / 2
5
    merge(mergeSort(arr, begin, mid), mergeSort(arr, mid+1, end))
6
  }
7
}
8

9
def merge(arr1: Array[Int], arr2: Array[Int]): Array[Int] = {
10
  var (i, j) = (0, 0)
11
  val newArr = mutable.ArrayBuffer[Int]()
12
  while (i < arr1.length || j < arr2.length) {
13
    if (i >= arr1.length) {
14
      newArr.append(arr2(j))
15
      j +=1
16
    } else if (j >= arr2.length) {
17
      newArr.append(arr1(i))
18
      i += 1
19
    } else if (arr1(i) <= arr2(j)) {
20
      newArr.append(arr1(i))
21
      i += 1
22
    } else if (arr1(i) > arr2(j)) {
23
      newArr.append(arr2(j))
24
      j += 1
25
    }
26
  }
27
  newArr.toArray
28
}

堆排序

将数组构造成一个大顶堆，特性是父节点大于子节点的值。
将大顶堆的第一个值移到最后，剩下的数字重新构造大顶堆，并重复这一流程。

1
def heapsort(arr: Array[Int]): Unit = {
2
  // 构建大顶堆
3
  (0 to arr.length / 2).foreach(i => {
4
    adjustHeap(arr, i, arr.length)
5
  })
6

7
  // remove first
8
  (arr.length to 1 by -1).foreach(i => {
9
    swap(arr, 0, i-1)
10
    adjustHeap(arr, 0, i-1)
11
  })
12
}
13

14
def adjustHeap(arr: Array[Int], idx: Int, length: Int): Unit = {
15

16
  (0 to length / 2).foreach(i => {
17
    var maxIdx = i
18
    if (i * 2+1 < length && arr(i*2+1) > arr(i)) {
19
      maxIdx = i * 2+1
20
    }
21

22
    if (i * 2 + 2 < length && arr(i*2+2) > arr(maxIdx)) {
23
      maxIdx = i * 2 + 2
24
    }
25

26
    swap(arr, i, maxIdx)
27
  })
28
}

计数排序

空间换时间，利用有限的数集大小，来直接将元素放入对应的位置。

桶排序

通过一个partition函数将数据集放入不同的桶中，再针对桶中数据做排序。