成都建站模板公司,上海外贸营销网站建设地址,手机网站哪些功能,排版 网站快速排序
快速排序是对冒泡排序的一种改进。 它的基本思想是:通过一趟排序将待排记录分割成独立的两部分#xff0c;其中一部分记录的关键字均比另一部分记录的关键字小#xff0c;则可分别对这两部分记录继续进行快速排序#xff0c;以达到整个序列有序。 假设我们现在对 …快速排序
快速排序是对冒泡排序的一种改进。 它的基本思想是:通过一趟排序将待排记录分割成独立的两部分其中一部分记录的关键字均比另一部分记录的关键字小则可分别对这两部分记录继续进行快速排序以达到整个序列有序。 假设我们现在对 6 1 2 7 9 3 4 5 1 0 8 这个10个数进行排序。
int main(){int n;cinn;for(int i1;in;i) cina[i];qsort(1,n);for(int i1;i n;i){couta[i] ;} return 0;
}首先在这个序列中随便找一个数作为基准数(不要被这个名词吓到了就是一个用来参照的数)。为了方便就让第一个数6作为基准数吧。接下来需要将这个序列中所有比基准数大的数放在6的右边比基准数小的数放在6的左边类似下面这种排列:
int a[10001];
void qsort(int l,int r){int i,j,mid;il1,jr;mida[l];可以发现i从第二个位置开始j从最后一个位置开始当 i 指向的值 大于基准值6 而且 当 j 指向的值 小于基准值6就把这两个值交换然后接着往下继续比。
while(ij){ //当 i j 没有碰到while(a[i]mid) i;while(a[j]mid) j--;if(ij){swap(a[i],a[j]);i; j--;}}当 i j 相遇了就把 j指向的值 与基准数交换。
swap(a[j],a[l]); //交换基准数可以发现一趟完毕原基准数6的左边值一定比6小右边比6大。这样就确定了基准数6的排序。 接下来对于6左边的序列3 1 2 5 4和右边的序列9 7 10 8分别进行快速排序。 把整体分了左右边再把左边的序列3 1 2 5 4看成新的重新进行快速排序。不断地分解。 所以这个排序运用了分治的思想 完整代码
#includebits/stdc.h
using namespace std;
int a[10001];
void qsort(int l,int r){int i,j,mid;il1,jr;mida[l];while(ij){while(a[i]mid) i;while(a[j]mid) j--;if(ij){swap(a[i],a[j]);i; j--;}}swap(a[j],a[l]); //交换基准数if(lj) qsort(l,j-1);if(ir) qsort(i,r);
}
int main(){int n;cinn;for(int i1;in;i) cina[i];qsort(1,n);for(int i1;i n;i){couta[i] ;} return 0;
}
快速排序是不稳定的排序方法时间复杂度是O(nlog2n)速度快平均时间来说快速排序是最好的一种内部排序方法。但快速排序需要一个栈空间实现递归每一趟排序都会将记录序列分割成两个子序列栈最大深度为log(n1)。 归并排序
归并的思路分治是把一个大问题a拆解成两个小问题b和c解决了两个子问题再整合一下就解决了原问题。用递归的方法先分解再合并分治是一种解决问题的处理思想递归是一种编程技巧这两者并不冲突。
稳定性稳定空间复杂度O(n)复杂度时间复杂度O(nlogn)优缺点效率高且稳定但是消耗的辅助空间与原数据空间成正比。
int main(){cinn;for(int i1;in;i){ //输入 cina[i];}//归并排序mergesort(1,n);for(int i1;in;i){ //输出 couta[i] ;}return 0;
}递归分解 不断地二分分解拆左右。
void mergesort(int l,int r){int mid (lr)/2;if(lr) return ;mergesort(l,mid); //左边排序mergesort(mid1,r);//右边排序//上面已经拆成一个一个 merge(l,mid,mid1,r); //合并操作
}分解到1个值然后再合并排序。合并的思路看成左边是有序的a数组右边是有序的b数组。两数组开始比较小的值依次存到c数组。
int a[100],c[100],n,cnt;
void merge(int left,int i,int j,int right){int lenc left;int len1 left; //左边开头 看成a[] int len2 j; //右边开头 看成b[] while(len1i len2right){ //并c[] if(a[len1]a[len2]){ //左边小于右边 c[lenc] a[len1];}else{//右边小于左边c[lenc] a[len2];}} while(len1i){c[lenc] a[len1];} while(len2right){c[lenc] a[len2];}//把排好序的c数组存回a数组里面for(int kleft;kright;k){a[k]c[k];}
} 完整代码
#includebits/stdc.h
using namespace std;
int a[100],c[100],n,cnt;
void merge(int left,int i,int j,int right){int lenc left;int len1 left; //左边开头 看成a[] int len2 j; //右边开头 看成b[] while(len1i len2right){ //并c[] if(a[len1]a[len2]){ //左边小于右边 c[lenc] a[len1];}else{//右边小于左边c[lenc] a[len2];}} while(len1i){c[lenc] a[len1];} while(len2right){c[lenc] a[len2];}//把排好序的c数组存回a数组里面for(int kleft;kright;k){a[k]c[k];}
} void mergesort(int l,int r){int mid (lr)/2;if(lr) return ;mergesort(l,mid); //左边排序mergesort(mid1,r);//右边排序//上面已经拆成一个一个 merge(l,mid,mid1,r); //合并操作
}
int main(){cinn;for(int i1;in;i){ //输入 cina[i];}//归并排序mergesort(1,n);for(int i1;in;i){ //输出 couta[i] ;}return 0;
}
