四川盐亭网站制作公司

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

其他资讯