快速排序,是最常用的排序算法,就是选择待排序的列表中的其中一个数字,作为基准数,然后把小于基准数的所有数字放到这个数的左边,大于这个数的所有数字放到基准数的右边。这个时候开始分为两部分,左边和右边。第一部分,在左边中选择一个数字作为基准数,把小于这个数字的放到这个数的左边,大于这个数的放到这个数的右边。第二部分,在右边中选择一个数字作为基准数,把小于这个数字的放到这个数的左边,大于这个数的放到这个数的右边。ok,很明显,递归!
快速排序的时间复杂度在最坏的情况下是O(N2),因为和冒泡排序一样,需要两两交换。平均情况下,快速排序的时间复杂度是O(NlogN)。
下面是C语言的代码
#include <stdio.h>
void quickSort(int left, int right, int *rank);
int main(){
int i, j, num, score, tmp;
printf("How many?\n");
scanf("%d", &num);
int rank[num];
for(i=0; i<num; i++){
printf("Enter Score:\n");
scanf("%d", &score);
//我们的试卷是0-100分的哦
if(score<0 || score > 100){
printf("Error");
return 1;
}
rank[i] = score;
}
printf("Rank:\n");
quickSort(0, num-1, rank);
for(i=0; i<num; i++){
printf("%d,", rank[i]);
}
return 0;
}
void quickSort(int left, int right, int *rank){
if(left > right){
return;
}
int i, j, t, tmp;
i = left;
j = right;
t = rank[left];
while(i!=j){
while(rank[j]>=t && i<j)
j--;
while(rank[i]<=t && i<j)
i++;
if(i < j){
tmp = rank[j];
rank[j] = rank[i];
rank[i] = tmp;
}
}
rank[left] = rank[i];
rank[i] = t;
quickSort(left, i-1, rank);
quickSort(i+1, right, rank);
}
Reply: StevJaby On 2020-03-21 01:31:53
Priligy Venta https://apcialisle.com/# - online cialis Miglior Viagra Senza Ricetta <a href=https://apcialisle.com/#>Cialis</a> Viagra Requiere Receta Medica
Reply: VassiGn On 2020-05-04 04:47:58
No Presription Finasteride https://abcialisnews.com/# - Cialis Where Can I Buy Discount Progesterone Medication Shop <a href=https://abcialisnews.com/#>Cialis</a> Levoxyl Pharm
Reply: Launa On 2020-05-17 19:33:59
Wonderful post! We are linking to this great article on our site. Keep up the great writing.
Bslanteefs On pharmacie boulogne billancourt...
Bslanteefs On therapie streaming, pharmacie ...
EElemeecowl On pharmacie lafayette belfort, a...
BInfurnese On pharmacie simo argenteuil, pha...
BInfurnese On pharmacie lafayette amiens tel...
Reply: weihd On 2014-11-01 20:22:12
very nice
回复