1468848854
最后一篇排序算法，快速排序，该算法基本思想是这样
1．先从数列中取出一个数作为基准数。
2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
3．再对左右区间重复第二步，直到各区间只有一个数。如图
Java核心代码实现
static void qsort(int[] array, int left, int right) {
if (left < right) {
// 每次一最左变的为基数t
int t = array[left], i = left, j = right;
// 从当前段右边开始找比t大的数
while (i < j && array[j] >= t)
j–;
// 找到比t大的数
if (i < j)
array[i++] = array[j];
// 从当前段左边开始找比t小的数
while (i < j && array[i] < t)
i++;
// 找到比t小的数
if (i < j)
array[j–] = array[i];
// 已经找到了t的位置
array[i] = t;
// 从右边开始找
qsort(array, left, right - 1);
// 从左边开始找
qsort(array, left + 1, right);
}
下面是几个排序算法的效率进行比较
单位ms（毫秒），每次生成的是0-1000的随机数，所以取的是运行10次的平均值，可以看出效率最高是的归并排序，什么冒泡插入就不列举了，还有就是快排在100个数据的时候感觉就要挂了，竟然运行了2000000+ms
排序数目 归并排序 希尔排序 堆排 Java的Arrays类自带排序
100 0ms 0ms 0ms 0ms
1000 2ms
10ms 16ms 1ms
10000 13ms 107ms 100ms 11ms
50000 16ms 3300ms 900ms 28ms
100000 21ms 9720ms 1887ms 41ms