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

一、排序算法的分类

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

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

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

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)