快速排序，是最常用的排序算法，就是选择待排序的列表中的其中一个数字，作为基准数，然后把小于基准数的所有数字放到这个数的左边，大于这个数的所有数字放到基准数的右边。这个时候开始分为两部分，左边和右边。第一部分，在左边中选择一个数字作为基准数，把小于这个数字的放到这个数的左边，大于这个数的放到这个数的右边。第二部分，在右边中选择一个数字作为基准数，把小于这个数字的放到这个数的左边，大于这个数的放到这个数的右边。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.
MatthewUTILK On <a href=https://mailchi.mp/...
Emmanuel On viagra for men price https://v...
Therese On http://www.aiuextension.org/gr...
Denis On viagra coupon https://genviaga...
Refugia On http://nopain.fun/ buy sildena...
Reply: weihd On 2014-11-01 20:22:12
very nice
回复