好贷网好贷款

面试经典算法1之交换排序

发布时间:2016-12-4 16:28:04 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"面试经典算法1之交换排序",主要涉及到面试经典算法1之交换排序方面的内容,对于面试经典算法1之交换排序感兴趣的同学可以参考一下。

交换排序的典型代表有: (1)  冒泡排序 (2)  快速排序 冒泡排序:每趟都是比较相邻的两个元素,如果逆序,则将两者交换。每趟都是从数组的第一个元素开始扫描。 冒泡排序代码: bool BubbleSort(int A[],int n) { if (A==NULL||n<=0) { printf("Parameters for function BubbleSort error!\n"); return false; } bool flag = true; for (int i=0;i<n-1&&flag;i++) //n-1趟即可 { flag = false; for (int j=0;j<n-i-1;j++) //从大到小 { if (A[j]<A[j+1]) { int temp = A[j+1]; A[j+1] = A[j]; A[j] = temp; flag = true; } } } return true; } 注意事项: (1) i,j变量的取值范围,i决定扫描的趟数,最多只需n-1次扫描,即可是数组有序。j取值范围,i的值表示已经有i个数排好序,而一共有n个数,所以还有n-i个数没有排好序,右因为j的下标是从0开始不是从1开始的,所以没排好序的是A[0]、A[1]....A[n-i-1],因为下面是那A[j]与A[j+1]比较,所以j应小于n-i-1。 (2) flag标志变量的作用是当某一趟扫描中,若没有发生交换,说明所有数据已经有序了,则排序过程完成。 (3) 若真正面试时,不可忘记函数开始的那段代码,对输入参数检查。 算法效率分析: 最好情况:初始序列为正序序列,只需进行一次排序,在此过程中进行n-1次比较,不移动   数据。 最差情况:初始序列为逆序序列,需要进行n-1趟排序,需要进行内n(n-1)/2次比较,并且   移动数据,每次比较都必须移动记录三次来达到交换记录位置。因此总的时间复杂度为O(n2)。 冒泡排序是就地排序,是稳定的。  快速排序:快速排序采用的是分治的思想。将待排序的数组划分为多个子数组,若每一个子数组排好了序,则整个数组就排好了序。对于每一个划分的子数组,采用如下思想排序:假设数组第一个元素为A[0],我们所要做的是找到A[0]这个元素应该放的位置(假设为j),也即使A[j]前面的元素都小于它A[0],A[j]后面的元素都大于A[0]. 快速排序代码: //划分函数 int Partition(int A[],int L,int R) { int i,j; i = L; j = R; int pivot = A[0]; while(i<j) { while(i<j&&A[j]>pivot) { j--; } if(i<j) { A[i] = A[j]; i++; } while(i<j&&A[i]<pivot) { i++; } if(i<j) { A[j] = A[i]; j--; } } A[i] = pivot; return i; } bool QuickSort(int A[],int L,int R) { if(A==NULL||L>R||L<0||R<0) { printf("Paraments for function QuickSort Error!\n"); return false; } int pivot = Partition(A,L,R); QuickSort(A,L,pivot-1); QucikSort(A,pivot+1,R); return true; }快速排序的时间复杂度为O(n*log2n),它是一种不稳定的排序。

上一篇:导出mysql数据库数据
下一篇:linux下CVS安装配置

相关文章

相关评论