数据结构中常见的排序

排序的概念

• 排序：使一串记录，按照其中某个或某些关键字的大小，递增或递减的排列起来的操作
• 稳定性：假定在待排序的记录序列中，存在多个具有相同关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，arr[ i ]=arr[ j ，且]arr[ i ]在arr[ j ]之前，而在排序后的序列中，arr[ i ]仍然在arr[ j ]之前，则称这种排序算法是稳定的，反之则不稳定。
• 内部排序：数据元素全部放在内存中的排序
• 外部排序：数据元素太多，不能同时存放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

常见的排序有：

• 插入排序：直接插入排序，希尔排序
• 选择排序：选择排序，堆排序
• 交换排序：冒泡排序，快速排序
• 归并排序：归并排序
• 非比较排序：计数排序

插入排序

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

直接插入排序

当插入第 i (i >= 1)个元素时，前边的arr[ 0 ],arr[ 1 ],…,arr[ i - 1]已经排好序，此时用arr[ i ]的排序码与arr[ i - 1 ]，arr[ i - 2 ] …的排序码进行比较，找到插入位置即将其插入，原来的元素顺序后移，代码如下：

void insert_Sort(int* arr, int size)
{
	for (int i = 0; i < size - 1; i++)
	{
		int end = i;
		int key = arr[end + 1];
		while (end >= 0 && arr[end] > key)
		{
			arr[end + 1] = arr[end];
			end--;
		}
		arr[end + 1] = key;
	}
}

特点：

1. 时间复杂度：最坏O(N²)，平均O(N²)，最好O(N)
2. 空间复杂度O(1)
3. 稳定性：稳定
4. 数据敏感性：敏感

希尔排序

直接插入排序的优化版本，在直接插入排序的基础上增加了步长这一概念，将待排序序列按照步长分成小组，组内进行插入排序，缩短步长，进行多轮排序。
代码如下：

void shell_Sort(int* arr, int size)
{
	int gap = size;
	while (gap > 1)
	{
		gap = gap / 3 + 1;
		for (int i = 0; i < size - gap; i++)
		{
			int end = i;
			int key = arr[end + gap];
			while (end >= 0 && arr[end] > key)
			{
				arr[end + gap] = arr[end];
				end -= gap;
			}
			arr[end + gap] = key;
		}
	}
}

特点：

1. 时间按复杂度：最坏O(N^1.3)，平均O(N^1.3)，最好O(N)
2. 空间复杂度O(1)
3. 稳定性，不稳定，分组时相同值元素不一定可以分到同一组，预排序时可能导致相对位置发生变化
4. 数据敏感性：敏感

选择排序

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

直接选择排序

在元素集合array[i]–array[n-1]中选择关键码最大(小)的数据元素，若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交，在剩余的array[ i ]–array[n-2]（array[i+1]–array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素
代码如下：

void select_Sort(int* arr, int size)
{
	for (int i = 0; i < size; i++)
	{
		int start = i;
		int min = start;
		for (int j = start + 1; j < size; j++)
		{
			if (arr[j] < arr[min])
				min = j;
		}
		swap(arr, start, min);
	}
}

特点：

1. 时间复杂度：最坏O(N²)，平均O(N²)，最好O(N²)
2. 空间复杂度：O(1)
3. 稳定性：稳定
4. 敏感性：不敏感

优化版本：

void select2_Sort(int* arr, int size)
{
	int begin = 0;
	int end = size - 1;
	while (end > begin)
	{//每次选择一个最大值和最小值
		int min = begin;
		int max = end;
		for (int i = begin + 1; i <= end; i++)
		{
			if (arr[i] >= arr[max])
				max = i;
			if (arr[i] < arr[min])
				min = i;
		}
		swap(arr, begin, min);//最小值放在begin
		if (max == begin)
			max = min;//如果最大值位置发生变化，需要更新位置
		swap(arr, end, max);//最大值放在end
		begin++;
		end--;
	}
}

堆排序

建堆进行排序，升序建大堆，降序建小堆，通过循环删除堆顶元素进行排序
代码如下：

void shiftDown(int* arr, int size, int parent)
{
	//小堆
	//int child = 2 * parent + 1;
	//while (child < size)
	//{
	//	if (child + 1 < size && a[child + 1] < a[child])
	//		child++;
	//	if (a[child] < a[parent])
	//	{
	//		Swap(a, child, parent);
	//		parent = child;
	//		child = 2 * parent + 1;
	//	}
	//	else
	//	{
	//		break;
	//	}
	//}
	//大堆
	int child = 2 * parent + 1;
	while (child < size)
	{
		if (child + 1 < size && arr[child + 1] > arr[child])
			child++;
		if (arr[child] > arr[parent])
		{
			swap(arr, child, parent);
			parent = child;
			child = 2 * parent + 1;
		}
		else
		{
			break;
		}
	}
}
void heap_Sort(int* arr, int size)
{
	for (int parent = (size - 2) / 2; parent >= 0; parent--)
	{
		shiftDown(arr, size, parent);
	}
	while (size > 1)
	{
		swap(arr, 0, size - 1);
		size--;//循环删除堆顶元素并向下调整
		shiftDown(arr, size, 0);
	}
}

特点：

1. 时间复杂度：恒为O(N*Log₂N)
2. 空间复杂度：O(1)
3. 稳定性：不稳定，调整的过程中相对位置可能发生变化
4. 数据敏感性：不敏感

交换排序

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

冒泡排序

进行多轮比较，每次将最值移到末端，代码如下：

void bubble_Sort(int* arr, int size)
{
	while (size)
	{
		int flag = 1;
		int end = size;
		for (int i = 1; i < end; i++)
		{
			if (arr[i - 1] > arr[i])
			{
				swap(arr, i - 1, i);
				flag = 0;
			}
		}
		if (flag)
			break;
		size--;
	}
}

特点：

1. 时间复杂度：最坏O(N²)，平均O(N²)，最好O(N)
2. 空间复杂度：O(1)
3. 稳定性：稳定
4. 敏感性：敏感

快速排序

任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。常见的划分方式有，hoare划分，挖坑法，前后指针法。
代码如下：

int getMid(int* arr, int begin, int end)
{//快排优化：三数取中
	int mid = begin + (end - begin) / 2;
	if (arr[begin] < arr[mid])
	{
		if (arr[mid] < arr[end])
			return mid;
		else
			return arr[begin] > arr[end] ? begin : end;
	}
	else
	{
		if (arr[end] < arr[mid])
			return mid;
		else
			return arr[begin] < arr[end] ? begin : end;
	}
}

int partion(int* arr, int begin, int end)//hora划分
{
	//int key = arr[begin];//基准值
	int mid = getMid(arr, begin, end);
	swap(arr, mid, begin);

	int key = arr[begin];//基准值
	int start = begin;
	while (begin < end)
	{
		while (end > begin && arr[end] >= key)
			end--;//从后往前找到第一个小于key的值
		while (end > begin && arr[begin] <= key)
			begin++;//从前向后找到第一个大于key的值
		swap(arr, begin, end);//交换二者
	}
	swap(arr, start, begin);//交换基准值和相遇位置
	return begin;//返回改变后的基准值的索引
}

int partion2(int* arr, int begin, int end)//挖坑法
{
	int mid = getMid(arr, begin, end);
	swap(arr, mid, begin);

	int key = arr[begin];//挖掉基准值
	while (end > begin)
	{
		while (end > begin && arr[end] >= key)
			end--;//先从后往前找到第一个小于key的值
		arr[begin] = arr[end];//填补基准值挖出来的坑
		while (end > begin && arr[begin] <= key)
			begin++;//从前往后找到第一个大于key的值
		arr[end] = arr[begin];//填补上一步挖的坑
	}
	arr[begin] = key;//相遇时把基准值塞进来
	return begin;
}

int partion3(int* arr, int begin, int end)//前后指针法
{
	int mid = getMid(arr, begin, end);
	swap(arr, mid, begin);

	int prev = begin;//prev：最后一个小于基准值的位置
	int cur = prev + 1;//cur：新发现的下一个小于基准值的位置
	int key = arr[begin];//基准值
	while (cur <= end)
	{
		if (arr[cur] < key && ++prev != cur)//新发现的小于基准值的数据和prev不连续，说明中间含有大于基准值的数据，故交换
			swap(arr, cur, prev);//小数据向前，大数据向后
		cur++;
	}
	swap(arr, begin, prev);
	return prev;
}

void quick_Sort(int* arr, int begin, int end)//快速排序
{
	if (begin >= end)
		return;
	int keyPos = partion2(arr, begin, end);
	quick_Sort(arr, begin, keyPos - 1);
	quick_Sort(arr, keyPos + 1, end);
}

特点：

1. 时间复杂度：最坏O(N²)（优化后可以避免），平均O(N* Log₂N)，最好O(N* Log₂N)
2. 空间复杂度：O( Log₂N) 函数调用栈，极端情况O(N)(优化后可避免)
3. 稳定性：不稳定
4. 敏感性：敏感

非递归实现：

//栈实现非递归
void quick_Sort_NoR_Stack(int* arr, int size)
{
	Stack st;
	StackInit(&st);
	if (size > 1)
	{
		StackPush(&st, size - 1);
		StackPush(&st, 0);
	}
	while (!StackEmpty(&st))
	{
		int begin = StackTop(&st);
		StackPop(&st);
		int end = StackTop(&st);
		StackPop(&st);

		int keyPos = partion2(arr, begin, end);
		 
		if (keyPos + 1 < end)
		{
			StackPush(&st, end);
			StackPush(&st, keyPos + 1);
		}
		if (begin < keyPos - 1)
		{
			StackPush(&st, keyPos - 1);
			StackPush(&st, begin);
		}
	}
}

//队列实现非递归
void quick_Sort_NoR_Queue(int* arr, int size)
{
	Queue q;
	QueueInit(&q);
	if (size > 1)
	{
		QueuePush(&q, 0);
		QueuePush(&q, size - 1);
	}
	while (!QueueEmpty(&q))
	{
		int begin = QueueFront(&q);
		QueuePop(&q);
		int end = QueueFront(&q);
		QueuePop(&q);

		int keyPos = partion2(arr, begin, end);

		if (begin < keyPos - 1)
		{
			QueuePush(&q, begin);
			QueuePush(&q, keyPos - 1);
		}
		if (end > keyPos + 1)
		{
			QueuePush(&q, keyPos + 1);
			QueuePush(&q, end);
		}
	}
}

归并排序

归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有 序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
代码如下：

void merge(int* arr, int begin, int mid, int end, int* tmp)
{
	int begin1 = begin, end1 = mid, begin2 = mid + 1, end2 = end;
	int idx = begin;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (arr[begin1] <= arr[begin2])
			tmp[idx++] = arr[begin1++];
		else
			tmp[idx++] = arr[begin2++];
	}
	if (begin1 <= end1)
		memcpy(tmp + idx, arr + begin1, sizeof(int)* (end1 - begin1 + 1));
	if (begin2 <= end2)
		memcpy(tmp + idx, arr + begin2, sizeof(int)*(end2 - begin2 + 1));
	memcpy(arr + begin, tmp + begin, sizeof(int)* (end - begin + 1));
}

void merge_SortR(int* arr, int begin, int end, int* tmp)
{
	if (begin >= end)
		return;
	int mid = begin + (end - begin) / 2;

	merge_SortR(arr, begin, mid, tmp);
	merge_SortR(arr, mid + 1, end, tmp);

	merge(arr, begin, mid, end, tmp);
}

void merge_Sort(int* arr, int size)
{
	int* tmp = (int*)malloc(sizeof(int)* size);

	merge_SortR(arr, 0, size - 1, tmp);
	free(tmp);
}

特点：

1. 时间按复杂度：(N* Log₂N)
2. 空间复杂度：O(N)
3. 稳定性：稳定
4. 敏感性：不敏感

非递归实现：

void merge_Sort_NoR(int* arr, int size)
{
	int* tmp = (int*)malloc(sizeof(int)* size);
	int k = 1;
	while (k < size)
	{
		for (int i = 0; i < size; i++)
		{
			int begin = i;
			int mid = i + k + 1;
			if (mid >= size - 1)
				continue;

			int end = i + 2 * k - 1;
			if (end >= size)
				end = size - 1;

			merge(arr, begin, mid, end, tmp);
		}
		k *= 2;
	}
}

非比较排序

计数排序，统计相同元素出现次数，根据统计结果将序列回收到原有序列中，它适合小范围数据，若范围大，则空间复杂度较高。
代码如下：

void count_Sort(int* arr, int size)
{
	int min = arr[0], max = arr[0];
	for (int i = 0; i < size; i++)
	{
		if (arr[i] < min)
			min = arr[i];
		if (arr[i] > max)
			max = arr[i];
	}
	int range = max - min + 1;

	int* countArr = (int*)malloc(sizeof(int)* range);
	memset(countArr, 0, sizeof(int)* range);

	for (int i = 0; i < size; i++)
		countArr[arr[i] - min]++;

	int idx = 0;
	for (int i = 0; i < range; i++)
	{
		while (countArr[i]--)
			arr[idx++] = i + min;
	}
	free(countArr);
}

特点：

1. 时间复杂度：O(MAX(N，范围))
2. 空间复杂度：O(范围)
3. 稳定性：一般来说稳定
4. 敏感性：不敏感