首页 > 代码库 > 巧妙利用快速排序法的原理求一个数组中的第10大元素
巧妙利用快速排序法的原理求一个数组中的第10大元素
//快速排序法 int QuickSort_process3(int *a, int low, int high) { int l, h, temp; l = low; h = high; temp = a[low]; while (l < h){ while (l< h&&a[h] >= temp) --h; if (l < h) a[l] = a[h]; while (l < h&&a[l] < temp) ++l; if (l < h) a[h] = a[l]; } a[h] = temp; return h; } void QuickSort3(int *a, int low,int high) { int pos; if (low < high){ pos = QuickSort_process3(a,low,high); QuickSort3(a,low,pos-1); QuickSort3(a,pos+1,high); } } int getTop_N_Numbers(int *a,int n) { int pos, curpos, e; do{ printf("Please input a numbers(less than %d and bigger than 0).\n", n); scanf("%d",&e); } while (!(e<=n&&e>=1)); pos = n - e;/*在一个从小到大排序的数组中,最大第e个数的下标恰好是n-e*/ curpos = QuickSort_process3(a, 0, n - 1);/*一趟快排结束时,肯定会有一个已经确定了位置的数,返回它的下标*/ while (1){ if (curpos == pos){/*当要找的第几最大的数的位子已经确定后,说明,比它还要大的数也已经确定了,就不再排序了,直接返回*/ break; } else if (curpos < pos){/*在后半部找*/ curpos = QuickSort_process3(a,curpos+1,n-1); } else{/*在前半部分找*/ curpos = QuickSort_process3(a,0,curpos-1); } } return pos; } void show_TopN_numbers(int *a,int n) { int k = getTop_N_Numbers(a, n); int i; printf("The Top %d numbers are :\n",n-k); for (i = k; i < n; ++i) printf("%d ",a[i]); printf("\n"); }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。