从排序开始

原创

ge3m0r

发布于 2024-11-16 20:44:49

2100

文章被收录于专栏：数据结构与算法专栏数据结构与算法专栏

排序算法算是算法中最基本的一种算法,而且由于排序算法很多,很多算法思想之间容易靠混,因此第一篇就是排序算法,主要包含冒泡排序,插入排序,选择排序,还有稍微有点难度的归并排序,快速排序和桶排序.

桶排序

由于很多人对前边的比较熟悉,因此这边也是从桶排序开始,桶其实在很多业务场景也会遇到, 大数据领域 hdfs 有分桶表,同样桶排序一般也是用于数据量较大的排序(主要数据量大是一个相对概念,我们一般数据量大于内存叫做大量数据)

桶排序思想

桶排序大概是这样的, 假设我们知道需要排序的数据范围是 1-10000 ,那么我们可以使用 100 ,每个桶里边存放 100 个范围的数据, 例如第一个桶放 1-100,然后在每个桶内对数据进行排序,然后按照桶的范围取出数据就是排完序的数据.

show me the code

单纯手写一个桶排序可能有点困难,我们可以写一个他的简化版场景,就是每个桶存放 1 个数据,我们大概思路是这样的:

1、对于一个数据,我们先求出数组的最大值和最小值,从而知道我们需要多少个桶

2、统计每个桶数据的个数

3、按照桶排序的话,我们需要对每个桶进行排序,但是由于桶内只有一个数据,因此这里不需要排序

4、将桶的数据进行扩展,我们可以想想,每个桶内都统计了一定数量的数据,例如第一个桶为 3 ,我们需要讲这个数据扩展到 0-2 下标,然后第二个桶从 3 开始扩展,一直扩展到 n (数据长度)

代码如下:

func BucketCounting(arr []int) []int{
	 n := len(arr)
     if n <= 1 {
         return arr
     }
	 
	 // 求最大值和最小值
	 var max = arr[0]
	 var min = arr[0]
	 for i := 1; i < n; i++{
		 if arr[i] > max{
			 max = arr[i]
		 }
		 if arr[i] < min{
			 min = arr[i]
		 }
	 }
	 
	 // 计算桶的数量, 分配桶的数量
	 bucketNum := (max - min) + 1
	 bucket := make([]int, bucketNum)
	 
	 // 统计每个桶中元素个数
	 for i := 0; i < n; i++{
		 bucket[arr[i] - min] += 1
	 }
	 // 桶排序,这里桶范围是  1  因此不需要排序
	 // 计算扩展后每个桶应该在的位置
	 for i := 1; i < bucketNum - 1; i++{
		 bucket[i] = bucket[i] + bucket[i - 1]
	 }
	 
	 // 数据排序后数组
	 result := make([]int, n)
	 for i := 0; i < n; i++{
		 result[bucket[arr[i] - min]] = arr[i]
		 bucket[arr[i] - min ] -= 1
	 }
	 return result
}

快速排序

因为有一段时间总是讲快排和归并排序分不清楚,因此先讲快速排序.

快速排序的思想

快速排序可以思想很简单,就是在一堆排序的数据中选择一个数据,然后大于他的分在他的右边,小于他的分在他的左边,然后对两边的数据使用同样的方法进行排序

show me the code

我们的思路大概很简单

1、对需要排序的数据按照参照分区

2、左边数组递归

3、右边数组递归

func QuickSort(arr []int, left int, right int)  {
	// 讲最右边的值作为基准值
	pivot := arr[right]
	if left >= right{
		return 
	}
	i := left
	for j := left; j <= right; j++{
		if arr[j] < pivot{
			arr[i], arr[j] = arr[j], arr[i]
			i = i + 1
		}
	}
	arr[i], arr[right] = arr[right], arr[i]
	QuickSort(arr, left, i -1)
	QuickSort(arr, i + 1, right)

归并排序

归并排序其实主要是分治和递归处理,讲一系列数据不断二分,直到最后少数几个数据后,然后排序,最后对排好序的数据合并称一个有序数组.

show me the code

对于归并排序首先就是分治,然后合并

1、讲数据分成两个,递归分治

2、讲分成的两个数组合并

func MergeSort(arr []int, left int, right int){
	if right <= left{
		return
	}
	
	mid := (left + right) / 2
	// 分治
	MergeSort(arr, left, mid)
	MergeSort(arr, mid + 1, right)
	
	// 合并
	Merge(arr, left, mid, right)
}
func Merge(arr []int, left int, mid int, right int){
	i := left
	j := mid + 1
	k := 0
	tmp := make([]int , right - left + 1)
	// 左右数组都有值的时候,合并
	for i < mid && j <= right{
		if arr[i] <= arr[j]{
			tmp[k] = arr[i]
			k++
			i++
		}else{
			tmp[k] = arr[j]
			k++
			j++
		}
	}
	
	// 判断左右那个数组有值
	if j <= right{
		for j <= right{
			tmp[k] = arr[j]
			k++
			j++
		}
	}
	if i <= mid{
		for i <= mid{
			tmp[k] =arr[i]
			k++
			i++
		}
	}
	for i := left; i <= right; i++{
		arr[i] = tmp[i - left]
	}
}

冒泡排序

冒泡排序非常简单,就是每次将最大的值或者最小的值移动到首尾或者末尾.

怎么达成这个,就每次交换相邻的两个数组,试想一下,最大值无论在哪里,他都会被交换,最终肯定交换到队首或者队尾

show me the code

func BubbleSort(arr []int){
	for i := 0; i < len(arr); i++{
		flag := false
		for j := 0; j < len(arr) - i - 1; j++{
			if arr[j] > arr[j + 1]{
				arr[j], arr[j + 1] = arr[j+1], arr[j]
			}
			flag = true
		}
		if !flag{
			break
		}
	}
}

上边是最有解的冒泡排序,加上一个标志位,表示在一个循环中如果没有需要交换的元素,那么表示这个数据已经是有序的了.

插入排序

插入排序理解起来也很简单,就是一个数据如果插入一个有序数据我要怎么办.

show me the code

func InsertSort(arr []int){
	for i := 1; i < len(arr); i++{
		value := arr[i]
		j := i - 1
		for j >= 0 && arr[j] > value{
			arr[j + 1] = arr[j]
			j--
		}
		arr[j + 1] = value
	}
}

选择排序

选择排序好理解一点,每次从没有排序的数据总选出一个最小值,然后放到队首

show me the code

func SelectSort(arr []int){
	if len(arr) <= 1 {
		return 
	}
	for i := 0; i < len(arr); i++{
		minPos := i
		for j := i + 1; j < len(arr); j++{
			if arr[j] < arr[minPos]{
				minPos = j
			}
		}
		arr[i], arr[minPos] = arr[minPos], arr[i]
	}
}