@[学习笔记1——算法—排序（插入排序、希尔排序、堆排序、快排）]

本文主要是介绍@[学习笔记1——算法—排序（插入排序、希尔排序、堆排序、快排）]，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

#排序
排序基于是否比较被排数列大小，分为比较排序与比较排序，其中非比较排序有计数排序法，比较排序有常用的冒泡排序、选择排序、插入排序、希尔排序、堆排序、快排、归并排序。
##目录
（一）排序方法介绍
1.插入排序
2.希尔排序
3.堆排序
4.快排
（二）各种排序特点及适用总结
##各种排序方法介绍（假设升序）
#插入排序

插入排序思想：选择一个数x插入某个“ 有序”数列arr。从arr最后一个数向前逐个比较，如数列中最后一个数为end，end大于x则end向后移动一位，直到某个数小于x则放在这个数后面，或者x最小则放在最前面。
算法实现：
‘’‘’void InsertSort(int* a, int n)
{
//插入排序思想是从第一个数开始，选后面一个数，前面的数进行比较。
//如果前面的数//比这个数大，则将前面的数向后移动一位，直到第一个数移至第二位，
// 选的数放第一位，或者前数比选中数小，那么放在选中数后面一位；
//end从第一个数开始， 被选数x从end+1开始
int i = 0;
for (i = 0; i < n-1 ; i++)
{
//单次的
int end = i;
int x = a[end + 1]; //end+1被记录，所以不会被覆盖数据

	while (end >= 0)
	{
		if (a[end] > x)
		{
			a[end + 1] = a[end];
			end--;
		}//if
		else
		{
			break;
		}
	}
	a[end + 1] = x;
}

}’’’
#希尔排序
希尔排序是一种能够应对各种场景，如数列全为单值的数列、已经有序的数列等各种场景的数列。希尔排序基于插入排序思想来，如果插入数列基本有序，则while循环的次数将大大减少。基于将数列进行预先排序的思想,对插入排序进行优化。

‘’’
void ShellSort(int* a, int n)
{
//希尔算法主要是对插入算法有个预排序调整。
//通过一个间距变量gap选出不同分组，在分组内现排序，不同分组排序完成后数组顺
//序大致已经排列好，再通过gap等于1时退化为插入排序进行一次排列，虽然麻烦
//但是效率好高，基本时间复杂度为N^1.3。

int gap = n;//这个gap选择是关键，如果从 10以下开始选，则优化不明显
                 //gap越大，gap内的元素越小，gap划分的数组越多，循环的出口是gap=1；gap--是循环退出的路径
                 //当gap=1时，希尔排序退化为插入排序，但是因为数列已经基本排好，所以很快
	//先写单次预排的
	//再写各组一锅炖的
	//再写一个控制gap的
	while (gap > 1)
	{//while1
		gap =gap/3+1;
		
		int i = 0;
		for (i = 0; i < n - gap; i++)
		{
			//n-gap是关键因为最后一个数的下标应该是n-1那么最后一个end的
			//位置应该是n-gap-1,所以是小于n-gap
			int end = i;
			int x = a[end + gap];
				while (end >=0)
				{
					if (a[end] > x)
					{
						a[end + gap] = a[end];
						end -= gap;
					}//if
					else
					{
						break;
					}//else
				}//while
		a[end + gap] = x;
		}
		

	}

}
‘’’
#堆排序
堆排序是借助二叉树，堆结构来进行排序，排升序用大堆（大堆：及树的所有根节点大于子节点的树），排降序用小堆。要借助二叉数排序是将一个大堆的根节点和最后一个叶子节点交换，然后将除最后一个叶子节点以外的节点在进行向下调整（大堆），此时第二大的节点再次形成根节点。重复进行则完成升序排序。降序同样，只是用小堆就行。

‘’’
图片好像用的是向上调整，但是向下调整一般来说要快一点。代码用向下调整实现，差别在于向上调整第一次是从前面向后面调，第二次是后面从前调，而向下调整是第一遍后面向前调成大堆（因为二叉树无序时，向下调整从前向后没法调）。（很简单，自己随便画个二叉树就知道了）
/升序建大堆
//向下调整，如果是子节点大于父节点，则父节点向下，子节点向上
//通过递归的方式
void AdjustDwon(int* a, int n, int root)
{
int parent = root;
int child = root * 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)
{
//堆排序，先建大堆
int root = n ;
for (int i = (n - 2)/2; i >=0; i–)
{
AdjustDwon(a, n, i);
}
//将最大的根节点 a[0]和 a[end]交换，对0 至 end-1 排序
for (int i = n - 1; i > 0; i–)
{
Swap(&a[0], &a[i]);
AdjustDwon(a, i, 0);
}

}

'''

#快速排序
快速排序是用递归实现，总的来看像构建了一个二叉树，每次递归可确定一个数，所以直接先理解一遍排序的过程，在理解递归过程就很明确了。没找到和是的图，就不放图了吧，很接单，可以自己画一下。每次递归的目的是将关键值放在正确的位置，先找到一个关键值，一般用最左边的来，key=arr[0]，然后设定两个下标，如果最左边的数当关键值，则从最右边的小标开始移动，直到两个光标相遇或者错过。右边光标发现比关键值小的值就停止，左边光标开始向右，发现比key大的就停下来和右边光标的数交换。最后两光标相遇，一定是左右下标相遇的数比key小（左下标遇右下标，说明相遇下标前的数都比key小，右下标遇左下标说明下标后的数都比key大，这就是为什么选左让右下标先动）。key找到后接下来就进入递归，[0,key_i-1] key位置坐标的数组进行递归，[key+1,n-1]右边的进行递归，递归的出口为左右下标相遇了。
‘’’
先写单趟的：
int Partern(int* a, int left, int right)
{
int midd_i = GetMidd(a, left, right);//这是优化三数取中
Swap(&a[midd_i], &a[left]);//这是优化三数取中
int keyi = left;
while (left < right)
{
while (a[right] >= a[keyi] && left < right)
{
right–;
}
while (a[left] <= a[keyi]&&left<right)
{
left++;
}
Swap(&a[left], &a[right]);
}
Swap(&a[left], &a[keyi]);
return left;
}
void QuickSort(int* a, int left,int right)
{

if (left >= right) //这是递归出口
{
	return;
}
if (right - left +1< 10)//先不看这，这是扣划的
{
	ShellSort(a+left, right - left + 1);
}
else
{
int keyi = Partern(a, left, right);//单趟排好后
QuickSort(a, left, keyi-1);//进入递归，有点像二叉树左子树
QuickSort(a, keyi + 1,right );//这是右子树
return;
}

}
‘’’
快排有几个缺点：
1.当数列有序时，时间很慢，因为每次单趟右下标都要走完，
2.不断递归开销很大，数列越接近有序，越接近最坏情况的0（n^2）的时间复杂度，
优化：三数取中
第二，当数列原本很大，但是递归到只有10个数的时候，栈开销会很大，所以将小数列优化为插排
‘’’
int GetMidd(int* a, int left, int right)
{
int midd_i = left + ((right - left) >> 1);
midd_i = a[left] > a[right] ? a[right] > a[midd_i] ? right : a[left] > a[midd_i] ? midd_i : left : a[left] > \a[midd_i] ? left : a[right] > a[midd_i] ? midd_i : right;
return midd_i;

}

‘’’
#（二）各种排序特点及适用总结
先上图：

整体来看希尔、堆排、快排的平均情况时间复杂度都还不错，比冒泡，选择排序好，计数排序虽然没有写，但是计数排序由于将位置偏移量作为数值来用，所以只适用于整体范围较小，且数值为整数的排序。快排需要优化，不然特殊数列排序较慢。
整体来看，希尔排序适用范围最广，对1000万个数排序，还是希尔仍跟快排差不多。堆排序也不错。

这篇关于@[学习笔记1——算法—排序（插入排序、希尔排序、堆排序、快排）]的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！