数据结构——排序算法分析与总结

一、插入排序

1、直接插入排序

核心思想:把后一个数插入到前面的有序区间,使得整体有序

思路:先取出数组中第一个值,然后再用tmp逐渐取出数组后面的值,与前面的值进行比较,假如我们进行的是升序排序,那么此时前面排序好的数组中,最后一个值最大,如果tmp大于它,就插入后面,否则end -- 往前走,进行比较,(注意:此时数组也要往后赋值),找到比它小的元素,则插在那个元素后面即可如果直到为0的时候,仍然小于,则把它放在下标为0的位置。

最坏情况(数组元素逆序):每次插入,元素都要往后移动

  • 移动次数:1 +2 +3…+ n => 等差数列 ==>O(N^2)

最好情况:(接近有序或者有序),基本不用移动数据 ->O(N)、

稳定性:稳定 

  • 将x插入到[0,end]的有序区间的时候,当区间元素和x的值相同的时候,是将x插入到该区间元素后面,二者的相对顺序不变

图文演示:假如a[ 5 ] = {3 , 2, 1, 4, 5}

代码演示:

//插排二
//时间复杂度 O(N^2)
// 最坏情况 :逆序
// 最好情况: 顺序或者接近有序 O(N)
void InsertSort(int* a, int n) //n表示数组有多少个元素
{
	for (int i = 0; i < n - 1; i++) //只需要走n-1个元素即可,防止越界
	{
		int end = i; //后面下标
		int tmp = a[end + 1]; //存下后面的值
		while (end >= 0) //与前面下标元素进行比较
		{
			if (a[end] > tmp) { //待插入元素小于前面元素,则数组往后走一位
				a[end + 1] = a[end];
				end--;
			}
			else break; //找到比待插入元素小的
		}
		a[end + 1] = tmp;  //插入当前位置
	}
}

2、希尔排序

核心思想

1.先选定一个gap,把待排序数据分组,所有距离为gap分在同一组内,并对每一组内的记录进行排序。

预排序:目的是让数组更接近于有序,这样子后续gap为1进行直接插入排序,效率就是O(N)
2.然后取重复上述分组和排序的工作,当到达gap=1时,就是直接插入排序,整体就有序了

  • gap越大:预排序越快,预排序后越不接近有序
  • gap越小:预排序越慢,预排序后越接近有序。
  • 数据是逆序的时候,预排序完成就接近有序,此时预排序的效果最好。

图文演示:

时间复杂度:O(N^1.3)

稳定性:不稳定

  • 相同的值,预排序时可能分到不同的组里面,导致相对顺序发生改变

写法1:多组进行排序

//多组一起进行预排序
void Shellsort1(int* a, int n)
{
	//int gap = 1; //如果gap为1 则为插入排序

	//把间隔为gap的数组同时排
	int gap = n;
	while (gap > 1)
	{
		gap /= 2; //gap>1 都是预排序 接近有序
		//gap=gap/3+1;
		for (int i = 0; i < n - gap; i++)//注意:i的范围! 否则end+gap会越界
		{
			int end = i;//end的范围:[0,n- gap -1]
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (a[end] > tmp)
				{
					a[end + gap] = a[end];//把a[end]往后移动,以gap为间隔的为一组,所以移动到a[end+gap]位置
					end -= gap;//下一轮循环,以gap为间隔的为一组,前一个数(end-gap位置对应的值)和 tmp 比较
				}
				else break;
			}
			a[end + gap] = tmp;
		}
	}
}

写法2:每一组分别进行预排序

每一组都进行预排序

  • 一次只排序间隔为gap的元素(同组元素),一共有gap组,所以要循环gap次

需要变动的位置:循环gap次,每次处理一组!

  • 每一组的起始位置是当前组的组号,然后每次变化范围:  gap
//多组一起进行预排序
void Shellsort2(int* a, int n)
{
	//int gap = 1; //如果gap为1 则为插入排序

	//把间隔为gap的数组同时排
	int gap = n;
	while (gap > 1)
	{
		//目的是为了保证最后能让gap为1,进行直接插入排序
		gap /= 2; //gap>1 都是预排序 接近有序
		//gap=gap/3+1;
		for (int j = 0; j < gap; j++) {
			for (int i = j; i < n - gap; i += gap)//注意:i的初始值!!和变动范围 i+=gap
			{
				int end = i;//end的范围:[0,n- gap -1]
				int tmp = a[end + gap];//下一轮循环,以gap为间隔的为一组,前一个数(end-gap位置对应的值)和 tmp 比较
				while (end >= 0)
				{
					if (a[end] > tmp)
					{
						a[end + gap] = a[end];
						end -= gap;
					}
					else break;
				}
				a[end + gap] = tmp;//以gap为间隔的为一组,把tmp放在end + gap位置 
			}
		}
	}
}

二、选择排序

1、直接选择排序

核心思想:第一次从R[0]~R[n-1]中选取最小值,与R[0]交换,第二次从R[1]~R[n-1]中选取最小值,与R[1]交换,....,第i次从R[i-1]~R[n-1]中选取最小值,与R[i-1]交换,.....,第n-1次从R[n-2]~R[n-1]中选取最小值,与R[n-2]交换,总共通过n-1次,得到一个按排序码从小到大排列的有序序列。

时间复杂度:遍历一遍才能选出一个数或者两个数,无论什么情况都是O(N^2)。

稳定性:不稳定

  • 在区间当中找到最大和最小的数和区间左右端点位置的值交换,可能会导致两个相同的值相对顺序发生变化

图文演示:

代码演示:

方法一:每次选择一个数,比如一个移动范围内的最小值

//直接选择排序 
//写法1:每次选择一个数
void SelectSort1(int* a, int n)
{
	int begin = 0;
	while (begin < n - 1) {//当区间只有一个元素就不需要选了所以循环条件为:end > 0
		int mini = begin;
		for (int i =  begin + 1; i < n; i++) {// 在[begin, n-1]中选取最小值
			if (a[mini] > a[i]) mini = i;
		}
		swap(a[begin], a[mini]);
		begin++;
	}
}

方法2:每次选择两个数

思路:每次从要排序的区间当中找到最大和最小的数,如果是排序,那么把他区间的最大的数和区间右端点对应值交换,把区间中最小的数和区间左端点对应值交换,然后缩小区间重复上述步骤,直到区间只有一个数。

//写法2:每次选择两个数
void SelectSort2(int* a, int n)
{
	int begin = 0, end = n - 1;
	
	while (begin <end)
	{
		int mini = begin, maxi = end;
		for (int i = begin; i <= end; i++)
		{
			if (a[i] < a[mini]) mini = i; //找出最小的值下标
			if (a[i] > a[maxi]) maxi = i; //找出最大的值下标
		}
		
		swap(a[begin], a[mini]);//最小值放到begin位置

		//注意:如果begin和maxi一样,即begin就是最大值的位置
		//因为下面一步begin位置和值已经和mini位置交换了,所以就导致了mini位置放的才是最大值了
		//所以需要特判一下,如果begin和maxi相同,那么经过上面一步交换之后,mini位置放的才是最大值

		if (begin == maxi) maxi = mini;//加以优化,避免最大的数出现在第一个
		
		swap(a[end], a[maxi]);//最大值放到end位置
		begin++, end--; //缩小区间
	}
}

2、堆排序

核心思想

     1.首先需要先建堆,只需要从最后一个叶子结点的父节点开始,在数组当中从后往前去向下调整即可共n个元素。

  • 共n个元素,最后一个结点的下标为: n -1
  • 它的父亲结点的下标为:parent = (child - 1)/2 = (n - 1- 1)/2

        2.建好堆之后,将堆顶数据与堆的最后一个数据交换,然后对根位置进行一次堆的向下调整,但是调整时被交换到最后的那个数不参与向下调整,然后缩小堆中有效数据个数,剩下的元素进行向下调整,其余数又成一个大堆…重复上述步骤,直到堆中只剩下一个元素。

       注意:

            a、排升序建大堆

            b、排降序建小堆

对于N个元素建堆,我们用筛选法建堆,从 N/2 (即最后一个非叶子节点)的元素开始建堆

时间复杂度分析:无论哪种方法建堆:都是O(N*logN)

  • 建堆的时间复杂度 + 调堆的时间复杂度 N*logN

稳定性:不稳定

  • 在调堆的时候,可能会导致相同元素的相对顺序改变

图文演示:

代码演示:

//排升序最后是建大堆
void AdjustDwon(int* a, int n, int root)
{
	int parent = root;
	int child = parent * 2 + 1; //默认是左孩子,右孩子比左孩子大1
	while (child < n)
	{
		//1、选出左右孩子中大的那一个
		if (child+1<n && a[child + 1] > a[child]) //建一个大堆
		{
			child += 1;
		}
		//2、然后再与父亲比较,若比父亲大就发生交换
		if (a[child] > a[parent])//让父亲永远大于儿子
		{
			Swap(&a[child], &a[parent]);
			parent = child; //交换下标
			child = parent * 2 + 1;
		}
		else break; //记得跳出循环
	}
}

//第一个和最后一个交换,把它不看作堆里面,前n-1个数向下调整,选出次大的数,再跟倒数第二个位置交换
void HeapSort(int* a, int n)
{
	//把数组建成大堆
	for (int i = (n-1-1) / 2; i >= 0; i--) //筛选法选出最后一个非叶子节点
	{
		AdjustDwon(a, n, i); //建大根堆
	}
	int end = n - 1;
	while (end > 0)//开始向下调整
	{
		Swap(&a[0], &a[end]);
		AdjustDwon(a, end, 0);
		--end;
	}
}

 举例:将整数数组(7-6-3-5-4-1-2)按照堆排序的方式原地进行升序排列,请问在整个排序过程中,数组的顺序是_____。(6-5-3-2-4-1-7)


三、交换排序

1、冒泡排序

核心思想:重复地走访过要排序的元素列,依次比较两个相邻的元素,如果顺序(如从大到小、首字母从Z到A)错误就把他们交换过来。走访元素的工作是重复地进行,直到没有相邻元素需要交换,也就是说该元素列已经排序完成。

  • n个元素,只需排序n-1次,就可以让n个数有序

优化:如果提前有序了(某一趟冒泡当中没有元素交换),就不需要再冒泡了。

时间复杂度:

  • 最坏情况:第一轮:N个数比较交换,第二轮:N-1个数比较交换… ,此时相当于是等差数列,复杂度为O(N^2)
  • 最好情况:数组接近有序/有序,某一趟冒泡当中没有元素交换直接结束,O(N)

稳定性:稳定

  • 相邻元素进行比较,相同的元素之间不进行交换
void BubbleSort(int* a, int n)
{
//每一趟可以确定一个元素到准确位置,n个元素只需要进行n-1趟
	for (int i = 0; i < n - 1; i++) 
	{
		bool flag = 0;
//每一趟都可以少比较一个已经确定好的数
		for (int j = 0; j < n - 1 - i; j++)
		{
			if (a[j] > a[j + 1]) {
				swap(a[j], a[j + 1]);
				flag = 1;
			}
		}
		if (flag == 0) break; //说明没有进行交换,此时已经有序,跳出即可
	}
}

 2、快速排序

快速排序是基于 分治法 的一个排序算法。

核心思想:取待排序区间上的某一个元素作为基准值,根据处理方法,将待排序区间上的元素划分为:左区间的元素小于基准值,右区间的元素大于基准值,然后对左右区间重复这个过程,直到所有元素都排列在相应位置上为止

代码演示:

最简便模板:(记住这个即可)

void QuickSort(int q[], int l, int r) //先分治再递归
{
	if (l >= r) return; //递归截止条件

	int x = q[l + r >> 1]; // 但是一般选择第一个或者最后一个
	int i = l - 1, j = r + 1; //注意:l-1 和 r + 1
	while (i < j)//x左边都是小于x的,右边都是大于x的 
	{
		do i++; while (q[i] < x);
		do j--; while (q[j] > x);
		//假设上面截止时且满足i < j,此时a[i] >= x, a[j] <= x 
		if (i < j) swap(q[i], q[j]);
	}
	QuickSort(q, l, j);
	QuickSort(q, j + 1, r);
}

比如快速排序的第一趟结果:

比如关键字(20,15,14,18,21,36,40,10)以20为基准进行排序。
第一步,先从后往前找出小于基准数20的数,并与基准数20交换得:10,15,14,18,21,36,40,20)。
第二步,再从前往后找出大于基准数20的数,并与基准数20交换得:10,15,14,18,20,36,40,21)。
再一次执行第一步与第二步,直到最后基准数左边的序列都小于基准数,基准数右边的序列都大于基准数。
所得结果:(10,15,14,18,20,36,40,21)。为第一趟排序的结果。


四、归并排序

核心思想:根据左右区间的值,计算一个中间值mid,先让[left,mid] [mid+1,right]两个区间有序, 然后这两个有序区间进行归并 (归并到临时数组),将临时数组的内容拷贝回去。

时间复杂度:O(N*logN)

空间复杂度:O(N)

稳定性:稳定

  • 归并的时候,相同的值,先拷贝左区间的值,再拷贝右区间的

归并操作,也叫归并算法,指的是将两个顺序序列合并成一个顺序序列的方法。

如 设有数列{6,202,100,301,38,8,1}

初始状态:6,202,100,301,38,8,1。

第一次归并后:{6,202},{100,301},{8,38},{1},比较次数:3;

第二次归并后:{6,100,202,301},{1,8,38},比较次数:4;

第三次归并后:{1,6,8,38,100,202,301},比较次数:4;

总的比较次数为:3+4+4=11;

逆序数为14;(因此我们可以用 归并算法 来计算逆序数)

代码演示:

const int N = 10010;
int tmp[N];
void merge_sort(int q[], int l, int r) //先归并再分治
{
	if (l >= r) return; //递归截止
	int mid = l + r >> 1; //记录中间值
	merge_sort(q, l, mid);   
	merge_sort(q, mid + 1, r);
	
	int k = 0, i = l, j = mid + 1; //k表示tmp储存的元素数量

	while (i<=mid && j<=r) //注意下面都是<=,保证了它的稳定性
	{
		if (q[i] <= q[j])tmp[k++] = q[i++]; 
		else  tmp[k++] = q[j++];
	}
 
	//防止分布不均
	while (i <= mid) tmp[k++] = q[i++];
	while (j <= r) tmp[k++] = q[j++]; 
	//注意i的范围是[l,r]		
	for (i = l, j = 0; i <= r; i++,j++) q[i] = tmp[j]; //拷贝

}


五、计数排序——鸽巢原理

核心思想:统计相同元素出现次数,根据统计的结果将序列写回到原来的序列中

统计每个数据出现的次数 count[a[i]]++
适合数据集中的数组进行排序
  时间复杂度O(N+range)
  空间复杂度 O(range)

稳定性:不稳定

  • 计数到count数组中,每个元素已经没有顺序了
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;  //比如109 100 实际有10个值
	int* count = (int*)malloc(sizeof(int) * range);
	//数组元素进行映射。此时x元素映射在x - min位置
	memset(count, 0, sizeof(int) * range);
	for (int i = 0; i < n; ++i)
	{
		count[a[i] - min]++;
	}
	//将count数组的内容映射回去原数组,此时对应的值为i + min
	int j = 0;
	for (int i = 0; i < range; i++)
	{
		while (count[i]--)
		{
			a[j++] = i + min;
		}
	}
	free(count);
}

上述八大排序的稳定性以及复杂度

注意:

1、对于快速排序:如果加了三数取中 + 三路归并 最坏就不是O(N^2)

2、为了绝对的速度选快排,为了省空间选堆排,为了稳定性选归并

3、时间复杂度:O(N*logN),额外空间复杂度低于O(N),且稳定的基于比较的排序是不存在的

最后下面我们再提一个排序


九、基数排序

代码演示:

bool check(int* arr, int l, int r)
{
	for (int i = l + 1; i < r; i++)
	{
		if (arr[i] < arr[i - 1]) return true;
	}
	return false;
}

// 扩大范围 从 0 - 99为基数
void radix_sort(int* arr, int l, int r)
{
#define K 65536
	int* cnt = (int*)malloc(sizeof(int) * K);
	int* temp = (int*)malloc(sizeof(int) * (r - l));

	// round 1
	memset(cnt, 0, sizeof(int) * K);
	for (int i = l; i < r; i++) cnt[arr[i] % K] += 1; //求前缀和
	for (int i = 1; i < K; i++) cnt[i] += cnt[i - 1];
	for (int i = r - 1; i >= l; i--) temp[--cnt[arr[i] % K]] = arr[i]; //记录当前数字应该存放的位置
	memcpy(arr + l, temp, sizeof(int) * (r - l));

	// round 2
	memset(cnt, 0, sizeof(int) * K);
	for (int i = l; i < r; i++) cnt[arr[i] / K] += 1; //求前缀和
	for (int i = 1; i < K; i++) cnt[i] += cnt[i - 1];
	for (int i = r - 1; i >= l; i--) temp[--cnt[arr[i] / K]] = arr[i]; //记录当前数字应该存放的位置
	memcpy(arr + l, temp, sizeof(int) * (r - l));

}

相关推荐

  1. 数据结构算法>效率分析专项总结

    2024-05-02 19:16:03       31 阅读
  2. 数据结构算法-排序算法

    2024-05-02 19:16:03       17 阅读

最近更新

  1. TCP协议是安全的吗?

    2024-05-02 19:16:03       18 阅读
  2. 阿里云服务器执行yum,一直下载docker-ce-stable失败

    2024-05-02 19:16:03       19 阅读
  3. 【Python教程】压缩PDF文件大小

    2024-05-02 19:16:03       19 阅读
  4. 通过文章id递归查询所有评论(xml)

    2024-05-02 19:16:03       20 阅读

热门阅读

  1. 【高并发解决思路】

    2024-05-02 19:16:03       16 阅读
  2. 关于开源软件的影响力的探讨

    2024-05-02 19:16:03       17 阅读
  3. HTML_CSS学习:CSSLearning

    2024-05-02 19:16:03       18 阅读
  4. JPA 如何修改 联表查询返回的Map

    2024-05-02 19:16:03       16 阅读
  5. 4月26日划分字母区间+合并区间

    2024-05-02 19:16:03       14 阅读