描述:
通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
快速排序 的平均时间复杂度为O(NlogN),是冒泡排序的一种改进版。
方法:快速排序主要采用“二分”的思想,步骤如下:
- 设置两个变量i、j,排序开始的时候:i=0,j=n-1;
2)待排序数组的第一个数组值s[0]作为比较值,首先保存到temp中,即temp=s[0];
3)然后j-- ,向前搜索,找到小于temp后,因为s[i]的值保存在temp中,所以直接赋值,s[i]=s[j]
4)然后i++,向后搜索,找到大于temp后,因为s[j]的值保存在第2步的s[i]中,所以直接赋值,s[j]=s[i],然后j–,避免死循环
5)重复第3、4步,直到i=j,最后将temp值返回s[i]中
- 然后采用“二分”的思想,以i为分界线,拆分成两个数组 s[0,i-1]、s[i+1,n-1]又开始排序
如下图,以数组 6 4 7 1 2为例:
代码如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
| #include "stdio.h" void find_frst(int *s,int left,int right) { int i=left,j=right,temp; if(left>=right) return ; temp=s[i]; while(i<j) { while(j>i&&s[j]>=temp) j--; s[i]= s[j]; while(i<j&&s[i]<=temp) i++; s[j--]=s[i]; } s[i]=temp; find_frst(s,left,i-1); find_frst(s,i+1,right); } int main() { int i=0,s[100],n; scanf("%d",&n); for(i=0;i<n;i++) scanf("%d",&s[i]); find_frst(s,0,n-1); for(i=0;i<n;i++) printf("%d ",s[i]); printf("\n"); }
|
既然有了排序,那么还有可能用到查找,在有序条件下,当然用二分查找快咯,即简单又速度快
代码如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70
| #include "stdio.h"
void find_frst(int *s,int left,int right) { int i=left,j=right,temp; if(left>=right) return ; temp=s[i]; while(i<j) { while(j>i&&s[j]>=temp) j--; s[i]= s[j]; while(i<j&&s[i]<=temp) i++; s[j--]=s[i]; } s[i]=temp; find_frst(s,left,i-1); find_frst(s,i+1,right); }
int binary_query(const int* s, int size, int cmp) { int low = 0; int high = size-1; int mid; while(low<=high) { mid = (low+high)/2; if(s[mid] == cmp) return mid; else if(s[mid] > cmp) high = mid-1; else low = mid+1; } return -1; }
int main() { int i=0,s[100],n,tmp,index; scanf("%d",&n); for(i=0;i<n;i++) scanf("%d",&s[i]); find_frst(s,0,n-1); printf("find_frst:\n",s[i]); for(i=0;i<n;i++) printf("%d ",s[i]); printf("\n"); scanf("%d",&tmp); index=binary_query(s,n,tmp); if(index<0) printf("ERR,The value is not querying\n"); else printf("index=%d\n",index); }
|