快速排序,是最常用的排序算法,就是选择待排序的列表中的其中一个数字,作为基准数,然后把小于基准数的所有数字放到这个数的左边,大于这个数的所有数字放到基准数的右边。这个时候开始分为两部分,左边和右边。第一部分,在左边中选择一个数字作为基准数,把小于这个数字的放到这个数的左边,大于这个数的放到这个数的右边。第二部分,在右边中选择一个数字作为基准数,把小于这个数字的放到这个数的左边,大于这个数的放到这个数的右边。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); }
上一篇:
算法二:冒泡排序
下一篇:
算法四:队列
友情提示:垃圾评论一律封号...