思考：对一亿个int型整数排序，哪种排序算法效率最高？ |
您所在的位置：网站首页 › 最稳定的排序算法是哪个 › 思考：对一亿个int型整数排序，哪种排序算法效率最高？ |
思考：对一亿个int型整数排序，哪种排序算法效率最高？
|
下图是常见排序算法的最好，最坏，平均时间复杂度、空间复杂度，稳定性总结表。
直接看表格，综合时间复杂度、空间复杂度等各种因素，目测堆排序是最优选择。不管最好、最坏还是平均情况，时间复杂度都是O(nlogn)，而且还不像快排排序和归并排序那样占空间，计数排序、基数排序、桶排序空间复杂度太大，需要消耗大量额外空间。 快速排序和堆排序接下来亲自比较一下，快速排序和堆排序到底谁效率更高。附上快速排序和堆排序的代码（其中，快速排序使用《编程珠玑》第二版第11章中的方法，堆排序使用第14章中的方法）。 //快速排序 void swap(int*a, int*b){ int temp = *a; *a = *b; *b = temp; } void quicksort(int *a, int l, int u){ if (l >= u) return; srand(time(NULL)); int j = (rand() % (u - l + 1)) + l; swap(&a[l], &a[j]); int m = a[l]; int index = u + 1; for (int i = u; i >= l; i--) { if (a[i] >= m) swap(&a[i], &a[--index]); } quicksort(a, l, index - 1); quicksort(a, index + 1, u); } //堆排序 vector x; void swap(int *a, int *b){ int temp = *a; *a = *b; *b = temp; } void siftup(int n){ int i, p; for (i = n; i > 1 && x[p = i / 2] > x[i]; i = p) { swap(&x[i],&x[p]); } } void siftdown(int n) { int i, c; for (i = 1; (c = 2 * i) |
【本文地址】
今日新闻 |
推荐新闻 |