[数据结构]排序算法

目录

常用排序算法的实现::

                                        1.排序的概念及其运用

                                        2.插入排序

                                        3.希尔排序

                                        4.选择排序

                                        5.冒泡排序

                                        6.堆排序

                                        7.快速排序

                                        8.归并排序

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

                                       10.排序选择题练习


常用排序算法的实现::

1.排序的概念及其运用

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

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

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

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

 

测试排序的性能对比:

//测试排序的性能对比
void TestOP()
{
	srand(time(0));
	const int N = 100000;
	int* a1 = (int*)malloc(sizeof(int) * N);
	int* a2 = (int*)malloc(sizeof(int) * N);
	int* a3 = (int*)malloc(sizeof(int) * N);
	int* a4 = (int*)malloc(sizeof(int) * N);
	int* a5 = (int*)malloc(sizeof(int) * N);
	int* a6 = (int*)malloc(sizeof(int) * N);
	for (int i = 0; i < N; ++i)
	{
		a1[i] = rand();
		a2[i] = a1[i];
		a3[i] = a1[i];
		a4[i] = a1[i];
		a5[i] = a1[i];
		a6[i] = a1[i];
	}
	int begin1 = clock();
	InsertSort(a1, N);
	int end1 = clock();

	int begin2 = clock();
	ShellSort(a2, N);
	int end2 = clock();

	int begin3 = clock();
	SelectSort(a3, N);
	int end3 = clock();

	int begin4 = clock();
	HeapSort(a4, N);
	int end4 = clock();

	int begin5 = clock();
	QuickSort(a5, 0, N - 1);
	int end5 = clock();

	int begin6 = clock();
	MergeSort(a6, N);
	int end6 = clock();

	printf("InsertSort:%d\n", end1 - begin1);
	printf("ShellSort:%d\n", end2 - begin2);
	printf("SelectSort:%d\n", end3 - begin3);
	printf("HeapSort:%d\n", end4 - begin4);
	printf("QuickSort:%d\n", end5 - begin5);
	printf("MergeSort:%d\n", end6 - begin6);

	free(a1);
	free(a2);
	free(a3);
	free(a4);
	free(a5);
	free(a6);
}

2.插入排序

插入排序基本思想: 

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

实际中我们玩扑克牌时,就用了插入排序的思想:

当插入第 i(i>=1) 个元素时,前面的 array[0],array[1],…,array[i-1] 已经排好序,此时用 array[i] 的排序码与array[i-1],array[i-2],…的排序码顺序进行比较,找到插入位置即将 array[i] 插入,原来位置上的元素顺序后移。 
插入排序的特性总结:
1.元素集合越接近有序,插入排序算法的时间效率越高
2.时间复杂度:O(N^2)
3.空间复杂度:O(1)
4.稳定性:稳定
代码实现:
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 (a[end] > tmp)
			{
				a[end + 1] = a[end];
				--end;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
}

3.希尔排序(缩小增量排序)

希尔排序的基本思想:

希尔排序又称缩小增量法,希尔排序的基本思想是:先选定一个整数,把待排序文件中所有记录分成各组,所有距离为gap的记录分在同一组内,并对每一组内的记录进行排序,然后重复上述分组和排序的工作。当达到gap=1时,所有记录在同一组内已排好序。

希尔排序的特性总结:

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

2.当gap>1时都是预排序,目的是让数组更接近有序。当gap==1时,数组已经接近有序了,这样就会很快,整体而言,可以达到优化的效果。

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

《数据结构(C语言版)--- 严蔚敏

 《数据结构-用面相对象方法与C++描述》--- 殷人昆

注:我们的gap是按照Knuth提出的方式取值的,而且Knuth进行了大量的实验统计,我们暂时就按照:O(n^1.25)到O(1.6*n^1.25)来算。

4.稳定性:不稳定

代码实现:

//希尔排序(缩小增量排序)
//希尔排序又称缩小增量法 希尔排序的基本思想是:先选定一个整数,把待排序文件中所有
//记录分成n个组 所有距离为的记录分在同一个组 并对每一组内的记录进行排序,然后取重复上述分组
//和排序的工作,当达到1时,所有记录在统一组内排好序
//希尔排序的时间复杂度为O(N^1.3) 数据量特别大时略逊于N*logN
void ShellSort(int* a, int n)
{
	//gap > 1预排序 gap == 1直接插入排序
	int gap = n;
	while (gap > 1)
	{
		//gap = gap / 2;
		gap = gap / 3 + 1;
		for (int j = 0; j < gap; ++j)
		{
			for (int i = j; i < n - gap; i += gap)
			{
				//[0,end] 插入 end+gap [0,end+gap]有序——间隔为gap的数据
				int end = i;
				int tmp = a[end + gap];
				while (end >= 0)
				{
					if (a[end] > tmp)
					{
						a[end + gap] = a[end];
						end -= gap;
					}
					else
					{
						break;
					}
				}
				a[end + gap] = tmp;
			}
		}
	}
}

4.选择排序

选择排序的基本思想:

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

在元素集合array[i]—array[n-1]中选择关键码最大(小)的数据元素,若它不是这组元素中的最后一个(第一个)元素,则将它与这组元素中的最后一个(第一个)元素互换,在剩余的array[i]—array[n-2](array[i+1]—array[n-1])集合中,重复上述步骤,直到集合剩余一个元素。

选择排序的特性总结:

1.选择排序的代码非常好理解,但是效率不是很好,实际中很少用

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

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

4.稳定性:不稳定

代码实现:

//选择排序
//最坏时间复杂度:O(N^2)
//最好时间复杂度:O(N^2)
void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
void SelectSort(int* a, int n)
{
	int begin - 0.end = n - 1;
	while (begin < end)
	{
		//选出最小的放begin位置
		//选出最大的放end位置
		int mini = begin, maxi = begin;
		for (int i = begin + 1; i <= end; ++i)
		{
			if (a[i] > a[maxi])
			{
				maxi = i;
			}
			if (a[i] < a[mini])
			{
				mini = i;
			}
		}
		Swap(&a[begin], &a[mini]);
		//最大数据在第一个位置时需要修正一下maxi
		if (maxi == begin)
			maxi = mini;
		Swap(&a[end], &a[maxi]);
		++begin;
		--end;
	}
}

5.冒泡排序

基本思想:

所谓交换,就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置,冒泡排序的特点是:将键值较大的记录向序列的尾部移动,键值较小的数据向序列的前部移动。

冒泡排序的特性总结:

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

2.空间复杂度:O(1)

3.稳定性:稳定

代码实现:

//冒泡排序
//最坏时间复杂度——O(N^2)
//最好时间复杂度——O(N)
void BubbleSort(int* a, int n)
{
	for (int j = 0; j < n; ++j)
	{
		int exchange = 0;
		for (int i = 1; i < n - j; ++i)
		{
			if (a[i - 1] > a[i])
			{
				Swap(&a[i - 1], &a[i]);
				exchange = 1;
			}
		}
		if (exchange == 0)
		{
			break;
		}
	}
}

6.堆排序

堆排序(HeapSort)是指利用堆这种数据结构所设计的一种排序算法,它是选择排序的一种,通过堆来进行选择数据,需要注意的是升序要建大堆,降序要建小堆。 

堆排序的特性总结:

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

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

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

4.稳定性:不稳定

代码实现:

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
void AdjustDown(int* a, int n, int parent)
{
	int minChild = parent * 2 + 1;
	while (minChild < n)
	{
		if (minChild + 1 < n && a[minChild + 1] > a[minChild]);
		{
			minChild++;
		}
		if (a[minChild] > a[parent])
		{
			Swap(&a[minChild], &a[parent]);
			parent = minChild;
			minChild = 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 i = 1;
	while (i < n)
	{
		Swap(&a[0], &a[n - i]);
		AdjustDown(a, n - i, 0);
		++i;
	}
}

7.快速排序

快速排序是 Hoare 1962 年提出的一种二叉树结构的交换排序方法,其基本思想为: 任取待排序元素序列中 的某元素作为基准值,按照该排序码将待排序集合分割成两子序列,左子序列中所有元素均小于基准值,右 子序列中所有元素均大于基准值,然后最左右子序列重复该过程,直到所有元素都排列在相应位置上为止
//假设按照升序对array数组中[left, right)区间中的元素进行排序
void QuickSort(int array[], int left, int right)
{
 if(right - left <= 1)
 return;
 
 // 按照基准值对array数组的 [left, right)区间中的元素进行划分
 int div = partion(array, left, right);
 
 // 划分成功后以div为边界形成了左右两部分 [left, div) 和 [div+1, right)
 // 递归排[left, div)
 QuickSort(array, left, div);
 
 // 递归排[div+1, right)
 QuickSort(array, div+1, right);
}
上述为快速排序递归实现的主框架,发现与二叉树前序遍历规则非常像,同学们在写递归框架时可想想二叉树前序遍历规则即可快速写出来,后序只需分析如何按照基准值来对区间中数据进行划分的方式即可。将区间按照基准值划分为左右两半部分的常见方式有:
//快速排序
//单趟排序:
//1.选1个key(一般是第一个或者是最后一个)
//2.单趟排序要求小的在key的左边,大的在key的右边
//相遇位置如何保证比key要小——左边第一个做key R先走
//1.R停下来 L遇到R 二者相遇 相遇位置比key小
//2.L停下来 R遇到L 二者相遇 相遇位置比key小
//发生第二种情况一定是R没有找到小的和L相遇,但此时L的位置已经被换成比key小的数据
//同样的道理:如果右边第一个做key——L先走
//单趟排序的价值
//1.key已经找到了它的最终位置,这个数已经排好了
//2.分割出去了两个子区间,如果子区间有序。整体就有序了
//子区间如何有序呢?——子区间递归
//最好时间复杂度:O(N*logN)
//最坏时间复杂度:O(N^2)
int PartSort(int* a, int left, int right)
{
	//数组之间的交换 不能和值换 要和对应的位置换
	int keyi = left;
	while (left < right)
	{
		//R找小
		while (left < right && a[right] >= a[keyi])
		{
			--right;
		}
    	//L找大
		while (left < right && a[left] <= a[keyi])
		{
			++left;
		}
		if(left < right)
		Swap(&a[left], &a[right]);
	}
	int meeti = left;
	Swap(&a[meeti], &a[keyi]);
	return meeti;
}

Hoare版本

//优化快速排序:1.三数取中 2.小区间优化减少递归次数
//三数取中
int GetMidIndex(int* a, int left, int right)
{
	int mid = (right + left) / 2;
	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;
		}
	}
}
//Hoare
int PartSort1(int* a, int left, int right)
{
	//三数取中
	int mid = GetMidIndex(a, left, right);
	Swap(&a[left], &a[mid]);
	int keyi = left;
	while (left < right)
	{
		//R找小
		while (left < right && a[right] >= a[keyi])
		{
			--right;
		}
		//L找大
		while (left < right && a[left] <= a[keyi])
		{
			++left;
		}
		if (left < right)
			Swap(&a[left], &a[right]);
	}
	int meeti = left;
	Swap(&a[meeti], &a[keyi]);
	return meeti;
}
//[begin,end]
void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
	if (end - begin <= 8)
	{
		InsertSort(a + begin, end - begin + 1);
	}
	else
	{
		int keyi = PartSort1(a, begin, end);
		//[begin,keyi-1] keyi [keyi+1,end]
		QuickSort(a, begin, keyi - 1);
		QuickSort(a, keyi + 1, end);
	}
}

挖坑法

//挖坑法
//理解:1.左边是坑必然右边先走找数填坑 2.相遇位置必然是坑 
int PartSort2(int* a, int left, int right)
{
	//三数取中
	int mid = GetMidIndex(a, left, right);
	Swap(&a[left], &a[mid]);
	int keyi = left;
	int key = a[left];
	int hole = left;
	while (left < right)
	{
		//右边找小 填到左边的坑
		while (left < right && a[right] >= key)
		{
			--right;
		}
		a[hole] = a[right];
		hole = right;
		//左边找大填到右边的坑
		while (left < right && a[left] <= key)
		{
			++left;
		}
		a[hole] = a[left];
		hole = left;
	}
	a[hole] = key;
	return hole;
}
//[begin,end]
void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
	if (end - begin <= 8)
	{
		InsertSort(a + begin, end - begin + 1);
	}
	else
	{
		int keyi = PartSort2(a, begin, end);
		//[begin,keyi-1] keyi [keyi+1,end]
		QuickSort(a, begin, keyi - 1);
		QuickSort(a, keyi + 1, end);
	}
}

前后指针法:

//前后指针法
//cur找小 prev紧跟着cur prev和cue之间间隔的是比key大的值
//cur遇到比key小的值时 就停下来 ++prev
//交换prev和cur位置的值
int PartSort3(int* a, int left, int right)
{
	//三数取中
	int mid = GetMidIndex(a, left, right);
	Swap(&a[left], &a[mid]);
	int keyi = left;
	int prev = left;
	int cur = left + 1;
	while (cur <= right)
	{
		if (a[cur] < a[keyi] && ++prev != cur)
			Swap(&a[cur], &a[prev]);
		++cur;
	}
	//如果交换的是数组中的值 int key = a[left] Swap(&left,&a[prev])只是和局部变量key进行交换 并没有改变数组中的值
	Swap(&a[keyi], &a[prev]);
	return prev;
}
void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
	if (end - begin <= 8)
	{
		InsertSort(a + begin, end - begin + 1);
	}
	else
	{
		int keyi = PartSort3(a, begin, end);
		//[begin,keyi-1] keyi [keyi+1,end]
		QuickSort(a, begin, keyi - 1);
		QuickSort(a, keyi + 1, end);
	}
}

快速排序非递归:

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
//静态栈
/*#define N 100
typedef int STDataType;
struct Stack
{
	STDataType a[N];
	int top;
};*/
//动态栈
typedef char STDataType;
typedef struct Stack
{
	STDataType * a;
    int top;
	int capacity;
}ST;
void StackInit(ST* ps);
void StackDestory(ST* ps);
void StackPush(ST* ps, STDataType x);
void StackPop(ST* ps);
bool StackEmpty(ST* ps);
int StackSize(ST* ps);
//访问栈顶数据
STDataType StackTop(ST* ps);
#include"Stack.h"
void StackInit(ST* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}
void Destory(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->top = 0;
}
//数据结构建议不要直接访问结构体数据,一定要通过函数接口访问
//解耦:高内聚,低耦合
void StackPush(ST* ps, STDataType x)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(ps->a, newCapacity * sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newCapacity;
		ps->a[ps->top] = x;
		ps->top++;
	}
}
void StackPop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	--ps->top;
}
STDataType StackTop(ST* ps)
{
	assert(ps);
	//为空不能访问栈顶元素
	assert(!StackEmpty(ps));
	return ps->a[ps->top - 1];
}
bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}
int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;
}
#include"Stack.h"
//快速排序的非递归
//改非递归:递归函数中的栈帧保存什么 数据结构中的栈就保存什么
void QuickSortNonR(int* a, int begin, int end)
{
	ST st;
	StackInit(&st);
	StackPush(&st, begin);
	StackPush(&st, end);
	while (!StackEmpty(&st)
	{
		int right = StackTop(&st);
		StackPop(&st);
		int left = StackTop(&st);
		StackPop(&st);
		if (left >= right)
		{
			continue;
		}
		int keyi = PartSort3(a, left, right);
		//[left,keyi-1] l=keyi [keyi+1,right]
		StackPush(&st, keyi+1);
		StackPush(&st, right);
		StackPush(&st, left);
		StackPush(&st, keyi-1);

	}
	StackDestory(&st);
}
//优化:在区间为1或者区间不存在的时候 区间值不压入栈中
void QuickSortNonR(int* a, int begin, int end)
{
	ST st;
	StackInit(&st);
	StackPush(&st, begin);
	StackPush(&st, end);
	while (!StackEmpty(&st)
	{
		int right = StackTop(&st);
		StackPop(&st);
		int left = StackTop(&st);
		StackPop(&st);
		int keyi = PartSort3(a, left, right);
		//[left,keyi-1] l=keyi [keyi+1,right]
		if (keyi + 1 < right)
		{
			StackPush(&st, keyi + 1);
			StackPush(&st, right);
		}
		if (left < right - 1)
		{
			StackPush(&st, left);
			StackPush(&st, keyi - 1);
		}

	}
	StackDestory(&st);
}

快速排序的特性总结:

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

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

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

4.稳定性:不稳定

8.归并排序

基本思想:

归并排序( MERGE-SORT )是建立在归并操作上的一种有效的排序算法 , 该算法是采用分治法( Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。 归并排序核心步骤:

 

归并排序的特性总结:

1. 归并的缺点在于需要 O(N) 的空间复杂度,归并排序的思考更多的是解决在磁盘中的外排序问题。
2. 时间复杂度: O(N*logN)
3. 空间复杂度: O(N)
4. 稳定性:稳定
代码实现:
//归并排序
//归并思想:左右区间均有序 取小的尾插到新数组 
//归并排序的时间复杂度:O(N*logN) 空间复杂度为O(N)
//归并排序写子函数的原因:避免频繁malloc
void _MergeSort(int* a, int begin, int end, int* tmp)
{
	if (begin == end)
	{
		return;
	}
	int mid = (end + begin) / 2;
	//[begin,mid] [mid+1,end]
	_MergeSort(a, begin, mid, tmp);
	_MergeSort(a, mid + 1, end, tmp);
	//归并 取小的尾插
	//[begin,mid] [mid+1,end]
	int begin1 = begin, end1 = mid;
	int begin2 = mid + 1, end2 = end;
	int i = begin;
	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++];
	}
	//拷贝回原数组——归并哪部分就拷贝哪部分回去
	memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));
}
void MergeSort(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail");
		return;
	}
	_MergeSort(a, 0, n - 1, tmp);
	free(tmp);
	tmp = NULL;
}

归并排序非递归

//归并排序的非递归
//问题:控制边界 该代码只能处理2的次方次个数据
void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail");
		return;
	}
	int gap = 1;
	while (gap < n)
	{
		//gap个数据 gap个数据进行归并
		for (int j = 0; j < n; j += 2 * gap)
		{
			//归并 取小的尾插
			int begin1 = j, end1 = j + gap - 1;
			int begin2 = j + gap, end2 = j + 2 * gap - 1;
			int i = j;
			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++];
			}
		}
		//拷贝回原数组
		memcpy(a, tmp, n * sizeof(int));
		gap *= 2;
	}	
	free(tmp);
	tmp = NULL;
}
//数据个数不一定是2的整数倍 计算直接按整数倍算的 存在越界 需要修正
//代码优化:控制边界
//三种越界情况:1.第一组end1越界 2.第二组全部越界 3.第三组部分越界
void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail");
		return;
	}
	int gap = 1;
	while (gap < n)
	{
		//gap个数据 gap个数据进行归并
		for (int j = 0; j < n; j += 2 * gap)
		{
			//归并 取小的尾插
			int begin1 = j, end1 = j + gap - 1;
			int begin2 = j + gap, end2 = j + 2 * gap - 1;
			//第一组越界 第二组必然越界 只有一组不需要归并 直接跳出循环
			if (end1 >= n)
			{
				break;
			}
			//第二组全部越界
			if (begin2 >= n)f
			{
				break;
			}
			//第二组部分越界
			if (end2 >= n)
			{
				//修正一下end2 继续归并
				end2 = n - 1;
			}
			int i = j;
			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++];
			}
			//拷贝回原数组
			memcpy(a + j, tmp + j, (end2 - j + 1) * sizeof(int));
		}
		gap *= 2;
		printf("\n");
	}
	free(tmp);
	tmp = NULL;
}

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

排序总结
直接插入排序最好的时间复杂度是O(N)最坏的时间复杂度是O(N^2)
希尔排序时间复杂度是O(N^1.3)
选择排序最好的时间复杂度是O(N^2)最坏的时间复杂度是O(N^2)
堆排序最好的时间复杂度是O(N*logN)最坏的时间复杂度是O(N*logN)
冒泡排序最好的时间复杂度是O(N)最坏的时间复杂度是O(N^2)
快速排序最好的时间复杂度是O(N*logN)最坏的时间复杂度是O(N^2)
归并排序最好的时间复杂度是O(N*logN)最坏的时间复杂度是O(N)
快速排序的空间复杂度是O(logN)归并排序的空间复杂度是O(N)
稳定性:数组中相同的值 排完序相对顺序可以做到不变就是稳定的 否则就不稳定
冒泡排序的稳定性好
选择排序的稳定性差
插入排序的稳定性好
希尔排序的稳定性差
堆排序的稳定性差
归并排序的稳定性好
快速排序的稳定性差

10.排序选择题练习

1. 快速排序算法是基于( )的一个排序算法。
A分治法
B贪心法
C递归法
D动态规划法
2.对记录(54,38,96,23,15,72,60,45,83)进行从小到大的直接插入排序时,当把第8个记录45插入到有序表时,为找到插入位置需比较( )次?(采用从后往前比较)
A 3
B 4
C 5
D 6
3.以下排序方式中占用O(n)辅助存储空间的是
A 简单排序
B 快速排序
C 堆排序
D 归并排序
4.下列排序算法中稳定且时间复杂度为O(n2)的是( )
A 快速排序
B 冒泡排序
C 直接选择排序
D 归并排序
5.关于排序,下面说法不正确的是
A 快排时间复杂度为O(N*logN),空间复杂度为O(logN)
B 归并排序是一种稳定的排序,堆排序和快排均不稳定
C 序列基本有序时,快排退化成冒泡排序,直接插入排序最快
D 归并排序空间复杂度为O(N), 堆排序空间复杂度的为O(logN)
6.下列排序法中,最坏情况下时间复杂度最小的是( )
A 堆排序
B 快速排序
C 希尔排序
D 冒泡排序
7.设一组初始记录关键字序列为(65,56,72,99,86,25,34,66),则以第一个关键字65为基准而得到的一趟快
速排序结果是()
A 34,56,25,65,86,99,72,66
B 25,34,56,65,99,86,72,66
C 34,56,25,65,66,99,86,72
D 34,56,25,65,99,86,72,66
答案:
1.A
2.C
3.D
4.B
5.D
6.A
7.A

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/2925.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【C语言蓝桥杯每日一题】——排序

【C语言蓝桥杯每日一题】—— 排序&#x1f60e;前言&#x1f64c;排序&#x1f64c;总结撒花&#x1f49e;&#x1f60e;博客昵称&#xff1a;博客小梦 &#x1f60a;最喜欢的座右铭&#xff1a;全神贯注的上吧&#xff01;&#xff01;&#xff01; &#x1f60a;作者简介&am…

【千题案例】TypeScript获取两点之间的距离 | 中点 | 补点 | 向量 | 角度

我们在编写一些瞄准、绘制、擦除等功能函数时&#xff0c;经常会遇到计算两点之间的一些参数&#xff0c;那本篇文章就来讲一下两点之间的一系列参数计算。 目录 1️⃣ 两点之间的距离 ①实现原理 ②代码实现及结果 2️⃣两点之间的中点 ①实现原理 ②代码实现及结果 3…

当下的网络安全行业前景到底怎么样?还能否入行?

前言网络安全现在是朝阳行业&#xff0c;缺口是很大。不过网络安全行业就是需要技术很多的人达不到企业要求才导致人才缺口大常听到很多人不知道学习网络安全能做什么&#xff0c;发展前景好吗&#xff1f;今天我就在这里给大家介绍一下。网络安全作为目前比较火的朝阳行业&…

给程序加个进度条吧,1行Python代码,快速添加~

大家好&#xff0c;这里是程序员晚枫。 你在写代码的过程中&#xff0c;有没有遇到过以下问题&#xff1f; 已经写好的程序&#xff0c;想看看程序执行的进度&#xff1f; 在写代码批量处理文件的时候&#xff0c;如何显示现在处理到第几个文件了&#xff1f; &#x1f446…

真要被00后职场整顿了?老员工纷纷表示真的干不过.......

最近聊到软件测试的行业内卷&#xff0c;越来越多的转行和大学生进入测试行业。想要获得更好的待遇和机会&#xff0c;不断提升自己的技能栈成了测试老人迫在眉睫的问题。 不论是面试哪个级别的测试工程师&#xff0c;面试官都会问一句“会编程吗&#xff1f;有没有自动化测试…

dfs和bfs能解决的问题

一.理解暴力穷举之dfs和bfs暴力穷举暴力穷举是在解决问题中最常用的手段&#xff0c;而dfs和bfs算法则是这个手段的两个非常重要的工具。其实&#xff0c;最简单的穷举法是直接遍历&#xff0c;如数列求和&#xff0c;遍历一个数组即可求得所问答案&#xff0c;这与我在前两篇博…

【lwIP(第二章)】以太网DMA

目录一、以太网DMA描述符简介二、以太网DMA描述符结构三、如何追踪描述符总结一、以太网DMA描述符简介 发送&#xff1a;不需要CPU的参与下&#xff0c;把描述符指向的缓冲区数据传输到Tx FIFO当中 接收&#xff1a;不需要CPU的参与下&#xff0c;将Rx FIFO中的数据传输到描述符…

3 天交付新需求?极狐GitLab APP 「极限编程 XP」实践

近日&#xff0c;中移物联网有限公司、北京青云科技股份有限公司联合举办的 “2023 云原生重庆站技术分享会” 如期召开。会上&#xff0c;极狐(GitLab) 高级解决方案架构师刘剑桥带来《云原生极限编程 101》主题分享。本文整理自演讲内容&#xff0c;你可以阅读到&#xff1a;…

java调用chatgpt接口,实现专属于自己的人工智能助手

文章目录前言导包基本说明请求参数响应参数创建请求和响应的VO类代码编写使用最后说明前言 今天突然突发奇想&#xff0c;就想要用java来调用chatget的接口&#xff0c;实现自己的聊天机器人&#xff0c;但是网上找文章&#xff0c;属实是少的可怜(可能是不让发吧)。找到了一些…

【数据结构与算法】什么是双向链表?并用代码手动实现一个双向链表

文章目录一、什么是双向链表二、双向链表的简单实现一、什么是双向链表 我们来看一下这个例子&#xff1a; 在一个教室里&#xff0c;所有的课桌排成一列&#xff0c;如图 相信在你们的读书生涯中&#xff0c;老师肯定有要求你们记住自己的前后桌是谁。所以该例子中&#x…

J 砍竹子

砍竹子 【问题描述】 这天&#xff0c;小明在砍竹子&#xff0c;他面前有 n 棵竹子排成一排&#xff0c;一开始第 i 棵竹子的高度为 hi . 他觉得一棵一棵砍太慢了&#xff0c;决定使用魔法来砍竹子。魔法可以对连续的一段相同高度的竹子使用&#xff0c;假设这一段竹子的高度…

菜鸟刷题Day5

⭐作者&#xff1a;别动我的饭 ⭐专栏&#xff1a;菜鸟刷题 ⭐标语&#xff1a;悟已往之不谏&#xff0c;知来者之可追 一.一维数组的动态和&#xff1a;1480. 一维数组的动态和 - 力扣&#xff08;LeetCode&#xff09; 描述 给你一个数组 nums 。数组「动态和」的计算公式…

为了之后找工作不被虐,每天刷3道《剑指offer》Day-1

本文已收录于专栏&#x1f33b;《刷题笔记》文章目录前言&#x1f496; 1、二维数组中的查找题目描述思路&#x1f496; 2、替换空格题目描述思路&#x1f496; 3、从尾到头打印链表题目描述思路一&#xff08;反转函数&#xff09;思路二&#xff08;递归&#xff09;思路二&a…

Celery使用:优秀的python异步任务框架

目录Celery 简介介绍安装基本使用Flask使用Celery异步任务定时任务Celery使用Flask上下文进阶使用参考停止Worker后台运行Celery 简介 介绍 Celery 是一个简单、灵活且可靠的&#xff0c;处理大量消息的分布式系统&#xff0c;并且提供维护这样一个系统的必需工具。 它是一个…

文心一言 vs GPT-4 —— 全面横向比较

文心一言 vs GPT-4 —— 全面横向比较 3月15日凌晨&#xff0c;OpenAI发布“迄今为止功能最强大的模型”——GPT-4。我第一时间为大家奉上了体验报告《OpenAI 发布GPT-4——全网抢先体验》。 时隔一日&#xff0c;3月16日下午百度发布大语言模型——文心一言。发布会上&#…

4万字企业数字化转型大数据湖项目建设和运营综合解决方案WORD

本资料来源公开网络&#xff0c;仅供个人学习&#xff0c;请勿商用&#xff0c;如有侵权请联系删除。部分资料内容&#xff1a; 3.1.4沙盒管理 利用Docker, 基于kubernetes主打的容器技术与微服务应用基础平台&#xff0c;HDFS和YARN均可依此建模&#xff0c;为上层应用提供微服…

不愧是2023年就业最难的一年,还好有车企顶着~

就业龙卷风已经来临&#xff0c;以前都说找不到好的工作就去送外卖&#xff0c;但如今外卖骑手行业都已经接近饱和状态了&#xff0c;而且骑手们的学历也不低&#xff0c;本科学历都快达到了30%了&#xff0c;今年可以说是最难找到工作的一年。 像Android 开发行业原本就属于在…

学习 Python 之 Pygame 开发魂斗罗(十)

学习 Python 之 Pygame 开发魂斗罗&#xff08;十&#xff09;继续编写魂斗罗1. 解决敌人不开火的问题2. 创建爆炸效果类3. 为敌人跳入河中增加爆炸效果4. 玩家击中敌人继续编写魂斗罗 在上次的博客学习 Python 之 Pygame 开发魂斗罗&#xff08;九&#xff09;中&#xff0c;…

深度长文 | 数据安全共享技术发展综述及在能源电力领域应用研究

开放隐私计算 编者按数据要素的流通共享与协同应用是数字时代中数据要素市场培育的核心内容&#xff0c;数据安全共享技术能够有效实现数据的安全共享&#xff0c;避免“数据孤岛”现象、隐私泄露事件等.本文对国内外数据安全共享技术研究成果及进展进行了全面综述.首先&#x…

[前端笔记037]vue2之vuex

前言 本笔记参考视频&#xff0c;尚硅谷:BV1Zy4y1K7SH p105 - p116 vuex简介和基本使用 概念&#xff1a;专门在 Vue 中实现集中式状态&#xff08;数据&#xff09;管理的一个 Vue 插件&#xff0c;对 vue 应用中多个组件的共享状态进行集中式的管理&#xff08;读/写&…