数据结构：排序

目录

前言

一、常见的排序算法

 二、常见的排序算法的实现

1.插入排序

1.1基本思想

1.2直接插入排序

1.3希尔排序( 缩小增量排序 )

2.选择排序

2.1基本思想

2.2直接选择排序

2.3堆排序

 3.交换排序

3.1基本思想

3.2冒泡排序

 3.3快速排序

3.3.1 hoare版本

3.3.2挖坑法

3.3.3前后指针法

 3.3.4快速排序非递归实现

4.归并排序 

4.1基本思想

4.2递归实现 

 4.3非递归实现

5.非比较排序 

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

前言

排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。

内部排序：数据元素全部放在内存中的排序。

外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不断地在内外存之间移动数据的排序。

排序的运用：

一、常见的排序算法

 二、常见的排序算法的实现

1.插入排序

1.1基本思想

每一步将一个待排序的对象按其关键码值的大小，插入到一个有序的序列中，直到所有的对象插入完成，这时会得到一个新的有序序列。

实际上我们在玩扑克牌时整理牌时就要用到插入排序：

1.2直接插入排序

将第i（i>=1）元素插入已经有序的序列，将第i个元素与其前面a[i-1]、a[i-2].....进行比较，找到位置后插入，原位置和其后面的元素均往后移一位。

动图演示：

直接插入排序的特性总结：

1. 元素集合越接近有序，直接插入排序算法的时间效率越高

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

3. 空间复杂度：O(1)，它是一种稳定的排序算法

4. 稳定性：稳定

 代码实现及原理如下：

1.因为待插入的元素位置下标为end+1，又因为当所有元素插入时长度为n，所以下表范围是[0,n-1],为了防止越界，end+1<=n-1，即end<n-1,i<n-1。

2.当待插入的元素小于或大于有序中的所有元素，此时end=-1，我们将a[end+1]=tmp放在循环外。

void InsertSort(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		//数组在[0,end]范围内 
        //单趟  
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (tmp > a[end])
			{
				a[end + 1] = a[end];
                end--;
			}
			else
			{
				break;
			}
			
		}
		a[end + 1] = tmp;
	}
}

1.3希尔排序( 缩小增量排序 )

动图演示：

希尔排序是直接插入排序的改良，为防止排序所需要的时间复杂度过高。

希尔排序的基本思想：

希尔排序可以分解为两个大步骤：

一、(gap>1)预排序

1、先定义一个整数gap，gap为几就分为几组，所有距离为gap的记录分在同一组内，并对每一组内的记录进行排序。

2、逐渐减小gap的值，然后继续进行上面的步骤。直到gap=1.

二、（gap==1）直接插入排序

希尔排序的特征：

1、 希尔排序是对直接插入排序的优化。

2、预排序目的是为了是使数组更接近有序，待（gap==1）数组接近有序，直接插入排序会更快。这样整体而言，可以达到优化的效果。

3、希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的 希尔排序的时间复杂度都不固定

4、时间复杂度为O（N^1.3）

5. 稳定性：不稳定

代码实现 

以下有两中表示方式

1、 

void ShellSort(int* a, int n)
{
	int gap = n;
	// +1保证最后一个gap一定是1
		// gap > 1时是预排序
		// gap == 1时是插入排序
	while (gap > 1)
	{
		gap = gap / 3 + 1;
		for (int j = 0; j < gap; j++)
		{
			for (int i = j; i < n-gap; i += gap)//一个gap的趟
			{
				//单趟
				int end = i;
				int tmp = a[end + gap];
				while (end >= 0)
				{
					if (tmp > a[end])
					{
						a[end + gap] = a[end];
						end -= gap;
					}
					else
					{
						break;
					}
				}
				a[end + gap] = tmp;
			}
		}
	}	
}

2、

void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap > 1)
	{
		// +1保证最后一个gap一定是1
		// gap > 1时是预排序
		// gap == 1时是插入排序
		gap = gap / 3 + 1;
 
		for (size_t i = 0; i < n - gap; ++i)
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (tmp < a[end])
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}
}

2.选择排序

2.1基本思想

每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的 数据元素排完 。

2.2直接选择排序

动图演示：

 选择排序的基本思想：

1、第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始(末尾)位置。

2、然后选出次小(或次大)的一个元素，存放在最大(最小)元素的下一个位置。

3、重复这样的步骤直到全部待排序的数据元素排完 。

 代码如下：

注意：这里我们进行一个优化，我们在待排序的元素中，一次找到最大和最小的元素，分别放在起始和末尾。

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

1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用。

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

3. 空间复杂度：O(1)

4. 稳定性：不稳定

2.3堆排序

堆排序是指利用树这种数据结构，完成的排序，它是选择排序的一种，通过堆来选择数据，升序建大堆，降序建小堆。

堆排序的基本思路：

1.首先将数组看作一个完全二叉树，从最后一父节点开始到第一个，先通过向下调整算法，让数组建大或小堆，升序建大堆，降序建小堆。

2.建堆之后，然后按照堆删的思想将堆顶和堆底的数据交换，但不同的是这里不删除最后一个元素。

3.这样最大元素就在最后一个位置，然后从堆顶向下调整到倒数第二个元素，这样次大的元素就在堆顶，重复上述步骤直到只剩堆顶时停止。

void AdjustDown(int* a, int n, int parent)//向下调整
{
	//假设法子节点的左节点小
	int child = parent * 2 + 1;
	while (child + 1 < n && child < n)
	{
		if (a[child] > a[child + 1])
		{
			child++;
		}
		if (a[parent] > a[child])
		{
			swap(&a[parent], &a[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
void HeapSort(int* a, int n)
{
	//降序，建大堆
	//升序，建大堆
	//向下建堆法
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}
	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		--end;
	}
}

直接选择排序的特性总结 ：

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

2. 空间复杂度：O(1)。

3.堆排序使用堆来选数，效率就高了很多。

4. 稳定性：不稳定

 3.交换排序

3.1基本思想

基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排 序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

3.2冒泡排序

动图演示：

冒泡排序的基本思路： 

1.两两元素进行比较，前一个比后一个大就交换，直到将最大的元素放在最后一个，这是第一趟。

2.总共进行N-1趟。

代码如下：

void Bubble(int* a, int n)
{
	int flag = 1;
	for (int j = 0; j < n - 1; j++)
	{
		for (int i = 0; i < n-j-1; i++)//一趟
		{
			if (a[i] > a[i + 1])
			{
				Swap(&a[i], &a[i + 1]);
				flag = -1;
			}
		}
		若某一趟排序中没有元素交换则说明所有元素已经有序，不需要再排序
		if (flag == 1)
			break;
	}
}

 冒泡排序的特点总结：

1. 冒泡排序是一种非常容易理解的排序

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

3. 空间复杂度：O(1)

4. 稳定性：稳定

 3.3快速排序

基本思路：任取待排序元素序列中 的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右 子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

3.3.1 hoare版本

动图演示：

具体思路：

1.选取一个基准值（key），最好选最左或最右。

2.确定两个指针，left和right分别从最左和最右向中遍历。

3.如果以最左值为基准值则right指针先移动，如果以最右值为基准值则left指针先移动，接下来我们以最左值为基准值进行分析。

4.right指针先走遇到小于key的值停下，left再走遇到大于key的值停下，两者的值进行交换。

5.重复4的步骤。

6.当right与left相遇时，最后将基准值的值与left位置的值交换，且key的位置转移到left的位置。

 通过上面的思路，使基准值的左侧的值均小于基准值，基准值的右侧均大于基准值。

然后在通过递归，将基准值左右两侧的区间分别重复上面的步骤即可。

代码实现：

void quickSort(int* a, int left, int right)
{
	//判断是否排晚
	if (left >= right)
	{
		return;
	}
//创建两个指针代替left和right
	int begin = left, end = right;
	int key = begin;
		while (end > begin)
		{
			//右侧先走,找小
			while (begin < end && a[end] >= a[key])
			{
				end--;
			}
			//左侧找大
			while (begin < end && a[begin] <= a[key])
			{
				begin++;
			}
			Swap(&a[end], &a[begin]);
		}
		Swap(&a[begin], &a[key]);
		key = begin;
		//[left,key-1]  [key]  [key+1,right] 分为两个区间
		quickSort(a, left, key - 1);
		quickSort(a, key + 1, right);
	}
	
}

3.3.2挖坑法

挖坑法是hoare版本的适当改变，思路还是相似的。

动图演示：

基本思路：

 1.选取一个基准值（key），最好选最左或最右（这里我们选最左），直接取出，留下一个坑位。

2.确定两个指针，left和right分别从最左和最右向中遍历。

3.right指针先移动找到小于key的值，直接放到坑位，left指针再走找到大于key的值，直接放到坑位。

4.重复3的步骤。

5.当right与left相遇时，直接将key的值放在坑位。

代码如下：

int quickSort02(int* a, int left, int right)
{
	int begin = left, end = right;
	int key = a[left];
	//坑位为]
	int hole = left;
	while (end > begin)
	{
		//右侧先走,找小
		while (begin < end && a[end] >= key)
		{
			end--;
		}
			a[hole] = a[end];
			hole = end;
		//左侧找大
		while (begin < end && a[begin] <=key)
		{
			begin++;
		}
			a[hole] = a[begin];
			hole= begin;
	}
	hole = begin;
	a[hole] = key;
	return hole;
}
void Quicksort2(int* a, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	int keyi = quickSort02(a, left, right);
	//[left,key-1]  [key]  [key+1,right]
	Quicksort2(a, left, keyi - 1);
	Quicksort2(a, keyi + 1, right);
}

3.3.3前后指针法

动图演示：

基本思路： 

1.选定基准值，定义prev和cur指针(cur = prev + 1)。

2.cur先走，遇到小于基准值的数停下，然后将prev向后移动一个位置

3.交换cur和prev的值。

4.重复上面的步骤，直到cur跳出数组范围。

5.最后将基准值与prev对应位置交换

6.在进行递归。

代码如下：

void quickSort03(int* a, int left, int right)
{
	if (left >= right)
		return;
	int key = left;
	int prev = left,cur=prev+1;
	while (cur <=right)
	{
		//找小
		while (a[cur] < a[key]&&++prev!=cur)
		{
			Swap(&a[prev], &a[cur]);
		}
		cur++;
	}
	Swap(&a[prev], &a[key]);
	key = prev;
	quickSort03(a, left, key - 1);
	quickSort03(a, key + 1, right);
}

 3.3.4快速排序非递归实现

使用递归完成快速排序肯能会出现栈溢出的风险，这里我们使用非递归实现可以避免。

基本思路：

1.先建立一个栈，将数组的区间压入。（先右后左）

2.如果栈不为空，分别取两次栈顶。

3.将取出的区间，按挖坑法（也可以用其它两种方法），得到key的值。

4.分为[left,key-1]和[key+1,right]两个区间，先将右区间压入，在压入左区间。

5.重复上面的步骤，直至栈为空。

代码如下：

void QuickSortNonR(int* a, int left, int right)
{
	ST st;
	STInit(&st);
	STPush(&st, right);
	STPush(&st, left);
	while (!(STEmpty(&st)))
	{
		int begin=STTop(&st);
		STPop(&st);
		int end=STTop(&st);
		STPop(&st);
		int keyi = quickSort02(a, left, right);
		if (keyi+1 < right)
		{
			STPush(&st, end);
			STPush(&st, keyi+1);
		}
		if (left<keyi-1)
		{
			STPush(&st, keyi-1);
			STPush(&st, begin);
		}
	}
	STDestroy(&st);
}

快速排序的特点总结：

1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序。

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

3. 空间复杂度：O(logN)

4. 稳定性：不稳定

4.归并排序 

4.1基本思想

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有 序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 归并排序核心步骤

动图演示： 

4.2递归实现 

基本思想：

1.先将数组划分，一分二、二分四、……直到只剩下一个。

2.一个数据认为是有序的。

3.合并回去时在进行有序排序。

代码如下：

void _MergeSort(int* a, int left, int right, int* tmp)
{
	if (left >= right)
		return;
	int mid = (right + left) / 2;
	_MergeSort(a + left, left, mid , tmp);
	_MergeSort(a + left, mid + 1, right, tmp);
	//[begin1,end1]   [begin2,end2]
	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;
	int i = left;
	//合并排序
	while (begin1 <= end1 && begin2 <=end2)//有一个数组没插满
	{
		if (a[begin1] < a[begin2])
		{
			tmp[i++] = a[begin1];
			begin1++;
		}
		else
		{
			tmp[i++] = a[begin2];
			begin2++;
		}
	}
	while (begin1 <=end1)
	{
		tmp[i++] = a[begin1];
		begin1++;
	}
	while (begin2 <= end2)
	{
		tmp[i++] = a[begin2];
		begin2++;
	}
	memcpy(a + left, tmp+left, sizeof(int) * (right - left + 1));
}
 
	void MergeSort(int* a, int n)
	{
		int* tmp = (int*)malloc(sizeof(int) * n);
		if (tmp == NULL)
		{
			perror("malloc fail");
		}
		_MergeSort(a, 0, n - 1, tmp);
		free(tmp);
		tmp = NULL;
	}

 4.3非递归实现

1.先一个元素一组，在两个元素一组，四个元素一组直到所有的归并完。

注意：

我们可能会遇到下面三种情况

①[begin2,end2]越界,这时不用归并了；

②[end1,end2]越界，这时不用归并了；

③[end2,end2]越界，这时修正一下，将end2=n-1；

代码如下： 

void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail");
	}
	int gap = 1;
	while (gap <n)
	{
		
		for (int i = 0; i < n; i+= gap * 2)// 0  2 
		{
			int begin1 = i, end1 = gap + i - 1;
			int begin2 = gap + i, end2 = 2 * gap + i - 1;
			// 第二组都越界不存在，这一组就不需要归并
			if (begin2 >= n)
				break;
 
			// 第二的组begin2没越界，end2越界了，需要修正一下，继续归并
			if (end2 >= n)
				end2 = n - 1;
			int j = i;
			while (begin1 <= end1 && begin2 <= end2)//有一个数组没插满
			{
				if (a[begin1] < a[begin2])
				{
					tmp[j++] = a[begin1];
					begin1++;
				}
				else
				{
					tmp[j++] = a[begin2];
					begin2++;
				}
			}
			while (begin1 <= end1)
			{
				tmp[j++] = a[begin1];
				begin1++;
			}
			while (begin2 <= end2)
			{
				tmp[j++] = a[begin2];
				begin2++;
			}
			memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));
		}
		gap = gap * 2;
	}
}

归并排序的特性总结：

1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。

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

3. 空间复杂度：O(N)

4. 稳定性：稳定

5.非比较排序 

基本思路：

1.统计相同元素出现的次数。

2.将次数放在与新建立的数组下标相同的地方，该新建立的数组的其它值均设为0。

3.根据统计的结果将序列回收到原来的序列中.

注意：

①新建立的数组大小为最大值--最小值+1；（MAX-MIN+1）;

②为了防止元素差距过大导致创建空间浪费，我们可以让每个元素减最小值

void countsort(int* a, int n)
{
	
	int max = a[0];
	int min = a[0];
	for (int i = 1; i < n; i++)//找到最大值和最小值
	{
		if (a[i] > max)
		{
			max = a[i];
		}
		if (a[i] < min)
		{
			min = a[i];
		}
	}
	//创建一个新的数组，大小为max-min+1；
	int range = max - min + 1;//6
	int* count = (int*)calloc(range, sizeof(int));
	if (count == NULL)
	{
		perror("calloc fail");
	}
	//统计各个元素的个数
	for (int f = 0; f < n; f++)
	{
		count[a[f] - min]++;
	}
	//返回给原数组
	int j = 0;
	for (int k = 0; k < range; k++)
	{
		while (count[k]--)
		{
			a[j++] = k + min;
		}
	}
	free(count);
	count = NULL;
}

 计数排序的特性总结：

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

2. 时间复杂度：O(MAX(N,范围))

3. 空间复杂度：O(范围)

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