C++各自排序重点笔记-创新互联

目录

创新互联建站自2013年起,先为喀喇沁等服务建站,喀喇沁等地企业,进行企业商务咨询服务。为喀喇沁企业网站制作PC+手机+微官网三网同步一站式服务解决您的所有建站问题。

1.各种排序算法的性能对比

2.插入排序

3.冒泡排序

4.选择排序


1.各种排序算法的性能对比

2.插入排序

void InsertSort(int A[], int n) {
	int j,i,temp;
	for (i = 1;i< n;i++) {
			temp = A[i];
			for (j=i-1;j >= 0;j--) {
				if (A[j] >temp) {
					A[j + 1] = A[j];
				}
				else {
					break;
				}
			}
		A[j+1] = temp;
		}
}

关键点:

1.假设前面元素有序,取某元素插入到有序序列中。

2.二层for内, 判断temp前面的元素移动还是不移动,只要不移动,直接break跳出循环。

3.第二个for中,j不要在for里面定义,因为for外会用,内部定义的话,循环结束就销毁了。

3.冒泡排序

非常熟悉,就不画图表示了,代码如下:

void BubbleSort(int A[], int n) {
	int i, j;
	for (i = 0;i< n - 1;i++) {
		for (j = 0;j< n - 1 - i;j++) {
			if (A[j] >A[j + 1]) {
				swap(A[j], A[j + 1]);
			}
		}
	}
}
4.选择排序
void SelectSort(int* A, int n) {
	int i, j,min;
	for (i = 0;i< n;i++) {
		min=i;
		for (j = i + 1;j< n;j++) {
			if (A[j]

关键点:

1.main中传递的arr是数组的首地址,形参用指针接收,相当于A的指向和arr指向相同,因此能在局部函数中操作数组内容,其他排序函数亦是如此,可以A[]接受也可以指针接收。

2.总体逻辑就是找最小值,然后放在最前面,需要找n次(第一个for),每次和后续序列比较并更新min(第二个for)。

5.快速排序
int QuickSort(int* A, int low, int high) {
	int dum = A[low];
	while (low< high) {
		while (low< high&&A[high] >= dum) {
			--high;
		}
		A[low] = A[high];
		while (low< high&&A[low]<= dum) {
			++low;
		}
		A[high] = A[low];
	}
	A[low] = dum;
	return low;
}
void	QuickSortmain(int* A, int low, int high) {
	if (low< high) {
		int pre = QuickSort(A, low, high);
		QuickSort(A, low, pre-1);
		QuickSort(A, pre+1, high);
	}
}
main中:QuickSortmain(A, 0, len - 1);

关键点:

1.第二个第三个while也需要限制low

2.时间复杂度和递归深度有关,此递归可以看作二叉树模型,n个结点的二叉树最小层数(最小时间复杂度需要最小层数)log_{2}n+1,每层对比n次,时间复杂度最小O(nlog_{2} n)。

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


网站标题:C++各自排序重点笔记-创新互联
文章起源:http://scyanting.com/article/cdjdgs.html