none

0%

7大经典排序算法

发表于 更新于

冒泡

把较小的元素往前调或者把较大的元素往后调

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func BubbleSort(arr []int) {
   size := len(arr)
   for i := 0; i < size; i++ {
      changed:= false
      for j := 1; j < size; j++ {
         if arr[j-1] > arr[j] {
            arr[j-1], arr[j] = arr[j], arr[j-1]
            changed = true
         }
      }
      if !changed {
         break
      }
   }
}

选择

第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾

1
2
3
4
5
6
7
8
9
10
11
12
func SelectSort(arr []int) {
   size := len(arr)
   for i := 0; i < size; i++ {
      minIndex := i
      for j := i + 1; j < size; j++ {
         if arr[minIndex] > arr[j] {
            minIndex = j
         }
      }
      arr[minIndex], arr[i] = arr[i], arr[minIndex]
   }
}

快速

通过一趟排序算法把所需要排序的序列的元素分割成两大块，其中，一部分的元素都要小于或等于另外一部分的序列元素，然后仍根据该种方法对划分后的这两块序列的元素分别再次实行快速排序算法，排序实现的整个过程可以是递归的来进行调用

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
func QuickSorSort(arr []int, low, high int) {
   if low > high {
      return
   }
   l,h := low, high
   p := l + ((h - l) >> 1)
   key := arr[p]
   for l < h {
      for l < h && arr[h] > key {
         h--
      }
      if l < h {
         arr[l] = arr[h]
         l++
      }

      for l < h && arr[l] < key {
         l++
      }
      if l < h {
         arr[h] = arr[l]
         h--
      }
   }
   arr[l] = key
   QuickSorSort(arr, low, l -1)
   QuickSorSort(arr, h + 1, high)
}

堆排

堆的数据结构中，堆中的最大值总是位于根节点（在优先队列中使用堆的话堆中的最小值位于根节点）。堆中定义以下几种操作： 最大堆调整（Max Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点 创建最大堆（Build Max Heap）：将堆中的所有数据重新排序 堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算

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

func HeapSort(arr []int) {
	var heapify func(arr []int, index , size int)
	heapify = func(arr []int, index ,size int) {
		left, right:= index*2 + 1,index*2 + 2
		max := index
		if left < size && arr[left] > arr[index] {
			max = left
		}
		if right < size && arr[right] > arr[max] {
			max = right
		}
		// 找到左右子树中最大的一个进行交换
		if max != index {
			arr[index], arr[max] = arr[max], arr[index]
			heapify(arr, max, size)
		}
	}

	var buildHeap = func(arr []int) {
		size := len(arr)
		for i :=  size / 2; i >= 0; i-- {
			heapify(arr, i, size)
		}
	}
	size := len(arr)
	buildHeap(arr)
	for i := size - 1; i >0; i-- {
		arr[0], arr[i] = arr[i],arr[0]
		size--
		heapify(arr, 0, size)
	}
}

希尔

该方法实质上是一种分组插入方法

先取一个小于 n 的整数 d1 作为第一个增量，把文件的全部记录分组。所有距离为 d1 的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量 d2 = d1 / 2

1
2
3
4
5
6
7
8
9
10
11
12
13
func ShellSort(arr []int) {
   size := len(arr)
   step := size / 2
   for ; step > 0; step /= 2 {
      for i := step; i < size; i++ {
         for j := 0; j+ step < size ; j+=step {
            if arr[j] > arr[j+step] {
               arr[j], arr[j+step] = arr[j+step], arr[j]
            }
         }
      }
   }
}

归并

将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。

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 MergeSort(arr []int) []int {
   size := len(arr)
   mid := size / 2
   if size < 2 {
      return arr
   }
   var merge = func(left, right []int) []int {
      var ret = make([]int,0)
      sizeL := len(left)
      sizeR := len(right)
      i, j := 0, 0
      for i < sizeL && j < sizeR {
         if left[i] < right[j] {
            ret = append(ret, left[i])
            i++
         } else {
            ret = append(ret, right[j])
            j++
         }
      }
      if i < sizeL {
         ret = append(ret, left[i:]...)
      }
      if j < sizeR {
         ret = append(ret, right[j:]...)
      }
      return ret
   }
   return merge(MergeSort(arr[:mid]), MergeSort(arr[mid:]))
}

插入

源于扑克牌

插入排序是指在待排序的元素中，假设前面 n-1(其中 n>=2)个数已经是排好顺序的，现将第 n 个数插到前面已经排好的序列中，然后找到合适自己的位置

1
2
3
4
5
6
7
8
9
10
11
12
func InsertSort(arr []int) {
   size := len(arr)
   for i := 0; i < size - 1; i++ {
      for j := i + 1; j > 0; j-- {
         if arr[j] < arr[j - 1] {
            arr[j], arr[j-1] = arr[j-1],arr[j]
         } else {
            break
         }
      }
   }
}