image frame

XiShng Blog

既往拼搏，守护一生所爱

快速排序算法

算法 / 排序算法

快速排序

算法思想：快速排序算法与其他算法相比，它的特点是数字比较和交换的次数较少，在许多情况下可以高速地进行排序。

  • 第一步：选择数列中的一个数字作为排序的基准，这个数字被称为pivot。pivot通常选择一个随机的数字，在这里我们默认选择最右边的数字作为pivot。我们把这个数字做个标记记为p。
  • 第二步：在最左边的数字上标记为左标记，最右边的数字标记为右标记。快速排序是一种使用这些标记递归的重复一系列操作的算法。
  • 第三步：我们将左边的标记像右移动，当左边的标记的数字超过了pivot的数字时，停止移动。之后将右标记向左移动，当右标记的数字小于pivot时停止移动。当左右侧的标记都停止时，交换这两个数字的位置。（左标记的作用是找到一个大于pivot的数字，右标记是找到小于pivot的数字，通过交换数字可以在数列的左侧收集小于pivot的数字，右侧收集大于pivot的数字）。交换之后重复第二步操作。（ 情况1:当左标记找到比pivot大的数字 停止移动，右标记开始移动并且碰到了左标记所在的位置。则将当前位置的数字和pivot位置进行交换。情况2:当左标记移动和右标记碰撞时并不会停止移动，当左标记达到数列最右边时停止移动，这意味着pivot数字在这个数列里是最大值）
  • 第四步：因为pivot已经找到了数列中的位置，则对pivot左侧和右侧的数列 分成两部分并递归的执行前三步的步骤。（当操作的数列只有一个数字 则认为已经完成了排序）

时间复杂度：最坏情况为O(n^2) 最好情况O(nlog(n)) 平均情况为O(nlogn)

快速排序示意图

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
37
38
39
40
41
42
43
44
45
package main

import "fmt"

/*
	快读排序
	快排的思想 就是定一个目标值 确定这个目标值的位置 之后在对目标值两侧的数组
	递归的进行上述操作
	时间复杂度是最快和平均O(nlogn)  最慢 O(n^2)
*/
func quickSort(array []int, start, end int) {
	if start < end {

		left := start
		right := end
		pivot := array[start]
		for left < right {
			for left < right && array[right] >= pivot {
				right--
			}
			if left < right {
				array[left] = array[right]
				left++
			}

			for left < right && array[left] <= pivot {
				left++
			}
			if left < right {
				array[right] = array[left]
				right--
			}
		}
		array[left] = pivot
		quickSort(array, start, left-1)
		quickSort(array, left+1, end)
	}
	fmt.Println(array, "返回排序之后的array数组")
}

func main() {
	arrayList := []int{5, 4, 7, 2, 8, 10, 8}
	quickSort(arrayList, 0, len(arrayList)-1)
}

选择排序算法

算法 / 排序算法

选择排序

算法思想：线性搜索数列并找到最小值。将最小值替换为数列中最左端的数字并进行排序。如果最小值已经在最左端则不进行操作。重复此操作直到数列排序完成。
简单来说就是每次找到数列的最小值并和最左端还没确定的值进行替换。也可以找最大值和最右端没确定的值替换。 如下图所示

时间复杂度：最坏时间复杂度：O(n^2)。

选择排序示意图

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
package main

import "fmt"

func main() {
    numbers := []int{6, 2, 7, 5, 8, 9}
    SelectSort(numbers)

    fmt.Println(numbers)
}

func SelectSort(values []int) {
    length := len(values)
    if length <= 1 {
        return
    }

    for i := 0; i < length; i++ {
        min := i // 初始的最小值位置从0开始，依次向右

        // 从i右侧的所有元素中找出当前最小值所在的下标
        for j := length - 1; j > i; j-- {
            if values[j] < values[min] {
                min = j
            }
        }
        //fmt.Printf("i:%d min:%d\\n", i, min)

        // 把每次找出来的最小值与之前的最小值做交换
        values[i], values[min] = values[min], values[i]

        //fmt.Println(values)
    }
}

二分查找算法

算法 / 查找算法 / 通用查找

二分查找

二分查找法，在一个有序的数列里，把中间元素v与查找元素target相比较：

  • 若相等则返回
  • 若大于target则在v的右端继续使用二分查找法
  • 若小于target则在v的左端继续使用二分查找法

示意图

示例代码如下：

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
package main

import "fmt"

//二分查找（前提必须在有序的数组里，查找target）
//如果找到target，返回相应的索引index
//如果没有找到target，返回-1
//时间复杂度O(logN)

func binarySearch(arr *[]int, target int, l int, r int) int {
	//在arr[l...r]中查找target
	for l <= r {
		//middleIndex := r+l/2 //注意：这里容易产生bug（r+l溢出int最大值）,改写成如下方式
		middleIndex := l + (r-l)/2
		if (*arr)[middleIndex] == target {
			return middleIndex
		}else if (*arr)[middleIndex] > target {
			//在arr[l...middleIndex - 1]中查找target
			r = middleIndex - 1
		}else {
			//在arr[middleIndex + 1...r]中查找target
			l = middleIndex + 1
		}
	}
	return -1
}

func main() {
	arr := []int{1,2,5,8,11,13}
	index := binarySearch(&arr, 11,0, len(arr)-1)
	fmt.Println(index)
}

请我喝杯咖啡吧~

支付宝
微信