八大排序算法细讲

排序

概念

运用

常见排序算法

插入排序

直接插入排序

思想：

步骤（排升序）:

代码部分：

时间复杂度：

希尔排序

思路

步骤

gap的取法

代码部分：

时间复杂度：

选择排序

直接选择排序

排升序思路：

排升序步骤：

代码部分：

时间复杂度：

堆排序

代码部分：

交换排序

冒泡排序

代码部分：

快速排序（递归版本）

思路：

hoare版本

排升序步骤：

相遇问题：

代码部分：

挖坑法版本

排升序思路：

代码部分：

前后指针版本：

排升序思路：

代码部分：

时间复杂度：

快速排序（非递归版本）

思路：

注意：

编辑

代码部分(找基准值部分用的是前后指针方法)：

归并排序

思路：

排升序步骤：

代码部分：

时间复杂度：

非比较排序

计数排序

思路：

代码部分：

时间复杂度：

排序算法复杂度及稳定性分析

排序

概念

排序就是将一段记录，按照其中的某个或某些关键字大小，实现递增或递减的操作

运用

排序在我们的生活中运用也是极其广泛的，如：在购物软件中，根据不同条件来筛选商品；大学院校的排名……等等

常见排序算法

插入排序

直接插入排序

思想：

把待排序的记录按其关键码值的大小逐个插入到⼀个已经排好序的有序序列中，直到所有的记录插入完为止，得到⼀个新的有序序列

这种排序算法类似于玩扑克牌，就是依次将手中的牌进行排序

步骤（排升序）:

1、先取出第二张牌与第一张进行比较，小的放前面，大的放后面

2、让后面的牌再进行上面那一步

这样看起来会比较抽象，举一个例子来实现就容易理解了

代码部分：

void InsertSort(int* arr, int n)
{
	for (int i = 0; i < n - 1; ++i)
	{
		int end = i;
		int temp = arr[end + 1];
		while (end >= 0)
		{
			if (arr[end] > temp)
			{
				arr[end + 1] = arr[end];
				end--;
			}
			else
			{
				break;
			}
		}
		arr[end + 1] = temp;
	}
}

时间复杂度：

直接插入排序的时间复杂度为O(N^2)，但在一般情况下是不会达到N^2的，只有在排序数组与要求排序方向相反时（也就是逆序），才会达到O(N^2)

这也就导致了一个问题，在面对逆序情况下，使用该排序算法，效率就会大大降低

面对这种情况，前人就在直接插入排序算法的基础上进行了改良，也就是接下来要讲的——希尔排序

希尔排序

根据上面的直接插入排序算法我们可以知道，在面对逆序数组时，算法复杂度太大了（O(N^2)）,

所以前人就在该算法基础上进行了改良

思路

先选定一个整数，命名为gap，通常是gap=n/3+1，将带排序数组中元素根据gap值分为多组，也就是将相距gap值的元素分在同一组中，然后对每一组的元素进行排序，这是就完成一次排序，然后gap=gap/3+1，，再将数组根据gap值分为多组，进行插入排序，当gap=1时，就相当于进行直接插入排序算法。

步骤

步骤一（当gap>1）：

1、将数组根据gap分为多组

2、将相距gap值的元素进行比较

注：步骤一也可以称为预排序，目的是为了：将数组转变为一个相对有序的情况，避免直接插入排序在面对逆序数组情况时时间复杂度变大

排升序时：小的元素在前面，大的元素在后面

排降序时：大的元素在前面，小的元素在后面

步骤二（当gap=1）：

就相当于进行直接插入排序

举例可知

gap的取法

gap值的最初值取该数组的长度，当它进入while循环时，就先进行gap=gap/+1

然而，为什么是对gap/3，而不是除以其他值呢？

如果gap除以的值过小的话，比如：gap=gap/2，就会导致分的组太少，而每组内元素比较次数过多，while循环次数也会增多（因为gap值要不断除以2，直到gap=1时停止while循环）

如果gap除以的值过大的话，比如：gap=gap/8，就会导致分的组过多，而每组内元素比较次数较少，while循环次数少

所以gap除以的值要取适中的值，3则是较好的值

那为何还要加一呢？

加一的目的是为防止gap整除的值为0，这样可以防止gap=0时，直接退出循环，没有排序完全

代码部分：

void ShellSort(int* arr, int n)
{
	int gap = n;
	while (gap > 1)//gap不能等于1，如果为一进入循环，在gap/3+1中就会一直为1，就会死循环
	{
		
		gap = gap / 3 + 1;
		for (int i = 0; i < n - gap; ++i)
		{
			int end = i;
			int temp = arr[end + gap];
			while (end >= 0)
			{
				if (arr[end] > temp)
				{
					arr[end + gap] = arr[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			arr[end + gap] = temp;
		}
	}
	
}

时间复杂度：

希尔排序算法的时间复杂度不好计算，大概为O(N^1.3)

选择排序

直接选择排序

排升序思路：

每一次循环，先从待排数组中找出最大和最小值，将最小值与待排数组的起始位置交换，最大值与待排数组的最后一个元素交换，直到所有待排数组元素排完

排升序步骤：

1、设立起始位置和最后一元素下标位置：begin、end，然后找到最大值和最小值下标

2、将最小值和起始元素交换、最大值和末尾元素交换

3、交换后，begin++、end--，然后进行[begin,end]区间元素的排序，按照上面两步

4、直到begin>end时结束排序

注：当begin与maxi、end与mini重叠时，会造成重复交换，所以就需要将maini和mini进行交换

代码部分：

void SelectSort(int* arr, int n)
{
	int begin = 0, end = n - 1;
	while (begin < end)
	{
		int mini , maxi;
		mini = maxi = begin;
		for (int i = begin + 1; i <= end; ++i)
		{
			if (arr[i] > arr[maxi])
			{
				maxi = i;
			}
			if (arr[i] < arr[mini])
			{
				mini = i;
			}
		}
		if (begin == maxi)
		{
			maxi = mini;
		}
		Swap(&arr[begin], &arr[mini]);
		Swap(&arr[end], &arr[maxi]);

		begin++;
		end--;
	}
}

时间复杂度：

直接选择排序的时间复杂度很好理解，为O(N^2)，因为它的效率不是很好，所以实际上很少会用到

堆排序

堆排序的讲解，在前面的文章已经讲解过了，就不在这里过多说明，有兴趣的朋友可以移步

二叉树：堆的建立和应用_二叉树的应用,两种创建方式-CSDN博客

代码部分：

void AdJustDown(int* arr, int parent, int n)//向下调整
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		//这里左右孩子的比较，c>c+1,交换建小堆;c<c+1,交换建大堆
		//建大堆，先找大孩子；建小堆，先找小孩子
		if (child + 1 < n && arr[child] < arr[child + 1])
		{
			child++;
		}
		//>建大堆
		//<建小堆
		if (arr[child] > arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
void HeapSort(int* arr, int n)//向下调整算法建堆:时间复杂度O(n)
{
	//排升序建大堆
	//排降序建小堆
	//先建堆
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdJustDown(arr, i, n);
	}
	//再排序
	int end = n - 1;
	while (end > 0)
	{
		Swap(&arr[0], &arr[end]);//交换堆顶和尾结点
		AdJustDown(arr, 0, end);
		end--;
	}

}

交换排序

冒泡排序

冒泡排序大家应该都不陌生，是我们C语言学习的第一个排序算法，它的时间复杂度为O(N^2),

关于它的思路步骤我就不过多说明了，它在实际当中也基本不会用到，它是起着一种教学作用的排序算法

代码部分：

void BubbleSort(int* arr, int n)
{
	int i = 0;
	for (i = 0; i < n - 1; ++i)
	{
		int j = 0;
		int flag = 1;
		for (j = 0; j < n - 1 - i; ++j)
		{
			if (arr[j] > arr[j + 1])
			{
				int temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
				flag = 0;
			}
		}
		if (flag == 1)//当提前完成排序后，就直接退出循环
		{
			break;
		}
	}
}

快速排序（递归版本）

快速排序可以说是排序算法中最重要的排序算法，在实际学习和工作中运用得最多，接下来我们来好好学习快速排序算法

思路：

任取待排数组中某一个元素作为基准值(key)，然后将基准值放到正确位置上，按照基准值将数组分割成两个序列，左子序列中所有元素小于基准值，右子序列中所有元素大于基准值（这里排升序），然后再对左右子序列重复该过程，直到所有元素都排列再在相对应位置上为止

hoare版本

排升序步骤：

1、找基准值：

起始令首元素为基准值(key)，设right和left，right为末尾元素下标，left为首元素下标，

让left从左往右找比基准值大的值，right从右往左找比基准值大的值，

找到以后将left与right指向的值进行交换，这个交换的前提是right>=left；

而当right小于left时right所指向的值就与key进行交换，这时key就回到了正确的位置

2、二分

根据key所在位置，对数组进行二分，将数组分为左右两个子序列，然后再对左右两个子序列进行上述操作

相遇问题：

1、相遇点值小于基准值

由此可知，当相遇点小于基准值时，left依旧减减

2、相遇点值大于基准值

由此可知，当相遇点大于基准值时，right依旧加加

3、当相遇点值等于基准值

这种情况看似两种都可以，但是当选择了right依旧减减时，就会导致面对下面这种情况时，时间复杂度大大提高

这种情况便是相遇点值与基准值相同的情况，在这种情况下，该排序算法的时间复杂度就会大大提高，无法进行高效的分割排序

其实这也是这种hoare版本快速排序在面对待排数组中重复元素过多情况下的弊端

代码部分：

int Hoare_QuickSort(int* arr, int left, int right)
{
	int keyi = left;
	left++;
	while (left <= right)
	{
		//rigth从右往左找比基准值小的值
		while (left<=right && arr[right]>arr[keyi])//这里的arr[rigth]>arr[keyi]只能取大于号，不能加上等于号，
												   //加上的话在面对数组全相等或有序数组时，时间复杂度会变大
		{
			right--;
		}
		//left从左往右找比基准值大的值
		while (left<=right && arr[left]<arr[keyi])//这里的情况和rigth是一样的
		{
			left++;
		}
		if (left <= right)//当left还未大于rigth时，就进行交换
		{
			Swap(&arr[left], &arr[right]);
		}
	}
	Swap(&arr[right], &arr[keyi]);
	keyi = right;
	return keyi;
}

void QuickSort(int* arr, int left, int right)//排升序
{
	if (left >= right)
	{
		return;
	}
	//找基准值
	int keyi = Hoare_QuickSort(arr, left, right);

	//二分
	//[left,keyi-1] keyi [keyi+1,right]
	QuickSort(arr, left, keyi - 1);
	QuickSort(arr, keyi + 1, right);

}

挖坑法版本

排升序思路：

设立左右指针：left、right，先将基准值视为第一个坑：hole，

right从右往左找比基准值小的数，找到以后就放入到hole的位置，然后righ处就为新的坑；

left从左往右找比基准值大的数，找到以后就放入到hole的位置，然后left处就为新的坑；

当right==left时，就将保存的基准值放入到两者相遇处

就这样便完成了第一次基准值的寻找

找到以后就和hoare版本一样进行二分

注：

这种方法起始的left只能指向首元素；

和hoare版本不同的是，当right从右往左找比基准值小的值时，当遇到比基准值大的或者等于的值时，继续往左找；left也是一样的

代码部分：

int Hole_QuickSort(int* arr, int left, int right)
{
	int hole = left;
	int key = arr[hole];
	while (left < right)
	{
		while (left<right && arr[right]>=key)
		{
			right--;
		}
		//找到比基准值小的值
		arr[hole] = arr[right];
		hole = right;
		while (left<right && arr[left]<=key)
		{
			left++;
		}
		//找到比基准值大的值
		arr[hole] = arr[left];
		hole = left;
	}
	//right和left相遇
	arr[hole] = key;
	return hole;
}

void QuickSort(int* arr, int left, int right)//排升序
{
	if (left >= right)
	{
		return;
	}
	//找基准值
	int keyi = Hole_QuickSort(arr, left, right);

	//二分
	//[left,keyi-1] keyi [keyi+1,right]
	QuickSort(arr, left, keyi - 1);
	QuickSort(arr, keyi + 1, right);

}

前后指针版本：

排升序思路：

设立两个变量：pcur(用于探路，来找比基准值小的值)，prev(在pcur的后面)

1、当找到比基准值小的值时，++prev，prev所指向的元素和pcur所指向的元素交换，然后++pcur

2、当pcur所指向的元素没有比基准值小时，++pcur

当pcur越界(pcur>right)时，就将基准值与prev所指向的元素交换，就这样就实现了将比基准值小的元素放在基准值左边，大的放在右边

注：

有时候prev++后的值正好等于pcur，这个时候就不需要发生交换

代码部分：

int lomuto_QuickSort(int* arr, int left, int right)
{
	int prev = left, pcur = prev + 1;
	int keyi = left;
	while (pcur <= right)
	{
		if (arr[pcur] < arr[keyi]&&++prev != pcur)
		{
			Swap(&arr[prev], &arr[pcur]);
		}
		pcur++;
	}
	Swap(&arr[prev], &arr[keyi]);
	keyi = prev;
	return keyi;
}


void QuickSort(int* arr, int left, int right)//排升序
{
	if (left >= right)
	{
		return;
	}
	//找基准值
	int keyi = lomuto_QuickSort(arr, left, right);

	//二分
	//[left,keyi-1] keyi [keyi+1,right]
	QuickSort(arr, left, keyi - 1);
	QuickSort(arr, keyi + 1, right);

}

时间复杂度：

快速排序算法的时间复杂度为O(NlogN),在特殊情况下：待排数组中重复元素很多的时候，会到造成时间复杂度上升为O(N^2logN),这一点要记住，这与如何解决这一情况，在后面的文章中会着重讲解

快速排序（非递归版本）

我们讲解了递归版本的快速排序，那也会有非递归版本的快速排序

在非递归版本的快速排序和递归版本的快速排序有什么区别呢？

非递归版本的快速排序算法需要借助数据结构：栈来实现

思路：

我们首先需要建立一个栈，然后：

1、将数组的left和right下标入栈

2、进入一个循环(结束条件：栈为空)，将从栈中出来的两个元素命名为begin和end

3、然后对[begin,end]这个区间来找基准值，找基准值的方法在上面已经说了三种方法，随便用那个都行

4、找完以后，根据基准值进行二分为左右两个子序列，再将左右两个子序列的首尾下标入栈，再重复上面的操作

注意：

1、当begin大于或等于keyi-1或者end小于或等于keyi+1时不进行入栈操作，也就是只有在begin<keyi-1或end>keyi+1的情况下才允许入栈操作

2、每次找完基准值后还要确定一次待排区间中下标是否都入栈了，首尾下标要再入一次栈，入栈条件也要满足上面的条件

3、建立了栈，在排完序后就需要进行销毁

如果对栈还有所不解的朋友，可以移步至【数据结构初阶】栈和队列的建立_实现线性表、栈和队列(要求顺序和链式两种实现)-CSDN博客

其实非递归版快速排序就是利用栈这一数据结构来模拟实现正常快速排序中的递归过程

代码部分(找基准值部分用的是前后指针方法)：

void QuickSortNonR(int* arr, int left, int right)//非递归版本
{
	ST st;
	StackInit(&st);
	StackPush(&st, right);
	StackPush(&st, left);
	while (!StackEmpty(&st))
	{
		int begin = StackTop(&st);
		StackPop(&st);
		int end = StackTop(&st);
		StackPop(&st);
		
		int keyi = lomuto_QuickSort(arr, begin, end);
		if (end > keyi + 1)
		{
			StackPush(&st, end);
			StackPush(&st, keyi+1);
		}
		if (begin < keyi - 1)
		{
			StackPush(&st, keyi - 1);
			StackPush(&st, begin);
		}
	}

	StackDestroy(&st);

}

归并排序

思路：

将待排序数组不断进行二分，直到划分为一个个有序的子序列，然后再将这些子序列两两合并，成一个有序数组

也就是先二分再合并

排升序步骤：

1、二分：

对数组取中间值(mid),进行二分，要保证数组最左边下标left要小于最右边下标right(left<right)

mid = left+(right-left)/2

根据mid分为左右两个子序列([left,mid-1]，[mid+1,right])

直到left大于或等于right时停止二分

2、合并：

将相邻有序数组两两合并为一个有序数组，并将这个有序数组存储在一个临时数组(temp)中

要注意的是：每次放入临时数组结束后，两个数组中可能会有元素没有放入到临时数组中，所以循环结束后要对两个数组进行检查，再进行一次放入临时数组

3、将临时数组中元素放回原先数组中

代码部分：

void _MergeSort(int* arr, int left, int right, int* temp)
{
	//二分
	if (left >= right)
	{
		return;
	}
	int mid = left + (right - left) / 2;
	_MergeSort(arr, left, mid,temp);
	_MergeSort(arr, mid+1, right,temp);
	//合并
	int begin1 = left, end1 = mid;
	int begin2 = mid+1, end2 = right;
	int i = begin1;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (arr[begin1] < arr[begin2])
		{
			temp[i++] = arr[begin1++];
		}
		else
		{
			temp[i++] = arr[begin2++];
		}
	}
	//两个区间可能还有元素没有入temp
	while (begin1 <= end1)
	{
		temp[i++] = arr[begin1++];
	}
	while (begin2 <= end2)
	{
		temp[i++] = arr[begin2++];
	}

	//将temp中元素放回原数组中
	for (int i = left; i <= right; ++i)
	{
		arr[i] = temp[i];
	}
}

void MergeSort(int* arr, int n)
{
	int* temp = (int*)malloc(sizeof(int) * n);
	_MergeSort(arr, 0, n - 1, temp);
	free(temp);
}

时间复杂度：

归并排序算法时间复杂度为O(NlogN)，它二分的次数为logN次，合并次数为N次

非比较排序

计数排序

思路：

1、

先找出数组中的最大、最小值，

用最大值和最小值来求出待排数组中元素的出现次数数组大小

用一次数组来存储元素出现次数：count，它的大小为range = max-min+1

2、

遍历数组，求出待排数组中各个元素出现的次数

将每个元素和最小值相减可以得出它在countg数组中的下标，则该对应下标存储的值就加一

3、

根据count数组向原数组中放入元素

arr[index] = i + min

注：

当min和max跨度很大时就会造成空间的浪费，那就不适合这种算法

代码部分：

void CountSort(int* arr, int n)
{
	//先找最大值和最小值
	int max = arr[0], min = arr[0];
	for (int i = 1; i < n; ++i)
	{
		if (arr[i] > max)
		{
			max = arr[i];
		}
		if (arr[i] < min)
		{
			min = arr[i];
		}
	}
	int range = max - min + 1;
	int* count = (int*)malloc(sizeof(int) * range);
	if (count == NULL)
	{
		perror("malloc,fail!");
	}
	//初始化数组
	memset(count, 0, sizeof(int*) * range);
	//统计次数
	for (int i = 0; i < n; ++i)
	{
		count[arr[i] - min]++;
	}
	//将count中出现的次数还原到原数组中
	int index = 0;
	for (int i = 0; i < range; ++i)
	{
		while (count[i]--)
		{
			arr[index++] = i + min;
		}

	}
}

时间复杂度：

计数排序在数据范围集中时，效率很高，但是适用范围及场景有限

它的时间复杂度为O(N+range)

排序算法复杂度及稳定性分析

稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录

的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，⽽在排序后的序列中，r[i]仍在r[j]

之前，则称这种排序算法是稳定的；否则称为不稳定的。

排序方法	平均情况	最好情况	最坏情况	辅助空间	稳定性
冒泡排序	O(N^2)	O(N)	O(N^2)	O(1)	稳定
直接选择排序	O(N^2)	O(N^2)	O(N^2)	O(1)	不稳定
直接插入排序	O(N^2)	O(N)	O(N^2)	O(1)	稳定
希尔排序	O(NlogN)~O(N^2)	O(1.3)	O(N^2)	O(1)	不稳定
堆排序	O(NlogN)	O(NlogN)	O(NlogN)	O(1)	不稳定
归并排序	O(NlogN)	O(NlogN)	O(NlogN)	O(N)	稳定
快速排序	O(NlogN)	O(NlogN)	O(N^2)	O(logn)~O(N)	不稳定