几种排序算法详解以及比较（8种）_多种排序算算法对比研究

目录

1. 比较类排序

1.1 插入类排序

1.1.1 直接插入排序

1.1.2 希尔排序 对插入排序的优化

1.2 选择类排序

1.2.1 选择排序

1.2.2 堆排序

1.3 交换类排序

1.3.1 冒泡排序

1.3.2 快速排序

1.4 归并排序

2. 非比较类排序

2.1 计数排序

---

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

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

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

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

1. 比较类排序

1.1 插入类排序

1.1.1 直接插入排序

void InsertSort(int* a, int n)
{
	for (int i = 0; i < n-1; i++)
	{
		//大问题分解成小问题
		//先计算单趟，插入排序一个元素
		//再加上外层循环，对所有元素插入排序；
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (tmp < a[end])
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				//a[end + 1] = tmp;
				break;
			}
		}
		a[end + 1] = tmp;
	}
}

直接插入排序特性总结：
时间复杂度分析：
最好情况：数组已经排好序，时间复杂度O ( n ) 
最坏情况：逆序，每个元素都要与前面所有元素都比较一次，等差数列求和。时间复杂度为O(n2)
对于插入排序来说，接近有序的序列排序是比较快的。
空间复杂度O ( 1 ) O(1)O(1)
 

1.1.2 希尔排序 对插入排序的优化

 1.预排序（间隔为gap的元素分成一组，对每一组进行插入排序，一共gap个组

• gap越大，大的数和小的数越快挪到对应的位置上去，但是越不接近有序
• gap越小，大的数和小的数越慢挪到对应的位置上去，但是越接近有序
• gap为1的时候，就是直接插入排序 ，所以可以对gap来一个循环

2.再进行插入排序

void ShellSort(int* a, int n)
{
	int gap = n;
	// gap > 1的时候，预排序
	// gap == 1的时候，直接插入排序  O(N)
	while (gap > 1)
	{
		gap =( gap/3+1);//不能让gap为0，最后一次gap应该为1；
		for (int 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
				{
					//a[end + 1] = tmp;
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}
}

1.2 选择类排序

1.2.1 选择排序

//选择排序
void SelectSort(int* a, int n)
{
	for (int j = 0; j < n; j++)
	{
		int min = j;
		for (int i = j+1; i < n; i++)
		{
			if (a[i] < a[min])
			{
				min = i;
			}
		}
		Swap(&a[j], &a[min]);
	}
}//可以对选择排序优化，一次遍历同时选出最大和最小两个数

1.2.2 堆排序

 

堆排序：物理上操作的是一个数组，逻辑上把他看成一个heap。
排升序，要建大堆（建小堆只能找到最小的数，接下来又得建堆找次小的，效率太低）
建大堆的话，把最大的数换到最后，向下调整一次选出次大的数，再往后放

//向下调整算法
void AdjustDwon(int* a, int n, int root)
{
	int parent = root;
	int child = 2 * parent + 1;
	while (child < n)
	{
		if (child + 1 < n && a[child + 1] > a[child])//先检查越界再访问
			child++;
		if (a[child] > a[parent]){
			Swap(&a[child], &a[parent]);
			parent = child;
			child = 2 * parent + 1;
		}
		else{
			break;}
	}
}
void HeapSort(int* a, int n)
{
	//1. 首先建堆（大堆，升序），即物理上把数组形成大堆的样子
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)//从最后一次不是叶子节点的元素开始调整
	{
		AdjustDwon(a, n, i);
	}//到这里完成建堆，数组a在逻辑上是一个堆
 
	//2. 将堆顶元素（最大元素）换到最后，完成升序
	//在物理上就是将首元素换到最后，再让堆（物理上的数组）的长度-1，并向下调整一次生成新的大堆
	//注意，这个新的堆在物理上比上一个堆元素少1了，再把这个堆顶（数组首元素）即次大的元素换到最后，循环最后形成升序。
	int end = n - 1;
	while (end >= 1)
	{
		Swap(&a[0], &a[end]);
		AdjustDwon(a, end, 0);
		end--;
	}
}

1.3 交换类排序

1.3.1 冒泡排序

void Swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}
void BubbleSort(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		int flag = 0; //这里是代码优化
		for (int j = 0; j < n - i - 1; j++)
		{
			if (a[j] > a[j + 1])
			{
				flag = 1;
				Swap(&a[j], &a[j + 1]);
			}
		}
		if (flag == 0)
			break;
	}
}

flag用来优化，所以我们定义一个flag，当某一趟排序没有发生交换时，就说明数组已经有序，然后跳出循环。

1.3.2 快速排序

快排的原生函数为：

• c中为qsort：需要4个参数，qsort(排序首地址，排序长度，排序元素长度，cmp)
• c++中为sort（sort是qsort的优化）：2/3个参数，sort(排序首地址，排序尾地址，cmp)（2个参数就是不写cmp，这样默认是升序排列）

下面对快排进行模拟实现：

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

• 1. hoare版本
• 2. 挖坑法
• 3. 前后指针版本

快速排序的优化：

• 1. 三数取中法选key
• 2. 递归到小的子区间时，可以考虑使用插入排序

//快速排序：递归的思想
//优化方法（1）三数取中（选三个数，取中间大的数）
int GetMidIndex(int* a, int left, int right)
{
	int mid = (left + right) >> 1;//移位运算，相当于除以2（(left + right) / 2）
	// left  mid  right
	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;
	}
}
 
//单趟排序方法（1）hoare版本 -- 左右指针法
int PartSort1(int* a, int left, int right)
{
	int midIndex = GetMidIndex(a, left, right);//加入优化，三数取中
	Swap(&a[left], &a[midIndex]);
	int key = left;
 
	while (left < right)
	{
		//right找小的
		while (left < right && a[right] >= a[key])//加一个判断，不然会越界
			right--;
 
		//left找大的
		while (left < right && a[left] <= a[key])
			left++;
		Swap(&a[left], &a[right]);
	}
	Swap(&a[left], &a[key]);
	return left;
}
//单趟排序方法（2）挖坑法
//可以画图理解
int PartSort2(int* a, int left, int right)
{
	int midIndex = GetMidIndex(a, left, right);//加入优化，三数取中
	Swap(&a[left], &a[midIndex]);
	int key = left;
 
	while (left < right)
	{
		// right找小
		while (left < right && a[right] >= a[key])
		{
			--right;
		}
		// 找到之后，放到左边的坑位中,右边就形成新的坑
		a[left] = a[right];
		// left找大
		while (left < right && a[left] <= a[key])
		{
			++left;
		}
		// 找到之后放到右边的坑位中，左边就形成新的坑
		a[right] = a[left];
	}
	//这里left=right，是一个坑位
	a[left] = a[key];
	return left;
}
 
//单趟排序方法（3）前后指针法
int PartSort3(int* a, int left, int right)
{
	
	int midIndex = GetMidIndex(a, left, right);//加入优化，三数取中
	Swap(&a[left], &a[midIndex]);
	int key = left;
	int prev = left;
	int cur = left + 1;
	while (cur <= right)
	{
		//while (cur <= right && a[cur] >= a[key])
		//{
		//	cur++;
		//}
		//if (cur > right)//不要忘记这一步
		//	break;
		//Swap(&a[++prev], &a[cur]);
		//cur++;
		//或者换成下面
		if (a[cur] < a[key] && ++prev != cur)
		{
			Swap(&a[cur], &a[prev]);
		}
		++cur;
	}
	Swap(&a[key], &a[prev]);
	return prev;
}
 
//快排的时间复杂度：最好为每次的key都二分，为O(N*logN)
//最坏的情况为数组有序时，O(N^2)
//影响快排效率最大的是key，越接近中位数二分，效率越高
//针对性优化：
//优化方法（1）三数取中（选三个数，取中间大的数）（优化效果好）
//优化方法（2）小区间排序优化（效果一般）
void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
		return;
 
	int keyi = PartSort3(a, begin, end);//单趟排序之后找到key的位置
 
	//下面递归左右两个区间，[begin, keyi-1],[keyi+1, end];
	QuickSort(a, begin, keyi-1);
	QuickSort(a, keyi+1, end);
}

1.4 归并排序

 这显然也是可以分治递归实现。

//归并排序
//时间复杂度，O(N*logN)，每一层归并都是N个，一共logN层
//空间复杂度，O(N)
void _Merge(int* a, int* tmp, int left1, int right1, int left2, int right2)
{
	int begin1 = left1, end1 = right1;
	int begin2 = left2, end2 = right2;
	int i = left1;//这里要创建新变量，不能直接用
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] < a[begin2])
			tmp[i++] = a[begin1++];
		else
			tmp[i++] = a[begin2++];
	}
	while (begin1 <= end1)
		tmp[i++] = a[begin1++];
 
	while (begin2 <= end2)
		tmp[i++] = a[begin2++];
 
	// 归并完成以后，拷贝回到原数组
	for (int i = left1; i <= right2; i++)
	{
		a[i] = tmp[i];
	}
}
 
void _MergeSort(int* a, int left, int right, int* tmp)
{
	if (left >= right)
		return;
 
	int mid = (left + right) >> 1;
	
	//将左区间和右区间依次迭代到有序
	_MergeSort(a, left, mid, tmp);
	_MergeSort(a, mid + 1, right, tmp);
 
	//下面对左区间、右区间进行归并
	//按照尾插的思路
	_Merge(a, tmp, left, mid, mid + 2, right);
}
 
void MergeSort(int* a, int n)
{
	//用来存放归并时候的临时数组
	int tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		exit(-1);
	}
 
	_MergeSort(a, 0, n - 1, tmp);
	free(tmp);
}

拓展：
内排序和外排序
数量很大时候，要将外存中的数据分割成多个数据在内存中排序
排好的多个数据放到文件中，在从文件中拿数据进行归并
 

2. 非比较类排序

2.1 计数排序

//计数排序
//绝对映射、相对映射
//时间复杂度为O(N+range)
//适合，一组数据范围比较集中的数，但是只适合整数
//空间复杂度O(range)
void CountSort(int* a, int n)
{
	int max = a[0], min = a[0];
	for (int i = 0; i < n; i++)
	{
		if (a[i] > max)
			max = a[i];
		if (a[i] < min)
			min = a[i];
	}//加这个是为了相对映射
 
	//统计每个元素的个数
	int range = max - min + 1;
	int* count =(int*)malloc(sizeof(int) * range);
	memset(count, 0, sizeof(int) * range);
	for (int i = 0; i < n; i++)
	{
		count[a[i] - min]++;
	}
	
	//下面对a进行排序
	int j = 0;
	for (int i = 0; i < range; i++){
		while (count[i]--){
			a[j++] = i + min; }
	}
 
	free(count);
	count = NULL;
}