几种常用的排序算法

排序算法可分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因为排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。

排序算法 平均时间复杂度 最好情况 最坏情况 空间复杂度 排序方式 稳定性
冒泡排序 O(n^2^) O(n) O(n^2^) O(1) In-place 稳定
选择排序 O(n^2^) O(n^2^) O(n^2^) O(1) In-place 不稳定
插入排序 O(n^2^) O(n) O(n^2^) O(1) In-place 稳定
希尔排序 O(n log n) O(n log^2^ n) O(n log^2^ n) O(1) In-place 不稳定
归并排序 O(n log n) O(n log n) O(n log n) O(n) Out-place 稳定
快速排序 O(n log n) O(n log n) O(n^2^) O(log n) In-place 不稳定
堆排序 O(n log n) O(n log n) O(n log n) O(1) In-place 不稳定
计数排序 O(n + k) O(n + k) O(n + k) O(k) Out-place 稳定

冒泡排序

  • 算法步骤

比较相邻的元素，如果第一个比第二个大，那么交换他们两个，对每一对相邻的元素做相同的操作，从开始第一对到结尾的最后一对，这一步做完后，最后一个元素会是最大的数， 针对所有元素重复衣裳步骤，除了最后一个，

  • 代码实现
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

func BubbleSort(arr []int) []int {
 length := len(arr)

 for i := 0; i < length; i++ {
  for j := 0; j < length-i-1; j++ {
   if arr[j] > arr[j+1] {
    arr[j], arr[j+1] = arr[j+1], arr[j]
   }
  }
 }

 return arr
}

选择排序

  • 算法步骤

首先在未排序序列中找到最小（大）的元素，存放到序列的起始位置。 再从剩余未排序的未排序元素中继续寻找最小（大）的元素，然后放到已排序序列的末尾。 重复第二步，直到所有元素均排序完毕。

  • 代码实现
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

func SelectSort(arr []int) []int {
    length := len(arr)

    var minIndex int
 // var temp int

    for i := 0; i < length-1; i++ {
      minIndex = i
      for j := i + 1; j < length; j++ {
      if arr[j] < arr[minIndex] {
        minIndex = j
      }
    }
      arr[i], arr[minIndex] = arr[minIndex], arr[i]

 }

 return arr
}

插入排序

  • 算法步骤

将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

  • 代码实现
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

func InsertionSort(arr []int) []int {
        for i := range arr {
                preIndex := i - 1
                current := arr[i]
                for preIndex >= 0 && arr[preIndex] > current {
                        arr[preIndex+1] = arr[preIndex]
                        preIndex -= 1
                }
                arr[preIndex+1] = current
        }
        return arr
}

希尔排序

  • 算法步骤

选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1； 按增量序列个数 k，对序列进行 k 趟排序； 每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度

  • 代码实现
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

func shellSort(arr []int) []int {
        length := len(arr)
        gap := 1
        for gap < length/3 {
                gap = gap*3 + 1
        }
        for gap > 0 {
                for i := gap; i < length; i++ {
                        temp := arr[i]
                        j := i - gap
                        for j >= 0 && arr[j] > temp {
                                arr[j+gap] = arr[j]
                                j -= gap
                        }
                        arr[j+gap] = temp
                }
                gap = gap / 3
        }
        return arr
}

归并排序

  • 算法步骤
  1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
  2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置；
  3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
  4. 重复步骤 3 直到某一指针达到序列尾；
  5. 将另一序列剩下的所有元素直接复制到合并序列尾
  • 代码实现
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

func MergeSort(arr []int) []int {
        length := len(arr)
        if length < 2 {
                return arr
        }
        middle := length / 2
        left := arr[0:middle]
        right := arr[middle:]
        return merge(mergeSort(left), mergeSort(right))
}

func merge(left []int, right []int) []int {
        var result []int
        for len(left) != 0 && len(right) != 0 {
                if left[0] <= right[0] {
                        result = append(result, left[0])
                        left = left[1:]
                } else {
                        result = append(result, right[0])
                        right = right[1:]
                }
        }

        for len(left) != 0 {
                result = append(result, left[0])
                left = left[1:]
        }

        for len(right) != 0 {
                result = append(result, right[0])
                right = right[1:]
        }

        return result
}

快速排序

  • 算法步骤

从数列中挑出一个元素，称为 “基准”（pivot）; 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作； 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；

  • 代码实现
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

func QuickSort(arr []int) []int {
        return _quickSort(arr, 0, len(arr)-1)
}

func _quickSort(arr []int, left, right int) []int {
        if left < right {
                partitionIndex := partition(arr, left, right)
                _quickSort(arr, left, partitionIndex-1)
                _quickSort(arr, partitionIndex+1, right)
        }
        return arr
}

func partition(arr []int, left, right int) int {
        pivot := left
        index := pivot + 1

        for i := index; i <= right; i++ {
                if arr[i] < arr[pivot] {
                        swap(arr, i, index)
                        index += 1
                }
        }
        swap(arr, pivot, index-1)
        return index - 1
}

func swap(arr []int, i, j int) {
        arr[i], arr[j] = arr[j], arr[i]
}

堆排序

  • 算法步骤
  1. 创建一个堆 H[0……n-1]；
  2. 把堆首（最大值）和堆尾互换；
  3. 把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；
  4. 重复步骤 2，直到堆的尺寸为 1。
  • 代码实现
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

func HeapSort(arr []int) []int {
        arrLen := len(arr)
        buildMaxHeap(arr, arrLen)
        for i := arrLen - 1; i >= 0; i-- {
                swap(arr, 0, i)
                arrLen -= 1
                heapify(arr, 0, arrLen)
        }
        return arr
}

func buildMaxHeap(arr []int, arrLen int) {
        for i := arrLen / 2; i >= 0; i-- {
                heapify(arr, i, arrLen)
        }
}

func heapify(arr []int, i, arrLen int) {
        left := 2*i + 1
        right := 2*i + 2
        largest := i
        if left < arrLen && arr[left] > arr[largest] {
                largest = left
        }
        if right < arrLen && arr[right] > arr[largest] {
                largest = right
        }
        if largest != i {
                swap(arr, i, largest)
                heapify(arr, largest, arrLen)
        }
}

func swap(arr []int, i, j int) {
        arr[i], arr[j] = arr[j], arr[i]
}

计数排序

  • 算法步骤

找出待排序的数组中最大和最小的元素 （2）统计数组中每个值为i的元素出现的次数，存入数组C的第i项 （3）对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加） （4）反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1

  • 代码实现
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

func CountingSort(arr []int, maxValue int) []int {
        bucketLen := maxValue + 1
        bucket := make([]int, bucketLen) // 初始为0的数组

        sortedIndex := 0
        length := len(arr)

        for i := 0; i < length; i++ {
                bucket[arr[i]] += 1
        }

        for j := 0; j < bucketLen; j++ {
                for bucket[j] > 0 {
                        arr[sortedIndex] = j
                        sortedIndex += 1
                        bucket[j] -= 1
                }
        }

        return arr
}
Licensed under CC BY-NC-SA 4.0
© 2019 - 2024 不积跬步无以至千里
皖ICP备20014602号
Built with Hugo
Theme Stack designed by Jimmy