【数据结构】几种常见的排序算法

前端之家收集整理的这篇文章主要介绍了【数据结构】几种常见的排序算法前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

一、排序算法的分类

下图是我掌握的一些排序算法,我将他们做了分类,当然,排序算法远不止这些。


本篇博客主要记录插入,选择,以及交换排序的冒泡排序,因为快排和归并算法相对复杂,所以,下一篇博客再细细讲述。

二、各种算法的基本思想,分析及其代码实现

1.直接插入排序

a>算法思想:假设第一个数是有序的,那么把后面的数拿出来插入到这个有序数的合适位置,假设是升序(比第一个数小则向后移动第一个数,将数插入到第一个数的前面),插入后有序区间扩大为两个,依次向后,不断拿出新的数插入到有序区间,再扩大这个有序区间直至区间大小等于排序数组的大小。

b>时间复杂度:时间上,最好情况当序列已经是有序排列了,在这种情况下,需要进行的比较操作需(n-1)次即可,复杂度O(n)。最坏情况,序列与目标序列相反,那么此时需要进行的比较共有n(n-1)/2次,时间复杂度忽略系数,结果为O(n^2)。平均来说插入排序算法复杂度为O(n²)。

c>空间复杂度:由于插入排序没有进行任何开辟空间或者递归的操作,顾其空间复杂度为O(1).

d>适用场景:由于插入排序的时间复杂度太大,所以不适合大量数据的排序,如果数据量少,倒是没啥影响。

e>代码实现

#pragma once
#include<iostream>
using namespace std;

void InSertSort(int* a,size_t n)
{
	int index = 1;
	size_t pos = index - 1;  //有序区间的最后一个位置

	while (pos < n - 1)
	{	
		for (int i = pos; i >= 0; i--)
		{
			if (a[i]>a[index])
			{
				swap(a[i],a[index]);
				index--;
			}
		}
		pos++;
		index = pos + 1;
	}
}

void TestInsertSort()
{
	int a[] = { 9,5,4,2,3,6,8,7,1,0 };
	InSertSort(a,sizeof(a) / sizeof(a[0]));
	PrintArr(a,sizeof(a) / sizeof(a[0]));
}

2.希尔排序

a>算法思想:希尔排序可以认为是对直接插入排序的优化,我们知道,直接插入排序在基本有序时是非常快的,所以希尔排序就是在直接插入排序之前进行多趟预排序(直接插入排序每次只能将数据移动一个位置,希尔的优化就体现在一次可跳跃移动),使得排序数组接近有序,最后进行一趟直接插入排序。预排序的思想如下:


b>时间复杂度分析:希尔排序的时间复杂度介于O(n)至O(n^2)之间,相关资料显示其具体复杂度为O(n^1.3)次方,这里我没有深究。

c>空间复杂度:与直接插入排序一样,O(1)。

d>代码实现

#pragma once 
#include<iostream>
using namespace std;

void ShellSort(int*a,size_t size)
{
	size_t gap = size;  //增量
	
	while (gap>1)
	{
		gap = gap / 3 + 1;  //保证最后一次是直接插入排序
		int pos = 0;
		for (int index = pos + gap; index < size; index++)
		{
			int tmp = a[index];
			pos = index - gap;
			while (pos >= 0 && a[pos]>tmp)
			{
				a[pos + gap] = a[pos];
				pos -= gap;
			}
			a[pos + gap] = tmp;

		}
	}
}

void TestShellSort()
{
	int a[] = { 9,0 };
	ShellSort(a,sizeof(a) / sizeof(a[0]));
}
注意:希尔排序增量的设置不能为一个定值,要根据排序数组的大小进行调整,同时保证最后一次为1,进行直接插入排序。

3.选择排序

a>算法思想:选择排序可以一次选一个最大的数,放在数组的最后一位(假设升序),也可以一次选择两个(一个最大,一个最小)分别放在最后和最前,算法思想很简单。

b>时间复杂度分析:选择排序在最好和最坏的情况下都是O(n^2),因为,即使有序了,选择排序依然每次要进行固定的选择和比较。

c>空间复杂度分析:O(1)

d>代码实现(一次选两数版本)

#pragma once
#include<iostream>

using namespace std;

void SelectSort(int *a,size_t n)
{
	size_t max,min;

	size_t left = 0;
	size_t right = n - 1;

	while (left < right)
	{
		min = max = left;
		for (size_t j = left; j <= right; j++)
		{
			if (a[j] <= a[min])
				min = j;
			if (a[j]>=a[max])
				max = j;
		}
		swap(a[left],a[min]);
		if (left == max)
		{
			max = min;
		}
		swap(a[right],a[max]);
		left++;
		right--;
	}
}

void PrintArr(int* a,size_t n)
{
	for (size_t i = 0; i < n; i++)
	{
		cout << a[i] << " ";
	}
	cout << endl;
}

void TestSelectSort()
{
	int a[] = { 9,0 };
	SelectSort(a,sizeof(a) / sizeof(a[0]));
}

4.堆排序

a>算法思想:若升序,建大堆,每次选择堆顶元素即最大的数,和最后一位交换,再缩小堆的范围(避免刚排好的最后一个位置被调回去),对剩下的进行向下调整(此时只有根节点不对,左右子树都满足大堆)。反复进行直到堆的范围为0.则数据就有序了。

b>时间复杂度:建堆的时间复杂度近似为O(n*log n),每次选一个数后进行调整的复杂度也近似为O(n*log n),时间复杂度忽略系数,结果就近似为O(n*log n).
c>空间复杂度:O(1)

d>代码实现:

#pragma once
#include<iostream>

using namespace std;

void AdjustDown(int* a,int root,int size)
{
	int parent = root;
	int child = 2 * parent + 1;  //数组下标是从0开始的,故此处的child是左孩子的下标
	while (child < size)
	{
		if ((child + 1)<size && a[child + 1]>a[child])
			++child;
		if (a[child]>a[parent])
			swap(a[child],a[parent]);
		parent = child;
		child = 2 * parent + 1;
	}
}

void HeapSort(int*a,int size)
{
	for (int i = (size-2)/2; i >=0; i--)   //建堆
	{
		AdjustDown(a,i,size);
	}
	for (int j = 0; j < size; j++)
	{
		swap(a[0],a[size - 1 - j]);
		AdjustDown(a,size - j - 1);
	}
}

void TestHeapSort()
{
	int a[] = { 9,5 };
	HeapSort(a,sizeof(a) / sizeof(a[0]));
}
注意:堆排序虽然效率很高,但是只适用于随机序列,像链表这些就不行了。

5.冒泡排序

a>算法思想:从下表为0的数开始,和后面的数依次比较,大的向后移,一趟排序之后,最大的就移动到了最后,再从下标为0的开始将次大的冒到倒数第二位。

b>时间复杂度:第一趟排序需要经过(n-1)次比较,第二次(n-2),。。。等差数列,最后忽略系数还是O(n^2)。

c>空间复杂度:O(1)

d>代码实现:

#pragma once
#include<iostream>

using namespace std;

void BubbleSort(int* a,size_t size)
{
	bool flag = false;
	for (int i = size; i > 0; i--)
	{
		flag = false;
		for (size_t j = 1; j < i; j++)
		{
			if (a[j - 1]>a[j])
			{
				swap(a[j],a[j - 1]);
				flag = true;
			}
		}
		if (flag = false)
			break;
			
	}
}

void TestBubbleSort()
{
	int a[] = { 9,0 };
	BubbleSort(a,sizeof(a) / sizeof(a[0]));
}

冒泡排序的优化:若某趟排序没有经过一次交换数据,说明数组已经有序,则跳出循环。

原文链接:https://www.f2er.com/datastructure/382390.html

猜你在找的数据结构相关文章