【数据结构】八大排序

发布于：2024-12-18 ⋅ 阅读:(72) ⋅ 点赞:(0)

目录

一、直接插入排序

二、希尔排序

三、选择排序

四、堆排序

五、冒泡排序

六、快速排序

七、归并排序

八、计数排序

稳定性结论

稳定性：排序后相同元素之间的相对顺序是否保持不变。

一、直接插入排序

286b70424d874a008d81738fca84fdaa.gif

基本思想：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。 

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

空间复杂度：O(1)

稳定性：稳定

每次指向后一个元素，临时保存后一个元素temp，将大于该temp的元素后移，在第一个小于等于temp的后一个位置插入temp。

func InsertSort(arr []int) []int {
	for i := 0; i < len(arr)-1; i++ {
		temp := arr[i+1]
		end := i
		for end >= 0 {
			if arr[end] > temp {
				arr[end+1] = arr[end]
				end--
			} else {
				break
			}
			arr[end+1] = temp
		}
	}
	return arr
}

二、希尔排序

b2d83b0ecc1a459fa093dc8c2a1b0efc.gif

希尔排序（Shell Sort）是一种基于插入排序的改进算法，由D.L. Shell于1959年提出。它通过引入一个“增量”（gap）的概念来对插入排序进行优化，使得插入排序在处理大规模数据集时效率更高。

基本思想：

将待排序的记录序列分割成若干子序列，每个子序列的元素之间相隔一个特定的“增量”。这些子序列分别进行直接插入排序，随着增量逐渐减小，子序列的间隔也越来越小，直至增量为1，此时整个序列作为一个表来处理，完成排序。 

 

时间复杂度：O(n^1.3)

空间复杂度：O(1)

稳定性:不稳定

在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。 

func ShellSort(arr []int) []int {
	gap := len(arr)
	for gap > 1 {
		gap /= 2
		for i := 0; i < len(arr)-gap; i++ {
			temp := arr[i+gap]
			end := i
			for end >= 0 {
				if arr[end] > temp {
					arr[end+gap] = arr[end]
					end -= gap
				} else {
					break
				}
				arr[end+gap] = temp
			}
		}
	}
	return arr
}

三、选择排序

5f5052d4396d423ba422ee2d09ae4d81.gif

基本思想：每次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置。

假设指针i对应的元素最小，然后选出i之后数组中的最小元素下标，和i交换 

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

空间复杂度：O(1)

稳定性：不稳定

举例：序列5 8 5 2 9，我们知道第一遍选择第1个元素5会和2交换，那么原序列中两个5的相对前后顺序就被破坏了，所以选择排序是一个不稳定的排序算法。

func SelectSort(arr []int) []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//select
			}
		}
		arr[i], arr[minIndex] = arr[minIndex], arr[i]//swap
	}
	return arr
}

四、堆排序

8abb88ad895e4b6b95a8a4744a430e44.gif

堆是什么？

堆（heap）是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质：

  • 堆中某个结点的值总是不大于或不小于其父结点的值；

  • 堆总是一棵完全二叉树。

完成二叉树是什么？

在完全二叉树中，除了最后一层，其他各层的节点数都达到了最大个数，而最后一层的节点则都连续集中在最左边1。  

基本思想：

  1. 建立最大堆：将无序序列构建成一个最大堆，即每个父节点的值都大于或等于其子节点的值。
  2. 交换堆顶元素与末尾元素：将堆顶元素（最大值）与末尾元素交换，然后将最大值“沉”到堆的末尾。
  3. 重新调整堆：重新对堆进行调整，使其满足最大堆的性质。
  4. 重复上述过程：重复步骤2和3，直到堆的大小为1。

 C++  algorithm库大根堆实现升序排序：

std::vector<int> arr={1,2,3,41,43,44,6,75,634,5,234,4,21};
std::make_heap(arr.begin(),arr.end());
for(int i=arr.size()-1;i>0;i--)
{
     swap(arr[i],arr[0]);//最大的数交换到尾部
     auto last=arr.end()+i-arr.size();//缩小建队范围
     std::make_heap(arr.begin(),last);//再次保持堆
}

 C++  algorithm库小根堆实现降序排序：

std::vector<int> arr={1,2,3,41,43,44,6,75,634,5,234,4,21};
std::make_heap(arr.begin(),arr.end(),std::greater<int>());
for(int i=arr.size()-1;i>0;i--)
{
    swap(arr[i],arr[0]);
    auto last=arr.end()+i-arr.size();
    std::make_heap(arr.begin(),last,std::greater<int>());
}

C++STL库priority_queue实现大根堆排序：

std::vector<int> arr={1,2,3,41,43,44,6,75,634,5,234,4,21};
std::priority_queue<int> que(arr.begin(),arr.end());
for(int i=arr.size()-1;i>=0;i--){
    arr[i]=que.top();
    que.pop();
}

 C++STL库priority_queue实现小根堆排序：

std::vector<int> arr={1,2,3,41,43,44,6,75,634,5,234,4,21};
std::priority_queue<int,std::vector<int>,std::greater<int>> que(arr.begin(),arr.end());
for(int i=arr.size()-1;i>=0;i--){
    arr[i]=que.top();
    que.pop();
}

golang手动实现 

递归建堆：

实际是一个大元素上升的一个过程

func Heapify(arr []int, n, fatherIndex int) {
	bigIndex := fatherIndex
	//计算公式
	//左结点：i*2+1
	//右结点：i*2+2
	leftIndex := fatherIndex*2 + 1
	rightIndex := fatherIndex*2 + 2
	if leftIndex < n && arr[leftIndex] > arr[bigIndex] {
		bigIndex = leftIndex
	}
	if rightIndex < n && arr[rightIndex] > arr[bigIndex] {
		bigIndex = rightIndex
	}
	if bigIndex != fatherIndex {
		arr[fatherIndex], arr[bigIndex] = arr[bigIndex], arr[fatherIndex] //swap
		Heapify(arr, n, bigIndex)
	}
}

排序： 

func HeapSort(arr []int) []int {
	//建堆
	//最后一个父结点为最后一个元素的父亲，最后一个元素为len(arr)-1
	//父节点计算公式:(i-1)/2
	//最后一个父节点之前的索引均为父节点，向前遍历
	for i := ((len(arr) - 1) - 1) / 2; i >= 0; i-- {
		Heapify(arr, len(arr), i)
	}
	//排序
	for i := len(arr) - 1; i > 0; i-- {
		arr[i], arr[0] = arr[0], arr[i] //将最大的数交换到尾部
		Heapify(arr, i, 0)
	}
	return arr
}

时间复杂度：O(n*log(n))

空间复杂度：O（1）

稳定性：不稳定

五、冒泡排序

a7130cf1f16f430eb30d2153ad937777.gif

、

 冒泡排序（Bubble Sort）是一种简单的排序算法，它通过重复遍历待排序的数列，比较每对相邻元素，并在必要时交换它们的位置。这个过程会重复进行，直到没有再需要交换的元素为止，这意味着数列已经排序完成。

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

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

 空间复杂度：O(1)

 稳定性：稳定

六、快速排序

26ce05c499a44233bc9bd0e924759568.gif

快速排序（Quick Sort）是一种高效的排序算法，由英国计算机科学家托尼·霍尔（Tony Hoare）在1960年提出。它的基本思想是分治法（Divide and Conquer），通过一个称为“基准”（pivot）的元素将数组分为两个子数组，一个包含所有小于基准的元素，另一个包含所有大于基准的元素，然后递归地对这两个子数组进行快速排序。

基本思想：

  1. 选择基准：从数组中选择一个元素作为基准（pivot）。选择基准的方法可以有多种，常见的有随机选择、选择第一个元素、选择最后一个元素或选择中间元素。

  2. 分区操作（Partitioning）：重新排列数组，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面。在这个分区退出之后，该基准就处于数组的中间位置。

  3. 递归排序：递归地将小于基准值元素的子数组和大于基准值元素的子数组排序。

分区：

func partition(arr []int, begin, end int) int {
	pivot := arr[end] //随便选的数
	i := begin
	for j := begin; j < end; j++ {
		if arr[j] < pivot {
			arr[i], arr[j] = arr[j], arr[i] //swap
			i++
		}
	}
	arr[i], arr[end] = arr[end], arr[i]
	return i
}

递归排序：

func qsort(arr []int, begin, end int) {
	if begin < end {
		mid := partition(arr, begin, end)
		qsort(arr, begin, mid-1)
		qsort(arr, mid+1, end)
	}
}

快速排序入口：

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

时间复杂度：O(N*log(N))

空间复杂度：O(log(N))

稳定性：不稳定

对[3, 3, 3, 4]进行分区，选择最后一个元素4作为基准，那么4会和第一个3调换位置，导致3之间的顺序变化。

七、归并排序

2bb8becbd10a4cc391825b122ca75641.png

归并排序是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

 基本思想：

  1. 分解：将原始数组分成两个等大小（或几乎等大小）的子数组。
  2. 递归：递归地将每个子数组进行归并排序。
  3. 合并：将两个排序好的子数组合并成一个最终的排序数组。

递归分解直到单个元素（单个元素一定有序）：

func msort(arr []int, temp []int, left, right int) {
	if left < right {
		mid := (left + right) / 2
		msort(arr, temp, left, mid)
		msort(arr, temp, mid+1, right)
		merge(arr, temp, left, mid, right)
	}
}

合并左右两个有序的数组： 

func merge(arr []int, temp []int, left, mid, right int) {
	//双指针合并有序数组
	l_index := left
	r_index := mid + 1
	temp_index := left
	for l_index <= mid && r_index <= right {
		if arr[l_index] < arr[r_index] {
			temp[temp_index] = arr[l_index]
			temp_index++
			l_index++
		} else {
			temp[temp_index] = arr[r_index]
			temp_index++
			r_index++
		}
	}
	for l_index <= mid {
		temp[temp_index] = arr[l_index]
		temp_index++
		l_index++
	}
	for r_index <= right {
		temp[temp_index] = arr[r_index]
		temp_index++
		r_index++
	}
	//temp copy to arr
	for left <= right {
		arr[left] = temp[left]
		left++
	}
}

 入口函数：

func MergeSort(arr []int) []int {
	temp := make([]int, len(arr))
	msort(arr, temp, 0, len(arr)-1)
	return arr
}

时间复杂度：O(N*log(N))

空间复杂度：O(N)

稳定性：稳定

八、计数排序

db9015a37c7044cab2ef847ef01e2003.gif

计数排序是一个非基于比较的排序算法，该算法于1954年由 Harold H. Seward 提出。它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中k是整数的范围），快于任何比较排序算法。当然这是一种牺牲空间换取时间的做法，而且当O(k)＞O(n*log(n))的时候其效率反而不如基于比较的排序（基于比较的排序的时间复杂度在理论上的下限是O(n*log(n)), 如归并排序，堆排序）

基本思想：

  1. 计算范围：首先确定数组中最大和最小的元素，从而确定排序时需要的“桶”的数量。
  2. 计数：创建一个计数数组，长度为最大值加1。遍历待排序数组，对于数组中的每个元素，在计数数组中对应的位置加1。
  3. 累加：将计数数组中的每个元素转化为累加和，这样每个元素的位置就表示了该元素在排序后数组中的位置。
  4. 输出排序结果：根据累加后的计数数组，重新构建排序后的数组。
func CountSort(arr []int) []int {
	if len(arr) < 1 {
		return []int{}
	}
	max := arr[0]
	min := arr[0]
	for i := 1; i < len(arr); i++ {
		if arr[i] > max {
			max = arr[i]
		}
		if arr[i] < min {
			min = arr[i]
		}
	}
	count := make([]int, max+1)
	//计数
	for i := 0; i < len(arr); i++ {
		count[arr[i]]++
	}
	//统计累积值
	for i := min + 1; i < max+1; i++ {
		count[i] += count[i-1]
	}
	res := make([]int, len(arr))
	//将元素放到正确的位置
	for i := 0; i < len(arr); i++ {
		res[count[arr[i]]-1] = arr[i]
		count[arr[i]]--
	}
	return res
}

时间复杂度：O(N+K)//K为max-min+1

空间复杂度：O(K)

稳定性：不稳定

 通过这个元素的个数排序，已经失去相同元素的位置信息

稳定性结论

稳定的排序：直接插入排序，冒泡排序，归并排序

不稳定的排序：希尔排序、选择排序、堆排序、快速排序、计数排序

 

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布