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

目录

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

2.插入排序

3.冒泡排序

4.选择排序

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外会用，内部定义的话，循环结束就销毁了。

非常熟悉，就不画图表示了，代码如下：

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]);
			}
		}
	}
}

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）。

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);