七大经典排序算法图解

目录
  • 插入排序
    • ①直接插入排序
      • 基本思想
      • 动图演示
      • 代码实现
    • ②希尔排序
      • 基本思想
      • 图示
      • 代码实现
  • 选择排序
    • ③直接选择排序
      • 基本思想
      • 动图演示
      • 代码实现
    • ④堆排序
      • 基本思想
      • 建堆需要注意的问题
      • 图示
      • 代码实现
  • 交换排序
    • ⑤冒泡排序
      • 基本思想
      • 动图演示
      • 代码实现
    • ⑥快速排序
      • 基本思想
      • 基本框架
      • Partion函数分析
      • Partion函数的优化
      • 快速排序代码实现
  • 归并排序
    • ⑦归并排序
      • 基本思想
      • 动图演示
      • 代码实现
  • 排序算法复杂度及稳定性分析

插入排序

①直接插入排序

基本思想

每次从一个有序序列开始,将待排元素与有序序列中的元素从后往前逐个比较,

若有序序列中的元素大于待排元素,则将较大的元素往后覆盖;

否则,将待排元素插入其前面,并结束此轮比较。

动图演示

代码实现

void InsertSort(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		int end = i;
		int x = a[end + 1];
		while (end >= 0)
		{
			if (a[end] > x)
			{
				a[end + 1] = a[end];
				end--;
			}
			else
				break;
		}
		a[end + 1] = x;
	}
}

②希尔排序

基本思想

先选定一个整数作为 gap ,将待排序列以 gap 为间隔分成 gap 组,

先对每组进行直接插入排序,

然后再适当缩小 gap ,重复上述步骤。

当 gap = 1 时,此时序列已经进行了多次预排序,接近有序。

这时再对序列进行直接插入排序,就能达到优化的效果。

图示

代码实现

void ShellSort(int* a, int n)
{
	//多次预排序(gap > 1) + 直接插入( gap == 1)
	int gap = n;
	while (gap > 1)
	{
		//使gap最后一次一定能到1
		gap = gap / 3 + 1;
		//多组一起排
		for (int i = 0; i < n - gap; ++i)
		{
			int end = i;
			int x = a[end + gap];
			while (end >= 0)
			{
				if (a[end] > x)
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
					break;
			}
			a[end + gap] = x;
		}
	}
}

选择排序

③直接选择排序

基本思想

每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始(末尾)位置,直到全部待排序的数据元素排完 。

动图演示

以每次选出最小值为例

代码实现

void Swap(int* px, int* py)
{
	int tmp = *px;
	*px = *py;
	*py = tmp;
}

void SelectSort(int* a, int n)
{
	int begin = 0;
	while (begin < n - 1)
	{
		int mini = begin;
		for (int i = begin; i < n; i++)
		{
			if (a[i] < a[mini])
				mini = i;
		}
		Swap(&a[begin], &a[mini]);
		++begin;
	}
}

④堆排序

基本思想

小堆根上的元素是堆中最小的元素,大堆根上的元素是堆中最大的元素。

先将待排序列建成小(大)堆,

获取堆根上的元素,这样就达到了选出待排序列中最小(大)元素的目的,

然后再将其放至正确位置。

建堆需要注意的问题

若将待排序列建成小堆,则每次可将待排序列中最小的元素放至正确的位置,但每次排除堆根后,剩下元素组成的堆结构被打乱,需要对剩下待排序列重新建堆,反而增加的问题的复杂性。

故我们将其建成大堆,每次将堆根上的元素(待排序列中最大的元素)与待排序列中最后一个元素进行交换,将大堆根上的元素换至正确位置,然后再使用向下调整算法,将交换上来的元素调整至一个大堆中的合适位置。

图示

代码实现

void Swap(int* px, int* py)
{
	int tmp = *px;
	*px = *py;
	*py = tmp;
}

//建大堆的向下调整算法
void AdjustDown(int* a, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && a[child + 1] > a[child])
			++child;
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
			break;
	}
}

void HeapSort(int* a, int n)
{
    //先使用向下调整算法,从最后一个元素的父亲开始建堆
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(a, n, i);
	}
    //先交换,再调整
	for (int end = n - 1; end > 0; --end)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
	}
}

交换排序

⑤冒泡排序

基本思想

从待排序列的首元素开始,从前往后依次进行比较,

若大于则交换,将其继续与后面元素比较,直到被放至正确位置。

否则迭代至与其比较的元素,重复上面的步骤。

动图演示

代码实现

void Swap(int* px, int* py)
{
	int tmp = *px;
	*px = *py;
	*py = tmp;
}

void BubbleSort(int* a, int n)
{
	for (int j = 0; j < n; j++)
	{
		for (int i = 0; i < n - j - 1; i++)
		{
			if (a[i] > a[i + 1])
			{
				Swap(&a[i], &a[i + 1]);
			}
		}
	}
}

⑥快速排序

基本思想

任取待排序元素序列中的某元素作为基准值,按照该排序码将待排序集合分割成两子序列,左子序列中所有元素均小于基准值,右子序列中所有元素均大于基准值,然后最左右子序列重复该过程,直到所有元素都排列在相应位置上为止。

基本框架

void QuickSort(int* a, int left, int right)
{
	if (left >= right)
		return;

    //先将选定的基准值排好
	int keyi = Partion(a, left, right);

    //再通过递归排序其左右子序列
	QuickSort(a, left, keyi - 1);
	QuickSort(a, keyi + 1, right);
}

Partion函数分析

Partion函数在这里的作用是:

将选定的基准值排到正确位置,并将待排序列分成比基准值小的左子序列,比基准值大的右子序列。

将区间按照基准值划分为左右两半部分的常见方式有:

1.hoare版本
基本思想:

选择待排序列的最左值的下标为基准值所指下标,当区间左下标小于区间右下标时,先从右开始找比基准值小的值,找到后再从左开始找比基准值大的值,都找到后,将左右下标对应的值交换,然后从右开始重复上述步骤,直到左右下标相等。当左右下标相等时,将下标所指向的值与基准值互换。

动图演示:

代码实现:
//hoare版本
int Partion(int* a, int left, int right)
{
	int keyi = left;
	while (left < right)
	{
		//右边先走,找小
		while (left < right && a[right] >= a[keyi])
		{
			--right;
		}
		//左边走,找大
		while (left < right && a[left] <= a[keyi])
		{
			++left;
		}
		Swap(&a[left], &a[right]);
	}
	Swap(&a[keyi], &a[left]);
	return left;
}
2.挖坑法
基本思想:

选择待排序列的最左值为基准值,将其下标记为坑的下标。当区间左下标小于区间右下标时,先从右开始找比基准值小的值,找到后将其放在当前坑上,并将坑替换到所找位置。再从左开始找比基准值大的值,找到后同样将其放在当前坑上,然后从右开始重复上述步骤,直到左右下标相等。当左右下标相等时,把基准值放到当前坑所在位置。

动图演示:

代码实现:
//挖坑法
int Partion(int* a, int left, int right)
{
    int key = a[left];
	int pivot = left;
	while (left < right)
	{
		//右边先走,找小
		while (left < right && a[right] >= key)
		{
			--right;
		}
		//值覆盖,坑替换
		a[pivot] = a[right];
		pivot = right;
		//左边走,找大
		while (left < right && a[left] <= key)
		{
			++left;
		}
		//值覆盖,坑替换
		a[pivot] = a[left];
		pivot = left;
	}
	a[pivot] = key;
	return pivot;
}
3.前后指针法
基本思想:

选择最左值的下标为基准值下标,并设定指向前后位置的两个下标 cur , prev 。使 prev 指向基准值的位置,cur 指向基准值的前一个位置。当 cur <= right,也就是 cur 指向的位置小于等于右区间的位置时,从 cur 开始找比基准值小的值,并将其与 prev 所在位置的前一个交换。当 cur 跳出右区间时,将基准值与 prev 所指向的值交换。

动图演示:

代码实现: 
//前后指针法 ——更推荐
int Partion(int* a, int left, int right)
{
	int keyi = left;
	int cur = left + 1;
	int prev = left;
	while (cur <= right)
	{
		//cur找小,把小的换到左边
		if (a[cur] < a[keyi])
		{
            ++prev;
			Swap(&a[cur], &a[prev]);
		}
		++cur;
	}
	Swap(&a[prev], &a[keyi]);
	return prev;
}

小结:

hoare版本与挖坑法都需要注意,不管是从右开始找还是从左开始找,始终都要注意左下标要小于右下标,若没有此限定条件,当从任一方向开始找值时,一旦没有找到我们所预想的值,就会导致越界情况产生。

而前后指针法是从一个方向开始,遍历搜索一次待排序列,只需设定一次限定条件。

故这里更推荐使用前后指针法来实现快速排序。

Partion函数的优化

由于每次是以基准值为准,将待排序列分成左右两个子序列,若每次能保证选到的基准值的正确位置在待排序列的中间部分,则每次分序列时,都能大致将待排序列分成均衡的两部分,从而将排序次数减少。

这里使用到三数取中的方法:

再排序前,先将最左值、中间值与最右值进行比较,选出三个数中的中间值,并将其与最左值交换,这样每次以最左值为基准值时,都能选到一个大致在中间部分的数。

代码:
//三数取中
int GetMidIndex(int* a, int left, int right)
{
	int mid = (left + right) / 2;
	if (a[left] > a[mid])
	{
		if (a[mid] > a[right])
			return mid;
		else if (a[left] < a[right])
			return left;
		else
			return right;
	}
	else
	{
		if (a[mid] < a[right])
			return mid;
		else if (a[left] > a[right])
			return left;
		else
			return right;
	}
}

快速排序代码实现

//三数取中
int GetMidIndex(int* a, int left, int right)
{
	//int mid = (left + right) / 2;
	int mid = left + ((right - left) >> 1);
	if (a[left] > a[mid])
	{
		if (a[mid] > a[right])
			return mid;
		else if (a[left] < a[right])
			return left;
		else
			return right;
	}
	else
	{
		if (a[mid] < a[right])
			return mid;
		else if (a[left] > a[right])
			return left;
		else
			return right;
	}
}

void Swap(int* px, int* py)
{
	int tmp = *px;
	*px = *py;
	*py = tmp;
}

//前后指针法
int Partion(int* a, int left, int right)
{
	int midi = GetMidIndex(a, left, right);
	Swap(&a[midi], &a[left]);

	int keyi = left;
	int cur = left + 1;
	int prev = left;
	while (cur <= right)
	{
		//cur找小,把小的换到左边
		if (a[cur] < a[keyi] && ++prev != cur)
		{
			Swap(&a[cur], &a[prev]);
		}
		++cur;
	}
	Swap(&a[prev], &a[keyi]);
	return prev;
}

void QuickSort(int* a, int left, int right)
{
	if (left >= right)
		return;

	int keyi = Partion3(a, left, right);

	QuickSort(a, left, keyi - 1);
	QuickSort(a, keyi + 1, right);
}

归并排序

⑦归并排序

基本思想

归并排序是将待排序列先分解至单个子序列,再将已有序的子序列合并一个临时数组中,得到完全有序的序列后再拷贝回原数组。即先使左右子序列有序,再将其归并为一个完整的有序序列。

动图演示

代码实现

void _MergeSort(int* a, int left, int right, int* tmp)
{
	if (left >= right)
		return;
	int mid = left + ((right - left) >> 1);
	_MergeSort(a, left, mid, tmp);
	_MergeSort(a, mid + 1, right, tmp);

	//归并
	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;
	int i = left;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] <= a[begin2])
		{
			tmp[i++] = a[begin1++];
		}
		else
		{
			tmp[i++] = a[begin2++];
		}
	}
	while (begin1 <= end1)
	{
		tmp[i++] = a[begin1++];
	}
	while (begin2 <= end2)
	{
		tmp[i++] = a[begin2++];
	}

	//把排序后的元素拷贝回原来的数组
	for (int j = left; j <= right; ++j)
	{
		a[j] = tmp[j];
	}
}

void MergeSort(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}

	_MergeSort(a, 0, n - 1, tmp);

	free(tmp);
	tmp = NULL;
}

排序算法复杂度及稳定性分析

以上所述是小编给大家介绍的七大经典排序算法图解,希望对大家有所帮助。在此也非常感谢大家对我们网站的支持!

(0)

相关推荐

  • C语言实现九大排序算法的实例代码

    直接插入排序 将数组分为两个部分,一个是有序部分,一个是无序部分.从无序部分中依次取出元素插入到有序部分中.过程就是遍历有序部分,实现起来比较简单. #include <stdio.h> void insertion_sort(int arr[], int array_length) { for (int i = 0; i < array_length; ++i) { int data = arr[i]; int j = 0; while (arr[j] < arr[i]) { j

  • C语言 八大排序算法的过程图解及实现代码

    目录 前言 一.插入排序 时间复杂度 空间复杂度 代码实现(升序) 二.希尔排序 时间复杂度 空间复杂度 代码实现 三.选择排序 时间复杂度 空间复杂度 代码实现 四.堆排序 时间复杂度 空间复杂度 代码实现 五.冒泡排序 时间复杂度 空间复杂度 代码实现 六.快排排序 时间复杂度 空间复杂度 代码实现 七.归并排序 时间复杂度 空间复杂度 代码实现 八.计数排序 时间复杂度 空间复杂度 九.各种排序总结比较 前言 排序是数据结构中很重要的一章,先介绍几个基本概念. 排序稳定性:多个具有相同的关

  • 必须知道的C语言八大排序算法(收藏)

    概述 排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存. 我们这里说说八大排序就是内部排序. 当n较大,则应采用时间复杂度为O(nlog2n)的排序方法:快速排序.堆排序或归并排序序. 快速排序:是目前基于比较的内部排序中被认为是最好的方法,当待排序的关键字是随机分布时,快速排序的平均时间最短: 1.插入排序-直接插入排序(Straight Insertion Sort) 基本思想: 将一个记录插入到

  • c++中八大排序算法

    概述 排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存. 我们这里说说八大排序就是内部排序. 当n较大,则应采用时间复杂度为O(nlog2n)的排序方法:快速排序.堆排序或归并排序序. 快速排序:是目前基于比较的内部排序中被认为是最好的方法,当待排序的关键字是随机分布时,快速排序的平均时间最短:  1.插入排序-直接插入排序(Straight Insertion Sort) 基本思想: 将一个记录插入

  • 深入学习C语言中常见的八大排序

    目录 冒泡排序 1.算法描述 2.动图展示 3.图解展示 4.代码实现 5.冒泡排序的优化 6.复杂度分析 插入排序 1.算法描述 2.动图展示 3.图解展示 4.代码实现 5.复杂度分析 希尔排序 1.算法描述 2.动图展示 3.图解展示 4.代码实现 5.复杂度分析 堆排序 1.算法描述 2.动图展示 3.图解展示 4.堆的一些基本性质 5.堆的构造 6.代码实现 7.复杂度分析 选择排序 1.算法描述 2.动图展示 3.图解展示 4.代码实现 5.复杂度 快速排序 1.算法简介 2.动图展

  • 七大经典排序算法图解

    目录 插入排序 ①直接插入排序 基本思想 动图演示 代码实现 ②希尔排序 基本思想 图示 代码实现 选择排序 ③直接选择排序 基本思想 动图演示 代码实现 ④堆排序 基本思想 建堆需要注意的问题 图示 代码实现 交换排序 ⑤冒泡排序 基本思想 动图演示 代码实现 ⑥快速排序 基本思想 基本框架 Partion函数分析 Partion函数的优化 快速排序代码实现 归并排序 ⑦归并排序 基本思想 动图演示 代码实现 排序算法复杂度及稳定性分析 插入排序 ①直接插入排序 基本思想 每次从一个有序序列开

  • Java十大经典排序算法图解

    目录 0.算法概述 0.1 算法分类 0.2 算法复杂度 0.3 相关概念 1.冒泡排序(Bubble Sort) 1.1 算法描述 1.2 动图演示 1.3 代码实现 2.选择排序(Selection Sort) 2.1 算法描述 2.2 动图演示 2.3 代码实现 2.4 算法分析 3.插入排序(Insertion Sort) 3.1 算法描述 3.2 动图演示 3.3代码实现 3.4 算法分析 4.希尔排序(Shell Sort) 4.1 算法描述 4.2 动图演示 4.3 代码实现 4.

  • C#七大经典排序算法系列(上)

    今天是开篇,得要吹一下算法,算法就好比程序开发中的利剑,所到之处,刀起头落. 针对现实中的排序问题,算法有七把利剑可以助你马道成功. 首先排序分为四种: 交换排序: 包括冒泡排序,快速排序. 选择排序: 包括直接选择排序,堆排序. 插入排序: 包括直接插入排序,希尔排序. 合并排序: 合并排序. 那么今天我们讲的就是交换排序,我们都知道,C#类库提供的排序是快排,为了让今天玩的有意思点, 我们设计算法来跟类库提供的快排较量较量.争取KO对手. 冒泡排序: 首先我们自己来设计一下"冒泡排序&quo

  • C#七大经典排序算法系列(下)

    今天跟大家聊聊最后三种排序: 直接插入排序,希尔排序和归并排序. 直接插入排序: 这种排序其实蛮好理解的,很现实的例子就是俺们斗地主,当我们抓到一手乱牌时,我们就要按照大小梳理扑克,30秒后,扑克梳理完毕,4条3,5条s,哇塞...... 回忆一下,俺们当时是怎么梳理的. 最左一张牌是3,第二张牌是5,第三张牌又是3,赶紧插到第一张牌后面去,第四张牌又是3,大喜,赶紧插到第二张后面去,第五张牌又是3,狂喜,哈哈,一门炮就这样产生了. 怎么样,生活中处处都是算法,早已经融入我们的生活和血液. 下面

  • 几种经典排序算法的JS实现方法

    一.冒泡排序 function BubbleSort(array) { var length = array.length; for (var i = length - 1; i > 0; i--) { //用于缩小范围 for (var j = 0; j < i; j++) { //在范围内进行冒泡,在此范围内最大的一个将冒到最后面 if (array[j] > array[j+1]) { var temp = array[j]; array[j] = array[j+1]; arra

  • 经典排序算法之冒泡排序(Bubble sort)代码

    经典排序算法 - 冒泡排序Bubble sort 原理是临近的数字两两进行比较,按照从小到大或者从大到小的顺序进行交换, 这样一趟过去后,最大或最小的数字被交换到了最后一位, 然后再从头开始进行两两比较交换,直到倒数第二位时结束,其余类似看例子 例子为从小到大排序, 原始待排序数组| 6 | 2 | 4 | 1 | 5 | 9 | 第一趟排序(外循环) 第一次两两比较6 > 2交换(内循环) 交换前状态| 6 | 2 | 4 | 1 | 5 | 9 | 交换后状态| 2 | 6 | 4 | 1

  • python实现经典排序算法的示例代码

    以下排序算法最终结果都默认为升序排列,实现简单,没有考虑特殊情况,实现仅表达了算法的基本思想. 冒泡排序 内层循环中相邻的元素被依次比较,内层循环第一次结束后会将最大的元素移到序列最右边,第二次结束后会将次大的元素移到最大元素的左边,每次内层循环结束都会将一个元素排好序. def bubble_sort(arr): length = len(arr) for i in range(length): for j in range(length - i - 1): if arr[j] > arr[j

  • Java多种经典排序算法(含动态图)

    算法分析 一个排序算法的好坏,一般是通过下面几个关键信息来分析的,下面先介绍一下这几个关键信息,然后再将常见的排序算法的这些关键信息统计出来. 名词介绍 时间复杂度:指对数据操作的次数(或是简单的理解为某段代码的执行次数).举例:O(1):常数时间复杂度:O(log n):对数时间复杂度:O(n):线性时间复杂度. 空间复杂度:某段代码每次执行时需要开辟的内存大小. 内部排序:不依赖外部的空间,直接在数据内部进行排序: 外部排序:数据的排序,不能通过内部空间来完成,需要依赖外部空间. 稳定排序:

  • Python 数据结构之十大经典排序算法一文通关

    目录 1.冒泡排序 算法演示 算法步骤 算法实现 2.选择排序 算法演示 算法步骤 算法实现 3.简单插入排序 算法演示 算法步骤 算法实现 4.希尔排序 算法演示 算法步骤 算法实现 5.归并排序 算法演示 算法步骤 算法实现 6.快速排序 算法演示 算法步骤 算法实现 7.堆排序 算法演示 算法步骤 算法实现 8.计数排序 算法演示 算法步骤 算法实现 9.桶排序 算法演示 算法步骤 算法实现 10.基数排序 算法演示 算法步骤 算法实现 一文搞掂十大经典排序算法 今天整理一下十大经典排序算

  • Python 十大经典排序算法实现详解

    目录 关于时间复杂度 关于稳定性 名词解释 1.冒泡排序 (1)算法步骤 (2)动图演示 (3)Python代码 2.选择排序 (1)算法步骤 (2)动图演示 (3)Python代码 3.插入排序 (1)算法步骤 (2)动图演示 (3)Python代码 4.希尔排序 (1)算法步骤 (2)Python代码 5.归并排序 (1)算法步骤 (2)动图演示 (3)Python代码 6.快速排序 (1)算法步骤 (2)动图演示 (3)Python代码 7.堆排序 (1)算法步骤 (2)动图演示 (3)P

随机推荐