六大常见排序算法（插入、堆排、希尔、选择、冒泡、快速）_六大排序

多多重复，百炼成钢！！！

排序的稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

一、直接插入排序

时间复杂度（最坏情况）：O(N^2)

空间复杂度：O（1）

稳定性：好

// 最坏时间复杂度O(N^2)-逆序
void InsertSort(int* a, int n)
{
	// 在[0,end]之间 插入 end+1，保持 [0, end+1]有序
	for (int i = 0; i < n - 1; ++i)
	{
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (a[end] > tmp)
			{
				a[end + 1] = a[end];
				--end;
			}
			else
			{
				break;
			}
		}
 
		a[end + 1] = tmp;
	}
}

二、堆排序

时间复杂度：O(N*logN)

空间复杂度：O（N)

稳定性：不好

 

 要求升序-建大堆
 要求降序-建小堆

步骤：
 1.先找到最后一个节点，然后找到他的父亲a，在a在的堆（无序），通过向下调整把该堆调整为有序（大堆或小堆）
 2. 通过 i-- 找到父亲a的前一个节点b（也是另外一个堆的父亲-b），然后在父亲b所在的堆（无序）向下调整为有序
 3.迭代往根方向往上走-最后整个堆都有序（大堆或小堆）

 //最后一层排好的调整次数N/2*logN 总：O(N*logN)
 
 void Heapsort(int* a, int n)
 {
	
	 for (int i = (n - 1-1) / 2; i >= 0; --i)//n-1为最后一个节点的下标，最后一个节点的父亲下标：（最后一个节点的下标-1）/2
	 {
		 Adjustdown(a, n, i);
	 }
	 int i = 1;
	 while (i < n)
	 {
		 swap(&a[0], &a[n - i]);//把最大的放最后，然后重新排，迭代把最大的头插到后面，排（n-1）次最后排成升序
		 Adjustdown(a, n - i, 0);
		 ++i;
	 }
 }

向下调整

 void Adjustdown(HPDatatype* a, int n, int parent)//向下调整-O(logN)
 {
	 int minchild = 2 * parent + 1;
	 while (minchild < n)
	 {
		 if (minchild + 1 < n && a[minchild + 1] > a[minchild])
		 {
			 minchild++;
		 }
		 if (a[minchild] > a[parent])
		 {
			 swap(&a[minchild], &a[parent]);
			 parent = minchild;
			 int minchild = 2 * parent + 1;
		 }
		 else
		 {
			 break;
		 }
	 }
 }

三、希尔排序

时间复杂度：O(N^1.3)

空间复杂度：O(1)

稳定性：不好

gap越大，直接插入排序就越快，反而不那么有序
gap越小，直接插入排序就越慢，反而更有序

步骤： 

（gap为1的时候为直接插入排序；其余gap>1时为预排序）

1.预排序-接近有序-间隔为gap的数据分为一组，插入排序
2.直接插入排序

 void ShellSort(int* a, int n)
 {
	 int gap = n;
	 while (gap > 1)
	 {
		 gap = gap / 3 + 1;
		
		 for (int i = 0; i < n - gap; i++)
		 {
			 int end = i;
			 int tmp = a[end + gap];
			 while (end >= 0)
			 {
				 if (a[end] > tmp)
				 {
					 a[end + gap] = a[end];
					 end -= gap;
				 }
 
				 else
				 {
					 break;
				 }
			 }
			 a[end + gap] = tmp;
		 }
	 }
 }

四、选择排序

时间复杂度：O(N^2)

空间复杂度：O（1）

稳定性：不好

思路：（要求升序）把第一个元素设为最小值从这里开始找，遍历一轮数组，若找到比最小值还小的元素（遍历元素里面最小的）则交换；

然后把第二个元素作为最小值从这里开始找，遍历......以此类推，到最后一个元素为止

 void SelectSort(int* a, int n)//选择排序-O（N*2）
 {
	 int begin = 0;
	 int end = n - 1;
	 //选出最小的放begin位置
	//选出最大的放end位置
 
	//1.选出最大的数和最小的数
	 while (begin < end)
	 {
		 int minii = begin;
		 int maxi = begin;
		 for (int i = begin + 1; i <= end; ++i)
		 {
			 if (a[i] > a[maxi])
			 {
				 maxi = i;
			 }
			 if (a[i] < a[minii])
			 {
				 minii = i;
			 }
		 }
//2.把最大的数放end位置，把最小的数放begin位置
		 swap(&a[begin], &a[minii]);//最小的数放在begin位置
		 if (maxi == begin)//如果一开始最大的数就在begin位置则这样判断更改bug
		 {
			 maxi = minii;
		 }
		 swap(&a[end], &a[maxi]);//最大的数放在2end位置
//3.范围缩小【begin，end】->【begin+1，end—1】
		 ++begin;
		 --end;
	 }
 }

五、冒泡排序

时间复杂度-最坏（O（N^2)) 最好（O(N))

空间复杂度：O(1)

稳定性：好

步骤：
升序-把最大的放最后
降序-把最小的放最后

 void BubbleSort(int* a, int n)
 {
	 for (int j = 0; j < n; j++)
	 {
		 int exchange = 0;//优化：如果此时顺序符合升序或降序，则跳出循环
		 for (int i = 1; i < n-j; i++)
		 {
			 if (a[i - 1] > a[i])
			 {
				 swap(&a[i - 1], &a[i]);
				 exchange = 1;
			 }
		 }
		 if (exchange == 0)
		 {
			 break;
		 }
	 }
 }

六、快速排序

A、递归实现

1.优化：三数取中：三个数当中取个数值大小为中间值的值

  取出来的值作为keyi

 int Getmidindex(int* a, int left, int right)//三数取中
 {
	 int mid = left + (right - left) / 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 // a[left] >= a[mid]
	 {
		 if (a[mid] > a[right])
		 {
			 return mid;
		 }
		 else if (a[left] < a[right])
		 {
			 return left;
		 }
		 else
		 {
			 return right;
		 }
	 }
 }

霍尔排序：

R找比keyi小的值，找到则停下； L找比keyi大的值，找到则停下；   然后L和R交换，依次到最后碰面，把keyi和碰面时的值交换，完成排序。

最后返回碰面的下标

 int PartSort(int* a, int left, int right)//霍尔排序
 {
	 int mid = Getmidindex(a, left, right);
	 swap(&a[mid], &a[left]);
	 int keyi = left;
	 while (left < right)
	 {
		 //R找小
		 while (left < right && a[right] >= a[keyi])
		 {
			--right;
		 }
			 //L找大
		 while(left < right && a[left] <= a[keyi])
		 {
			++left;
		 }
 
		 if (left < right)
			 swap(&a[left], &a[right]);
	 }
	 int meeti = left;
	 swap(&a[keyi], &a[meeti]);
	 return meeti;
 }

挖坑法 

步骤：

先把key（left)所在位置作为坑位；

然后R先走，找到比keyi小的值则把该值填到坑位，然后该位置为新的坑位；

然后L走，找到比keyi大的值则把该值填到坑位，然后形成新的坑位；

以此类推，最后碰面时作为最后的坑位，把keyi填进去；

最后返回最后坑位的下标

 int PartSort2(int* a, int left, int right)//挖坑法
 {
 
	 int mid = Getmidindex(a, left, right);
	 swap(&a[mid], &a[left]);
	 int key = a[left];
	 int hole = left;
	 while (left < right)
	 {//一开始left为hole
		 //R找小,找到小后就把值填到hole所在的坑，填完就为hole
		 while (left < right && a[right] >= key)
		 {
			 --right;
		 }
		
		 a[hole] = a[right];
		 hole = right;
 
		 //L找大，找到大后就把值填到hole所在的坑，填完就为hole
		 while (left < right && a[left] <= key)
		 {
			 ++left;
		 }
         a[hole] = a[left];
		 hole = left;
	 }
	
	 a[hole] = key;
	 return hole;
 }

前后指针法：

步骤：

cur和prev一起走：如果cur遇到比keyi大的值则prev停下，则cur继续走，之后若遇到比keyi小的值则该值与prev所在的值交换；

以此类推，cur越界后prev停下，此时把prev所在值与keyi交换；

最后返回prev所在的下标

 int PartSort3(int* a, int left, int right)//前后指针法
 {
 
	 int mid = Getmidindex(a, left, right);
	 swap(&a[mid], &a[left]);
	 int keyi =left;
	 int prev = left;
	 int cur = left+1;
	 while (cur<=right)
	 {//cur找比key大的值之后的小
		 if (a[cur] < a[keyi] && ++prev != cur)//prev要和cur有间隔
			 swap(&a[cur], &a[prev]);
		 ++cur;
	 }
	 swap(&a[keyi], &a[prev]);
	 return prev;
 }

以上三种方法都是一轮排序：并不能完全排好，但能把小的值放在左边，大的值放在右边（若升序）；则需要用到递归依次排序好

注：一般情况下 一轮排序最多可把8个值完全排好顺序

总排序-递归（快速排序）

停止排序： 要么剩下一个元素 要么元素不存在（越界）
 时间复杂度：
 无序O(N*logN)
 有序O(N*N)

空间复杂度：O(1)

稳定性：不好

 void QuickSort(int* a, int begin, int end)//单趟-三个区间-2^3=8（最多八个数排序好）
 {
 
	 if (begin >= end)
	 {
		 return;
	 }
	 if (end - begin <= 8)//小区间优化：最后一趟（层）用递归消耗大-直接换插入排序
	 {
		
		 InsertSort(a + begin, end - begin + 1);
	 }
	 else {
		 先对区间[begin,end]进行排序
		// int keyi = PartSort(a, begin, end);//霍尔（hoare)排序
	// int keyi = PartSort2(a, begin, end);//挖坑法
	 int keyi = PartSort3(a, begin, end);//前后指针法
 
 
//经过上面排序好之后可分为区间：[begin,keyi-1],keyi,[keyi+1,end]
 
 
		 //则先对区间：[begin,keyi-1]排序
		// PartSort(a, begin, keyi - 1);//霍尔排序
	//	PartSort2(a, begin, keyi - 1);//挖坑法
		PartSort3(a, begin, keyi - 1);//前后指针法
 
 
		 //再对区间：[keyi+1,end]排序
		 //PartSort(a, keyi + 1, end);//霍尔排序
		// PartSort2(a, keyi + 1, end);//挖坑法
		 PartSort3(a, keyi + 1, end);//前后指针法
	 }
 }

B、非递归实现

栈实现

思路：

若需要需要把数组[9,8,7,6,5,4,3,2,1,0]进行升序排列：

先把下标为0 9push入栈（出栈顺序为9 0 - 对应区间为[0,9]）；

然后取left=0 right=9 并且都pop掉 然后对该区间[left,right]进行排序；

然后分为两个区间[0,4] 5 [6,9]；

然后把下标为 6 9push入栈，再把 下标为 0 4 push入栈 ；

然后取left=0，right=9 并且都pop掉然后对该区域[left,right]进行排序；

然后再分区间......

以此类推

停止排序： 要么剩下一个元素 要么元素不存在（越界）

 void QuickSortNonR(int* a, int begin, int end)
 {
	 ST st;
	 StackInit(&st);
	 StackPush(&st, begin);//放0
	 StackPush(&st, end);//放9
//先出9后出0 则范围为[0,9]则是先对[0,9]范围排序
	 while (!StackEmpty(&st))
	 {
		 int right = StackTop(&st);
		 StackPop(&st);
		 int left = StackTop(&st);
		 StackPop(&st);
		 int keyi = PartSort3(a, left, right);
		 //[left,keyi-1]  keyi [keyi+1,right]
		 if (keyi + 1 < right)//然后先push右边区间
		 {
			 StackPush(&st,keyi+1);
			 StackPush(&st, right);
		 }
 
		 if (left < keyi - 1)//再push左边区间
		 {
			 StackPush(&st, left);
			 StackPush(&st, keyi - 1);
		 }
 
	 }
	 StackDestory(&st);
 }

---

总结

以上六大排序都属于内排序（在内存中中排序），他们非常常见且实用，你也一定要掌握好噢！！！

如果以上内容能对你有帮助的话，麻烦给我一件三联！！！（超大声

不许下次一定（doge