当前位置： 首页 > article >正文

算法中常用的排序

article 2024/11/15 5:33:54

1.概念

排序是将一组数据,依指定的顺序进行排列的过程.

2.排序的分类

(1).内部排序

        指将需要处理的所有数据都加载到内部存储器中进行排序.包括:交换式排序法,选择式排序法和插入式排序法

(2).外部排序

        数据量过大,无法全部加载到内存中,需要借助外部存储进行排序.包括:合并排序法和直接合并排序法  

3.交换式排序法

交换式排序属于内部排序,是运用数据值比较后,依判断规则对数据位置进行交换,以达到排序的目的,交换式排序分两种:

(1).冒泡排序法(Bubble sort),时间复杂度为 O(n^2)

(2).快速排序法(Quick sort)时间复杂度为 O(nlogn)

3.1. 交换式排序法-冒泡排序法

基本思路:

        通过对待排序序列从后到前(从下标较大的元素开始),依次比较相邻元素的排序码,若发现逆序则交换,使排序码较小的元素逐渐从后部移向前部(从下标较大的单元移向下标较小的单元),就像水底下的气泡一样,逐渐向上冒.

        因为排序过程中,各元素不断接近自己的位置,如果一趟下来没有进行交换,就说明序列有序,因此要在排序过程中设置一个标志flag判断元素是否进行过交换,从而减少不必要的比较 

 

 案例:

        将五个无序的数:24, 69, 80, 57, 13 使用冒泡排序法将其排成一个从小到大的有序序列

package main

import (
    "fmt"
)

// 冒泡排序
func bubleSort (arr *[5]int)  {
    fmt.Println("排序前arr= ", (*arr)) //排序前arr=  [12 34 3 88 65]
    temp := 0 //临时变量
    //第一轮排序
    for i := 0; i < 4; i++ {
            if (*arr)[i] > (*arr)[i + 1] {
                temp = (*arr)[i]
                (*arr)[i] = (*arr)[i + 1]
                (*arr)[i + 1] = temp
            }
    }

    fmt.Println("第一轮排序后arr= ", (*arr))  //第一轮排序后arr=  [12 3 9 5 88]

    //第二轮排序
    for i := 0; i < 3; i++ {
        if (*arr)[i] > (*arr)[i + 1] {
            temp = (*arr)[i]
            (*arr)[i] = (*arr)[i + 1]
            (*arr)[i + 1] = temp
        }
    }

    fmt.Println("第二轮排序= ", (*arr))  //第二轮排序=  [3 9 5 12 88]
    // ...

    //升级成冒泡排序
    for j := 0; j < len(*arr) - 1; j++ {
        for i := 0; i < len(*arr) - 1 - j; i++ {
            if (*arr)[i] > (*arr)[i + 1] {
                temp = (*arr)[i]
                (*arr)[i] = (*arr)[i + 1]
                (*arr)[i + 1] = temp
            }
        }
    }

    fmt.Println("冒泡排序后= ", (*arr))  // 冒泡排序后=  [3 5 9 12 88]
}

func main() {
    //定义个数组
    arr := [5]int{12, 88, 3, 9, 5}
    //把数组传给一个函数
    bubleSort(&arr)
    fmt.Println("冒泡排序后= ", arr) //冒泡排序后=  [3 5 9 12 88]
}

3.2. 交换式排序法- 快速排序法

快速排序（Quick Sort）是一种使用分治思想的排序算法，是对冒泡排序的一种改进,它以一种分而治之的方式将一个数组分成两个子数组，然后递归地对这两个子数组进行排序。

快速排序的基本思想:选择一个基准值（pivot），将数组分成两个部分，使得左边的元素都小于基准值，右边的元素都大于基准值,然后对左右两个部分分别进行递归排序。

快速排序的时间复杂度为O(nlogn)，其中n是数组的长度。在最坏的情况下，快速排序的时间复杂度为O(n^2)，但平均情况下时间复杂度为O(nlogn)，并且具有原地排序的特性（只使用常数级别的额外空间）。

算法实现步骤:

  1. 定义QuickSort函数包括三个参数：left：数组最左边下标；right：数组最右边下标；arr：要操作的数组。
  2. 定义数组中间值pivot，以及代表数组最左边和最右边的l,r。
  3. 通过数组中间值将数组分为两个部分，通过循环将比pivot小的值放到数组的左边，比pivot大的值放到右边。
  4. 循环找到左边比pivot大的值，右边比pivot小的值，然后通过中间值将两者进行交换，通过arr[l]和arr[r]是否与pivot相等进行优化
  5. 然后再通过左递归进行将pivot左边的数进行排序，这里需要注意的是QuickSort函数中的right已经被替换为“4”中的r。
  6. 通过右递归进行将pivot左边的数进行排序，这里需要注意的是QuickSort函数中的left已经被替换为“4”中的l。
  7. 将for循环中的 l 替换为了a，将r替换为了b；通过for循环后的 l 和 r 仍然不变。下图是整个代码中的 l 和 r 的变化。

package main
 
import "fmt"
 
//快速排序
//1.left 表示数组最左边的下标
//2.right 表示数组最右边的下标
//arr 表示要排序的数组
 
func QuickSort(left, right int, arr *[6]int) {
	l := left
	r := right
	//pivot 表示中轴
	pivot := arr[(left+right)/2]
	temp := 0
 
	//for  循环的目标是将比pivot小的数放在左边，比pivot大的数放在右边
	for l < r {
		//先从 pivot 的左边找到大于等于pivot 的值
		for arr[l] < pivot {
			l++
		}
		//从 pivot 的右边找到小于等于pivot 的值
		for arr[r] > pivot {
			r--
		}
		//如果 左边的值大于右边的值，代表找到了左边大于右边的数
		if l >= r {
			break
		}
		temp = arr[l]
		arr[l] = arr[r]
		arr[r] = temp
		if arr[l] == pivot {
			r--
		}
		if arr[r] == pivot {
			l++
		}
	}
	if l == r {
		l++
		r--
	}
	//向左递归
	if left < r {
		QuickSort(left, r, arr)
	}
	//向右递归
	if right > l {
		QuickSort(l, right, arr)
	}
}
 
func main() {
	arr := [6]int{-9, 78, 0, 23, -567, 70}
	fmt.Println("原始数组：", arr)
	QuickSort(0, len(arr)-1, &arr)
	fmt.Println("排序后的数组：", arr)
}

 结果如下:

4. 插入排序

插入排序（Insertion sort）是一种简单直观且稳定的排序算法。插入排序的工作方式非常像人们排序一手扑克牌一样,时间复杂度为 O(n^2)。开始时，我们的左手为空并且桌子上的牌面朝下。然后，我们每次从桌子上拿走一张牌并将它插入左手中正确的位置。为了找到一张牌的正确位置，我们从右到左将它与已在手中的每张牌进行比较，如下图所示：

 需求：
排序前：{4,3,2,10,12,1,5,6}
排序后：{1,2,3,4,5,6,10,12}

排序原理：

  • 1.把所有的元素分为两组，已经排序的和未排序的；
  • 2.找到未排序的组中的第一个元素，向已经排序的组中进行插入；
  • 3.倒叙遍历已经排序的元素，依次和待插入的元素进行比较，直到找到一个元素小于等于待插入元素，那么就把待插入元素放到这个位置，其他的元素向后移动一位；

 

package main
 
import "fmt"
 
func insertionSort(arr []int) []int {
    for i := 1; i < len(arr); i++ {
        key := arr[i]
        j := i - 1
 
        // Move elements of arr[0..i-1], that are greater than key,
        // to one position ahead of their current position
        for j >= 0 && arr[j] > key {
            arr[j+1] = arr[j]
            j = j - 1
        }
        // Place key at it's correct position
        arr[j+1] = key
    }
    return arr
}
 
func main() {
    arr := []int{4,3,2,10,12,1,5,6}
    fmt.Println("Original array:", arr)
    sortedArray := insertionSort(arr)
    fmt.Println("Sorted array: ", sortedArray)
}

 插入排序的适用场景:

  • 1. 小规模数据: 由于插入排序在数据规模较小的情况下，其时间复杂度为 O( n^2 )，但常数因子较小，因此实际运行效率并不低，特别是数据量很小 (如少于10个元素) 时，其效率甚至可能超过更复杂的排序算法
  • 2. 基本有序的数据: 对于已经部分排序的数组，插入排序的效率很高，因为它只需要少量的元素移动。例如，在数组末尾插入一个元素，或者数组已经是基本有序的情况下，插入排序的性能会非常好
  • 3. 稳定排序需求:插入排序是一种稳定的排序算法，即相等元素的相对位置在排序前后不会改变。这在某些需要保持数据原有顺序的场合非常有用
  • 4. 内存限制:由于插入排序是原地排序，它不需要额外的存储空间(除了几个变量外)，这对于内存受限的环境非常有利

尽管插入排序在大数据集上表现不佳，但在上述场景下，它仍然是一种非常有用且简单的排序算法

5. 选择排序

选择排序是直观的排序，通过确定一个 Key 最大或最小值，再从带排序的的数中找出最大或最小的交换到对应位置。再选择次之,双重循环时间复杂度为 O(n^2)

 排序原理:

  • 1.在一个长度为 N 的无序数组中，第一次遍历 n-1 个数找到最小的和第一个数交换。
  • 2.第二次从下一个数开始遍历 n-2 个数，找到最小的数和第二个数交换。
  • 3.重复以上操作直到第 n-1 次遍历最小的数和第 n-1 个数交换，排序完成。

 代码如下:

package main
 
import "fmt"
 
func selectionSort(arr []int) {
    for i := 0; i < len(arr)-1; i++ {
        // 记录最小元素的索引
        minIndex := i
        // 找到未排序部分的最小元素
        for j := i + 1; j < len(arr); j++ {
            if arr[j] < arr[minIndex] {
                minIndex = j
            }
        }
        // 交换找到的最小元素与第i个位置的元素
        arr[i], arr[minIndex] = arr[minIndex], arr[i]
    }
}
 
func main() {
    arr := []int{64, 25, 12, 22, 11}
    selectionSort(arr)
    fmt.Println("Sorted array:", arr)
}

6.希尔排序

希尔排序是插入排序的一种,又称“缩小增量排序”,是插入排序算法的一种更高效的改进版本是非稳定排序算法,在处理大批量数据时，希尔排序的性能确实高于插入排序

 排序原理：
        1.选定一个增长量h，按照增长量h作为数据分组的依据，对数据进行分组；
        2.对分好组的每一组数据完成插入排序；
        3.减小增长量，最小减为1，重复第二步操作

增长量h的确定：增长量h的值每一固定的规则，这里采用以下规则：

int h=1
while(h<数组长度/2){
    h=2h+1；//3,7
}
//循环结束后我们就可以确定h的最大值；
h的减小规则为：
h=h/2

代码如下:

package main
 
import "fmt"
 
func shellSort(arr []int) {
    // 计算增量序列
    n := len(arr)
    gap := n / 2
    for gap > 0 {
        // 按增量进行插入排序
        for i := gap; i < n; i++ {
            temp := arr[i]
            j := i
            for j >= gap && arr[j-gap] > temp {
                arr[j] = arr[j-gap]
                j -= gap
            }
            arr[j] = temp
        }
        // 减少增量
        gap /= 2
    }
}
 
func main() {
    arr := []int{12, 34, 54, 2, 3}
    shellSort(arr)
    fmt.Println("Sorted array is:", arr)
}

 7.归并排序

7.1概念

归并排序（Merge Sort）是一种分而治之的排序算法。它将一个大列表分成两个小列表，分别对这两个小列表进行排序，然后将排序好的小列表合并成一个最终的排序列表。归并排序的关键在于合并（Merge）过程，它确保了在合并的过程中，两个已排序的序列被合并成一个新的、有序的序列

代码如下:

package main
 
import (
	"demo/pkg"
	"fmt"
)

// MergeSort 归并排序
func MergeSort(arr []int) []int {
	if len(arr) <= 1 {
		return arr
	}
 
	// 找到中点，分割数组
	mid := len(arr) / 2
	left := MergeSort(arr[:mid])
	right := MergeSort(arr[mid:])
 
	// 合并两个已排序的切片
	return merge(left, right)
}
 
// merge 函数用于合并两个已排序的切片
func merge(left, right []int) []int {
	var result []int
	i, j := 0, 0
 
	for i < len(left) && j < len(right) {
		if left[i] < right[j] {
			result = append(result, left[i])
			i++
		} else {
			result = append(result, right[j])
			j++
		}
	}
 
	// 如果左侧有剩余，则追加到结果切片
	result = append(result, left[i:]...)
	// 如果右侧有剩余，则追加到结果切片
	result = append(result, right[j:]...)
 
	return result
}

 
func main() {
	// 定义一个切片，这里我们模拟 10 个元素
	arr := []int{98081, 27887, 31847, 84059, 2081, 41318, 54425, 22540, 40456, 3300}
	fmt.Println("arr 的长度：", len(arr))
	fmt.Println("Original data:", arr) // 先打印原始数据
	newArr := pkg.MergeSort(arr)       // 调用归并排序
	fmt.Println("New data:  ", newArr) // 后打印排序后的数据
}

7.2归并排序主要操作

  • 1. 合并: 合并操作由 merge 函数实现，它接收两个已排序的切片 left 和 right，并返回一个新的、包含两个切片所有元素且已排序的切片。
    • 初始化：首先，创建一个空的切片 result 用于存储合并后的结果。同时，使用两个索引 i 和 j 分别指向 left 和 right 的起始位置
    • 比较与合并：然后，使用一个循环，比较 left[i] 和 right[j] 的大小。将较小的元素追加到 result 中，并移动相应的索引。这个过程一直持续到任一切片中的所有元素都被添加到 result 中
    • 追加剩余元素：如果 left 和 right 中还有剩余的元素（即某个切片的索引没有遍历完），则直接将剩余的元素追加到 result 的末尾。这是因为在循环结束时，剩余的元素一定是已排序的（它们来自原始的已排序切片）
  • 2. 分割（Divide）与递归排序（Conquer）:分割与递归排序操作由 mergeSort 函数实现
    • 基本情况：如果输入的切片 arr 的长度小于或等于 1，则不需要排序，直接返回该切片。因为单个元素或空切片都可以被认为是已排序的
    • 分割：找到切片的中点 mid，将切片分为两部分：arr[:mid] 和 arr[mid:]
    • 递归排序：对着两部分分别调用 mergeSort 函数进行递归排序。这会将问题分解成更小的子问题，直到子问题小到满足基本情况
    • 合并：最后，使用 merge 函数将这两个递归排序后的切片合并成一个有序的切片，并返回该切片

7.3总体思想

归并排序通过递归地将数组分解成越来越小的半子表，对半子表排序，然后再将排好序的半子表合并成有序的表来工作。这个过程需要额外的存储空间来存放合并后的数组，因此其空间复杂度为 O(n)。然而，归并排序的时间复杂度是稳定的 O(n log n)，并且由于其分治特性，它在实际应用中非常有效，尤其是在处理大数据集时

7.4归并排序的适用场景

  • 1. 大数据集: 对于非常大的数据集，归并排序通常比快速排序或插入排序更有效，因为归并排序的时间复杂度是 O(n log n)，并且它的性能相对稳定，不会因数据集的不同而大幅度变化
  • 2. 链表排序: 由于归并排序在合并过程中不需要额外的空间（除了递归栈），所以在链表排序时非常高效。链表数据结构的特性使得分割和合并操作相对简单
  • 3. 外部排序: 当数据集太大，无法全部加载到内存时，可以使用归并排序的外部版本。在这个版本中，数据被分割成多个块，每块单独排序后存储在磁盘上，然后通过归并操作将它们合并成一个有序的文件
  • 4. 稳定性需求:归并排序是稳定的排序算法，这意味着相等的元素在排序后仍然保持原来的顺序。这在需要保持元素原始顺序的某些应用中非常有用

尽管归并排序在很多场景下都很有用，但它也有缺点，主要是需要额外的空间 O(n) 来存储临时数组,这在内存受限的情况下可能是一个问题

8.排序的稳定性

数组arr中有若干元素，其中A元素和B元素相等，并且A元素在B元素前面，如果使用某种排序算法排序后，能够保证A元素依然在B元素的前面，可以说这个该算法是稳定的。 

 稳定性的意义:

如果一组数据只需要一次排序，则稳定性一般是没有意义的，如果一组数据需要多次排序，稳定性是有意义的。例如要排序的内容是一组商品对象，第一次排序按照价格由低到高排
序，第二次排序按照销量由高到低排序，如果第二次排序使用稳定性算法，就可以使得相同销量的对象依旧保持着价格高低的顺序展现，只有销量不同的对象才需要重新排序。这样既可以保持第一次排序的原有意义，而且可以减少系统开销。

第一次按照价格从低到高排序：
 

第二次按照销量进行从高到低排序：
 

常见排序算法的稳定性：

  • 冒泡排序：只有当arr[i]>arr[i+1]的时候，才会交换元素的位置，而相等的时候并不交换位置，所以冒泡排序是一种稳定排序算法。
  • 选择排序: 选择排序是给每个位置选择当前元素最小的,例如有数据{5(1)，8 ，5(2)， 2， 9 },第一遍选择到的最小元素为2，所以5(1)会和2进行交换位置，此时5(1)到了5(2)后面，破坏了稳定性，所以选择排序是一种不稳定的排序算法。
  • 插入排序：比较是从有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的，那么把要插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。
  • 希尔排序：希尔排序是按照不同步长对元素进行插入排序 ,虽然一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以希尔排序是不稳定的。
  • 归并排序：归并排序在归并的过程中，只有arr[i]<arr[i+1]的时候才会交换位置，如果两个元素相等则不会交换位置，所以它并不会破坏稳定性，归并排序是稳定的。
  • 快速排序：快速排序需要一个基准值，在基准值的右侧找一个比基准值小的元素，在基准值的左侧找一个比基准值大的元素，然后交换这两个元素，此时会破坏稳定性，所以快速排序是一种不稳定的算法。

http://www.kler.cn/a/283376.html

相关文章：

  • 设计模式之装饰器模式(SSO单点登录功能扩展，增加拦截用户访问方法范围场景)
  • 使用 Keras 训练一个卷积神经网络（CNN）（入门篇）
  • ubuntu20.04 解决Pytorch默认安装CPU版本的问题
  • Vue 项目打包后环境变量丢失问题（清除缓存），区分.env和.env.*文件
  • C/C++精品项目之图床共享云存储（3）：网络缓冲区类和main
  • 在 Service Worker 中caches.put() 和 caches.add()/caches.addAll() 方法他们之间的区别
  • 云计算实训37——Dockerfile的应用+私有仓库的创建与管理
  • 更改图片中的部分颜色及修改图片的背景色
  • 如何知道当前网卡连接的下位机的IP，通过工具实现
  • 代码随想录 | 贪心算法总结
  • 负载均衡OJ项目详细解剖
  • Error running tomcat: Can‘t find catalina.jar
  • 给自己复盘的随想录笔记-哈希表
  • Furion+SqlSugar+Swagger企业级后端工程师 - 学习路线总目录
  • 【IEEE独立出版，快检索 | 高录用】第五届IEEE信息科学与教育国际学术会议(ICISE-IE 2024，12月20-22)
  • 如何禁止电脑访问网站
  • 一维/二维高斯分布的负对数似然推导
  • 【日常记录-Linux】.tar.xz、.tar.bz2、tar.gz解压
  • 8、嵌套循环 - 循环中的循环 - 课件
  • MySQL表分区与分表：概念、规则及应用案例
  • MyPrint打印设计器（四）vue3 函数式调用组件
  • vue3 使用vue-masonry加载更多，重新渲染
  • Java设计模式之装饰器模式详细讲解和案例示范
  • 深度学习：图像数据分析的革命
  • HTML静态网页成品作业(HTML+CSS)——电影肖申克的救赎介绍设计制作(1个页面)
  • jmeter连接mysql数据库以及常规用法