让你搞轻松懂6大排序算法（插入、选择、交换三类排序）。

排序的概念

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

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

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

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

一、插入排序

1、直接插入排序

​ 直接插入排序是一种简单的插入排序法，其基本思想是：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。

单趟排序

插入排序的原理（博主自己的理解）：

何为插入排序？即我们需要将一个数据插入已经排序好的一段序列中。

那么我们如何在插入后依然保持有序呢？

**以数组为例：**待插入元素e1位于已排序好的序列后

接着，我们先用局部变量Tmp存储e1的值。我们假设e1=1.

接下来我们只需要与前面的数一个个进行比较即可，如果前面的数比tmp大，那么我们就将该数

往后挪一位。

之后依次比较，如果前面的数小于或者等于tmp，那么我们就跳出循环，或者当end<0时，结束该循环。此时我们只需要将tmp中的值赋给 下标为end+1的元素即可。

由此我们便完成了直接插入排序的单趟排序。

直接插入排序的代码实现：

下图为完整的直接插入排序的演示动图和其代码的实现：

void InsertSort(int* arr, int len)//插入排序
{
	for (int i = 0;i < len - 1;++i) {
		int end = i;
		int tmp = arr[end + 1];
		while (end >= 0) {
			if (arr[end] > tmp) {
				Swap(&arr[end], &arr[end + 1]);
				end--;
			}
			else {
				break;
			}
		}
		arr[end + 1] = tmp;
	}

}

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

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

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

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

4. 稳定性：稳定


#### 2、希尔排序（直接插入排序的优化）

希尔排序是对直接插入排序的优化，直接插入排序的时间复杂度在待排序数据有序时为O(N).

所以希尔排序有着两个步骤 **预排 和 直接插入排序**。

1、预排（让数据变得接近有序）
假定gap=5.
每个数都与后第gap个数比较，小的放前面，大的放后面.
通过进行这样一次排序，我们的数据就会比原来趋于有序，当gap越小时，我们的数据也就越有序，gap=1时，就是进行直接插入排序了。
​
2、直接插入排序

gap=1时，自然就是在进行直接插入排序了

```c

```c
```c
void ShellSort(int* arr, int len)   //希尔排序
{
	int gap = len;
	while (gap > 1) {
		gap = gap / 3 + 1;
		for (int i = 0;i < len - gap;++i) {
			int end = i;
			int tmp = arr[end + gap];

			while (end>=0) {
				if (arr[end] > tmp) {
					Swap(&arr[end], &arr[end + gap]);
					end -= gap;
				}
				else {
					break;
				}
			}
			arr[end + gap] = tmp;
		}
	}
}
...

希尔排序的特性总结：

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

2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。

3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，

4. 稳定性：不稳定

二、选择排序

1、直接选择排序

直接选择排序，就是每遍历一次，找到最大或者最小的值来放在对应的位置。很显然它的时间复杂度是

O（N^2）.

void SelectSort(int* arr, int len)   //优化版直接选择排序，一次选择两个数
{
	int begin = 0;
	int end = len-1;
	while (begin < end) {
	int min = begin;
		int max = begin;
	for (int i = begin+1;i < end+1;++i) {
			if (arr[min] > arr[i]) {
				min = i;
			}
			if (arr[max] <  arr[i]) {
				max = i;
			}
		}
	Swap(&arr[begin], &arr[min]);
	if (max == begin) {             //注意一下特殊情况即可，一轮只找一个的情况无需考虑
		max = min;
	}
	Swap(&arr[end], &arr[max]);
	begin++;
	end--;
	}

}

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

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

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

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

4. 稳定性：不稳定

2、堆排序

详情见上篇专门介绍堆和堆排序的博客

void AdjustDown(int* arr, int size, int root)  //向下调整为大堆的形式
{
	assert(arr);
	int parent = root;
	int MaxChild = 2 * parent + 1;
	while (MaxChild < size) {
		if (MaxChild + 1 < size && arr[MaxChild] < arr[MaxChild + 1]) {
			MaxChild++;
		}

		if (arr[MaxChild] > arr[parent]) {
			Swap(&arr[MaxChild], &arr[parent]);
			parent = MaxChild;
			MaxChild = 2 * parent + 1;
		}
		else {
			break;
		}

	}
}

void HeapSort(int* arr, int size) //升序
{
	assert(arr);
	//调整为大堆
	for (int i = (size - 2) / 2;i >= 0;--i){
	int root = i;
	AdjustDown(arr, size, i);
	}

	while (size > 1) {
		Swap(&arr[0], &arr[size - 1]);
		size--;
		AdjustDown(arr, size, 0);
	}
}

堆排序的特性总结：

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

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

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

4. 稳定性：不稳定

三、交换排序

1、冒泡排序

冒泡排序就想水中的泡泡一样，我们通过前后数据对比，不断的将大的数据往后放 ，

由此我们每遍历一次，最后一位就排好了，然后依次往前。

我们还可以进行点小小的优化，即若数据有序，我们就直接退出循环。

void BubbleSort(int* arr, int len)      //优化版冒泡排序，如待排数据本身有序则跳出循环
{
	for (int i = 0;i < len;++i) {
		int flag = 0;       
		for (int j = 0;j < len - i - 1;++j) {
			if (arr[j] > arr[j + 1]) {
				Swap(&arr[j], &arr[j + 1]);
				flag = 1;                     //通过flag判断是否该次循环是否发生过数据的交换
			}
		}
		if (flag == 0) {
			break;
		}
	}

}

冒泡排序的特性总结：

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

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

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

4. 稳定性：稳定

2、快速排序

递归实现

一、hoare法

int Part1Sort(int* arr, int left, int right)           //hoare版本
{
	int tmp = left;
	while (left < right) {
	while (left < right) {
			if (arr[right] < arr[tmp]) {
				break;
			}
			right--;
		}
		while (left < right) {
			if (arr[left] > arr[tmp]) {
				break;
			}
			left++;
		}
		if (left < right)
			Swap(&arr[left], &arr[right]);
		else {
			Swap(&arr[tmp], &arr[right]);
		}
	}
	return right;
}
void QuickSort(int* arr, int left, int right)   //递归实现
{
	if (left >= right) {
		return;
	}
	if (right - left <= 8) {                     //优化，最后三层递归直接使用插入排序
		InsertSort(arr + left, right - left + 1);
	}
	else {
	int flag = FindMidIndex(arr, left, right);     //三数取中
		Swap(&arr[left], &arr[flag]);
		
		int mid = Part1Sort(arr, left, right);
		QuickSort(arr, left, mid - 1);
		QuickSort(arr, mid + 1, right);
	}
	
}

二、挖坑法

int Part2Sort(int* arr, int left, int right)            //挖坑法
{
	int keyi = arr[left];
	int hole = left;
	while (left < right) {
		
		while (left < right) {
			if (arr[right] < keyi) {
				arr[hole] = arr[right];
				hole = right;
				break;
			}
			right--;
		}
		while (left < right) {
			if (arr[left] > keyi) {
				arr[hole] = arr[left];
				hole = left;
				break;
			}
			left++;
		}
	}
	arr[hole] = keyi;
	return hole;
}
void QuickSort(int* arr, int left, int right)   //递归实现
{
	if (left >= right) {
		return;
	}
	if (right - left <= 8) {                     //优化，最后三层递归直接使用插入排序
		InsertSort(arr + left, right - left + 1);
	}
	else {
	int flag = FindMidIndex(arr, left, right);     //三数取中
		Swap(&arr[left], &arr[flag]);
		
		int mid = Part2Sort(arr, left, right);
		QuickSort(arr, left, mid - 1);
		QuickSort(arr, mid + 1, right);
	}
	
}

三、前后指针法

int Part3Sort(int* arr, int left, int right)       //前后指针法
{
	int keyi = arr[left];
	int cur = left+1;
	int prev = left;
	while (cur <= right) {
		if (arr[cur] < keyi&& ++prev!=cur) {
			Swap(&arr[prev], &arr[cur]);
		}	
		cur++;
	}
	Swap(&arr[prev], &arr[left]);
	return prev;
}


void QuickSort(int* arr, int left, int right)   //递归实现
{
	if (left >= right) {
		return;
	}
	if (right - left <= 8) {                     //优化，最后三层递归直接使用插入排序
		InsertSort(arr + left, right - left + 1);
	}
	else {
	int flag = FindMidIndex(arr, left, right);     //三数取中
		Swap(&arr[left], &arr[flag]);
		
		int mid = Part3Sort(arr, left, right);
		QuickSort(arr, left, mid - 1);
		QuickSort(arr, mid + 1, right);
	}
	
}

非递归实现

如何使用非递归的形式实现快排？

在这里，我们需要利用栈来帮助我们实现。

#define _CRT_SECURE_NO_WARNINGS
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int STDataType;
typedef struct Stack
{
	STDataType* _a;
	int top;
	int capacity;
}Stack;

int StackEmpty(Stack* ps);
void StackInit(Stack* ps);  //初始化栈
void StackPush(Stack* ps, STDataType va);  //压栈
void StackPop(Stack* ps);  //出栈
int StackSize(Stack* ps); // 栈中有效元素个数
STDataType StackTop(Stack* ps);  //获取栈顶元素
int StackSize(Stack* ps); // 栈中有效元素个数
void StackDestory(Stack* ps);  //销毁栈

#include "stack.h"
void StackInit(Stack* ps)  //初始化栈
{
	assert(ps);
	ps->_a = NULL;
	ps->capacity = 0;
	ps->top = -1;
}

void StackPush(Stack* ps,STDataType val)  //压栈
{
	assert(ps);
	if (ps->top+1 == ps->capacity) {
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(ps->_a, newcapacity * sizeof(STDataType));
		if (tmp == NULL) {
			perror("malloc");
			exit(-1);
		}
		ps->_a = tmp;
		ps->capacity = newcapacity;
	}
	ps->_a[++ps->top] = val;
}

int StackEmpty(Stack* ps) // 检查栈是否为空
{
	if (ps->top >= 0) {
		return 0;
	}
	return 1;
}

void StackPop(Stack* ps)  //出栈
{
	assert(ps);
	if(!StackEmpty(ps))
	ps->top--;
}

STDataType StackTop(Stack* ps)  //获取栈顶元素
{
	assert(ps);
	if(!StackEmpty(ps))
	return ps->_a[ps->top];
}

int StackSize(Stack* ps) // 栈中有效元素个数
{
	assert(ps);
	return ps->top + 1;
}

void StackDestory(Stack* ps)  //销毁栈
{
	assert(ps);
	free(ps->_a);
	ps->_a = NULL;
	ps->capacity = 0;
	ps->top = -1;
}


void QuickSortNonR(int* arr, int left, int right)//非递归实现快排
{
	Stack st;
	StackInit(&st);
	StackPush(&st,right);
	StackPush(&st, left);
	while (!StackEmpty(&st)) {
		int begin = StackTop(&st);
		StackPop(&st);
		int end = StackTop(&st);
		StackPop(&st);
		if (begin >= end) {
			continue;
		}
		int keyi = Part2Sort(arr, begin, end);

		StackPush(&st, end);
		StackPush(&st, keyi+1);

		StackPush(&st, keyi-1);
		StackPush(&st, begin);
	}
	StackDestory(&st);
}

快速排序的特性总结：

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

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

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

4. 稳定性：不稳定

四、归并排序

归并排序之后会添上

五、总结

这篇博客主要介绍了7大排序，希望大家都能从中有所收获，如果觉得不错的话希望不要吝啬手中的赞哦！