目录

 插入排序

直接插入排序

核心思想

代码示例

折半插入查找

核心思想

代码示例

 希尔排序

基本思想

增量选取

代码示例（王道书上的）

交换排序

冒泡排序

核心思想

代码示例

快速排序

核心思想

代码示例

选择排序

简单选择排序

核心思想

示例代码

堆排序

 核心思想

代码示例

归并排序和基数排序

归并排序

核心思想

代码示例 

基数排序

定义

总结（算法效率）

---

 插入排序

主要针对已排好序的子序列。

直接插入排序

核心思想

上面一组例子直观的表示了插入排序。核心思想也就是给定一组数据，插入一个排一次序。

若后一个元素比前一个元素小，那么哨兵更新，为小的那个。总体来说思想较为简单。 

代码示例

//插入排序，从小到大排序，升序
void InsertSort(ElemType A[],int n)
{
	int i,j;
	//24 66 94  2 15 74 28 51 22 18  2
	for(i=2;i<=n;i++)//第零个元素是哨兵，从第二个元素开始拿，往前面插入
	{
		if(A[i]1])
		{
			A[0]=A[i];//放到暂存位置，A[0]即是暂存，也是哨兵
			for(j=i-1;A[0]//移动元素，内层循环控制有序序列中的每一个元素和要插入的元素比较
				A[j+1]=A[j];
			A[j+1]=A[0];//把暂存元素插入到对应位置
		}
	}
}

时间复杂度为o（n2），空间复杂度o（1），稳定

适用：顺序存储和链式存储的线性表。

折半插入查找

核心思想

主要就是利用折半查找找插入的位置

例：定义一个升序的数组 a[6] = {1，35，55，66，78，99}。其中我要向数组插入47。

1，35，55，66，78，99
通过改良二分查找，可以得到 最终跳出循环后min = 2，那么47最终插入的位置就为下标 = 2的位置，原先插入位置的元素和后面的元素全部向后移动一位。

所以最终的结果{1，35，47，55，66，78，99}

代码示例

//折半查找 插入排序
void MidInsertSort(ElemType A[],int n)
{
	int i,j,low,high,mid;
	for(i=2;i<=n;i++)
	{
		A[0]=A[i];
		low=1;high=i-1;
		while(low<=high)//先通过二分查找找到待插入位置
		{
			mid=(low+high)/2;
			if(A[mid]>A[0])
				high=mid-1;
			else
				low=mid+1;
		}
		for(j=i-1;j>=high+1;--j)
			A[j+1]=A[j];
		A[high+1]=A[0];
	}
}

时间复杂度o（n2),空间复杂度o（nlog2n），稳定

适用于顺序存储

 希尔排序

基本思想

首先他的基本思想就是选取一个增量，根据增量进行分组排序，然后增量递减，直到为一，排序完成。

思想较为简单，具体示例请看下图

 这个第一轮选取的增量为5，第二次为3，第三次为1。排序就完成了。

若希尔排序还是不太理解的同学，可以看看这个博主写的

希尔排序_天地高歌的博客-CSDN博客_希尔排序

增量选取

这里肯定有同学有疑问：增量到底是怎么选取的呀？

下面给出一条大佬们得出的结论：

1.增量必须递减，且最后增量为1（标志排序完成）。

2.增量序列必须互质，不然最小增量不起作用。

于是有些大佬就发明了一些求增量的方法，Hibbard增量序列、Knuth增量序列、Sedgewick增量序列等等

我们书上用的是希尔增量。

希尔增量
最坏时间复杂度：O(n^2)
教材上都是以希尔增量为例子 => [N/2, (N/2)/2, …]

Hibbard增量
最坏时间复杂度：O(n^1.5)
增量序列：2^k-1 => [1, 3, 7, 15, …]

如果想了解更多关于增量的知识，请看

https://blog.csdn.net/Foliciatarier/article/details/53891144?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522165891299416782390510402%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=165891299416782390510402&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduend~default-2-53891144-null-null.142^v35^experiment_28w_v1,185^v2^tag_show&utm_term=Knuth%E5%A2%9E%E9%87%8F%E5%BA%8F%E5%88%97&spm=1018.2226.3001.4187https://blog.csdn.net/Foliciatarier/article/details/53891144?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522165891299416782390510402%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=165891299416782390510402&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduend~default-2-53891144-null-null.142^v35^experiment_28w_v1,185^v2^tag_show&utm_term=Knuth%E5%A2%9E%E9%87%8F%E5%BA%8F%E5%88%97&spm=1018.2226.3001.4187

代码示例（王道书上的）

void ShellSort(ElemType A[],int n)
{
	int dk,i,j;
	// 73 29 74 51 29 90 37 48 72 54 83
	for(dk=n/2;dk>=1;dk=dk/2)//步长变化
	{
		for(i=dk+1;i<=n;++i)//以dk为步长进行插入排序
		{
			if(A[i]
			{
				A[0]=A[i];
				for(j=i-dk;j>0&&A[0]
					A[j+dk]=A[j];
				A[j+dk]=A[0];
			}
		}
	}
}

空间复杂度o（1），最坏时间复杂度o（n2），不稳定
仅适用于线性表顺序存储

交换排序

通过比较关键字来交换位置排序

冒泡排序

核心思想

从前往后或从后往前，依次两两比较相邻元素，若不符合规则（顺序或逆序），则交换位置。

代码示例

void swap(ElemType &a,ElemType &b)
{
	ElemType tmp;
	tmp=a;
	a=b;
	b=tmp;
}
// 64 94 95 79 69 84 18 22 12 78
// 12 64 94 95 79 69 84 18 22 78
void BubbleSort(ElemType A[],int n)
{
	int i,j;
	bool flag;
	for(i=0;i-1;i++)//i最多访问到8
	{
		flag=false;
		for(j=n-1;j>i;j--)//把最小值就放在最前面
		{
			if(A[j-1]>A[j])
			{
				swap(A[j-1],A[j]);
				flag=true;
			}
		}
		if(false==flag)
			return;
	}
}

 空间复杂度：o（1），平均和最坏时间复杂度：o（n2），稳定

快速排序

核心思想

基于分治法，比如说我们要顺序的排序。我们去数组的一个分隔值，把比值小的都放值左边，反之则放右边，然后不断递归，最终分割的只剩一个元素，自然就得到有序序列了。

图解法请参考这个博主

快速排序法（详解）_李小白~的博客-CSDN博客_快速排序

代码示例

int Partition(int* arr, int left, int right)
{
	int k, i;
	for (k = i = left;i
	{
		if (arr[i] < arr[right])
		{
			swap(arr[i], arr[k]);
			k++;
		}
	}
	swap(arr[k], arr[right]);
	return k;
}
//递归实现
void QuickSort(ElemType A[],int low,int high)
{
	if(low
	{
		int pivotpos=Partition(A,low,high);//分割点左边的元素都比分割点要小，右边的比分割点大
		QuickSort(A,low,pivotpos-1);
		QuickSort(A,pivotpos+1,high);
	}
}

 最坏空间复杂度o（n），与递归调用的深度有关。最坏时间复杂度为o（n2），不稳定

快速排列算法是内部排序算法中平均性能最优的算法。

选择排序

每次选择后面n-i+1的最小元素。

简单选择排序

核心思想

与上面差不多，也就是每次选择n-i+1（i为i趟）后的最小元素与位置为i的元素交换。

示例代码

void swap(ElemType &a,ElemType &b)
{
	ElemType tmp;
	tmp=a;
	a=b;
	b=tmp;
}
void SelectSort(ElemType A[],int n)
{
	int i,j,min;//min记录最小的元素的下标
	for(i=0;i-1;i++)//最多可以为8
	{
		min=i;
		for(j=i+1;j//j最多可以为9
		{
			if(A[j]
				min=j;
		}
		if(min!=i)
		{
			swap(A[i],A[min]);
		}
	}
}

空间复杂度o（1），时间复杂度o（n2），不稳定

堆排序

分为大根堆和小根堆

大根堆是最大元素放在根结点，，且任一非根结点的值小于等于其双亲结点，小根堆则与其定义相反。下面是大根堆示例图

 核心思想

首先将元素建成初始堆，堆顶元素为最大值。输出堆顶元素后，通常将堆底元素送入堆顶，此时已不满足大根堆性质，所以我们需要将堆顶元素向下调整，反复重复，直到堆中仅剩一个元素。

代码示例

void swap(ElemType &a,ElemType &b)
{
	ElemType tmp;
	tmp=a;
	a=b;
	b=tmp;
}
//调整某个父亲节点
void AdjustDown(ElemType A[],int k,int len)
{
	int i;
	A[0]=A[k];
	for(i=2*k;i<=len;i*=2)
	{
		if(i1])//左子节点与右子节点比较大小
			i++;
		if(A[0]>=A[i])
			break;
		else{
			A[k]=A[i];
			k=i;
		}
	}
	A[k]=A[0];
}
//用数组去表示树   层次建树
void BuildMaxHeap(ElemType A[],int len)
{
	for(int i=len/2;i>0;i--)
	{
		AdjustDown(A,i,len);
	}
}
void HeapSort(ElemType A[],int len)
{
	int i;
	BuildMaxHeap(A,len);//建立大顶堆
	for(i=len;i>1;i--)
	{
		swap(A[i],A[1]);
		AdjustDown(A,1,i-1);
	}
}

空间复杂度：o（1），最坏和平均时间复杂度：nlog2n，不稳定

归并排序和基数排序

归并排序

核心思想

将两个或两个以上有序表组合成一个新的有序表

代码示例 

void Merge(ElemType A[],int low,int mid,int high)
{
	ElemType B[N];
	int i,j,k;
	for(k=low;k<=high;k++)//复制元素到B中
		B[k]=A[k];
	for(i=low,j=mid+1,k=i;i<=mid&&j<=high;k++)//合并两个有序数组
	{
		if(B[i]<=B[j])
			A[k]=B[i++];
		else
			A[k]=B[j++];
	}
	while(i<=mid)//如果有剩余元素，接着放入即可
		A[k++]=B[i++];
	while(j<=high)
		A[k++]=B[j++];
}
//归并排序不限制是两两归并，还是多个归并
// 1 3 5 7 9
// 2 4
// 1 2 3 4 5 7 9  主要的代码逻辑
void MergeSort(ElemType A[],int low,int high)//递归分割
{
	if(low
	{
		int mid=(low+high)/2;
		MergeSort(A,low,mid);
		MergeSort(A,mid+1,high);
		Merge(A,low,mid,high);
	}
}

二路归并排序空间复杂度o（n），时间复杂度o（nlog2n），稳定

基数排序

定义

 图解算法请看

排序算法之基数排序_小C哈哈哈的博客-CSDN博客_基数排序算法

空间复杂度o（r），r为辅助存储空间，辅助队列数量。时间复杂度o（d（n+r）），d为趟，r为辅助队列数量。稳定。

总结（算法效率）

以上均为内部排序算法。