C++各自排序重点笔记-创新互联
目录
创新互联建站自2013年起，先为喀喇沁等服务建站，喀喇沁等地企业，进行企业商务咨询服务。为喀喇沁企业网站制作PC+手机+微官网三网同步一站式服务解决您的所有建站问题。1.各种排序算法的性能对比
2.插入排序
3.冒泡排序
4.选择排序
1.各种排序算法的性能对比
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]);
}
}
}
}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个结点的二叉树最小层数（最小时间复杂度需要最小层数） 你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
，每层对比n次，时间复杂度最小O()。
本文题目：C++各自排序重点笔记-创新互联
网站地址：http://6mz.cn/article/cdjdgs.html