1. 冒泡排序
/**
* 冒泡排序
*/
private void bubbleSort(int[] arr) {
for (int i = arr.length; i > 0; i--) {
for (int j = arr.length - 1; j > arr.length - i; j--) {
if (arr[j] < arr[j - 1]) {
int temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
}
}
}
}
2. 快速排序
/**
* 快速排序
*/
private void qSort(int[] arr, int head, int tail) {
if (arr == null || head >= tail || arr.length == 0) {
return;
}
int i = head, j = tail, q = arr[(i + j) / 2];
while (i < j) {
while (arr[i] < q) {
++i;
}
while (arr[j] > q) {
--j;
}
if (i < j) {
int temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
++i;
--j;
} else if (i == j) {
++i;
}
}
qSort(arr, head, j);
qSort(arr, i, tail);
}3. 归并排序
static void merge_sort_recursive(int[] arr, int[] result, int start, int end) {
if (start >= end)
return;
int len = end - start, mid = (len >> 1) + start;
int start1 = start, end1 = mid;
int start2 = mid + 1, end2 = end;
merge_sort_recursive(arr, result, start1, end1);
merge_sort_recursive(arr, result, start2, end2);
int k = start;
while (start1 <= end1 && start2 <= end2)
result[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
while (start1 <= end1)
result[k++] = arr[start1++];
while (start2 <= end2)
result[k++] = arr[start2++];
for (k = start; k <= end; k++)
arr[k] = result[k];
}
public static void merge_sort(int[] arr) {
int len = arr.length;
int[] result = new int[len];
merge_sort_recursive(arr, result, 0, len - 1);
}4. 测试代码
@Test
public void testSpeed(){
Random random = new Random();
int arrs[] = new int[30000];
for (int i = 0; i < arrs.length; i++) {
arrs[i] = random.nextInt(10000);
}
int[] arrs2 = arrs.clone();
int[] arrs3 = arrs.clone();
int[] arrs4 = arrs.clone();
long start = System.currentTimeMillis();
bubbleSort(arrs);
long end1 = System.currentTimeMillis();
log.info("冒泡排序 time:{}ms",(end1-start));
qSort(arrs2,0,arrs2.length-1);
long end2 = System.currentTimeMillis();
log.info("快速排序 time:{}ms",(end2-end1));
merge_sort(arrs3);
long end3 = System.currentTimeMillis();
log.info("归并排序 time:{}ms",(end3-end2));
Arrays.sort(arrs4);
long end4 = System.currentTimeMillis();
log.info("java.util排序 time:{}ms",(end4-end3));
}5. 测试结果
当数组长度60000时
15:35:28.609 [main] INFO com.zhiyis.framework.learn.sort.testSort - 冒泡排序 time:8497ms
15:35:28.645 [main] INFO com.zhiyis.framework.learn.sort.testSort - 快速排序 time:40ms
15:35:28.669 [main] INFO com.zhiyis.framework.learn.sort.testSort - 归并排序 time:24ms
15:35:28.696 [main] INFO com.zhiyis.framework.learn.sort.testSort - java.util排序 time:27ms当数组长度30000时
15:34:48.389 [main] INFO com.zhiyis.framework.learn.sort.testSort - 冒泡排序 time:2727ms
15:34:48.403 [main] INFO com.zhiyis.framework.learn.sort.testSort - 快速排序 time:18ms
15:34:48.418 [main] INFO com.zhiyis.framework.learn.sort.testSort - 归并排序 time:15ms
15:34:48.428 [main] INFO com.zhiyis.framework.learn.sort.testSort - java.util排序 time:10ms当数组长度3000时
15:33:52.156 [main] INFO com.zhiyis.framework.learn.sort.testSort - 冒泡排序 time:22ms
15:33:52.167 [main] INFO com.zhiyis.framework.learn.sort.testSort - 快速排序 time:21ms
15:33:52.171 [main] INFO com.zhiyis.framework.learn.sort.testSort - 归并排序 time:4ms
15:33:52.183 [main] INFO com.zhiyis.framework.learn.sort.testSort - java.util排序 time:12ms当数组长度300时
15:33:34.345 [main] INFO com.zhiyis.framework.learn.sort.testSort - 冒泡排序 time:3ms
15:33:34.356 [main] INFO com.zhiyis.framework.learn.sort.testSort - 快速排序 time:17ms
15:33:34.357 [main] INFO com.zhiyis.framework.learn.sort.testSort - 归并排序 time:1ms
15:33:34.357 [main] INFO com.zhiyis.framework.learn.sort.testSort - java.util排序 time:0ms当数组长度30时
15:33:07.920 [main] INFO com.zhiyis.framework.learn.sort.testSort - 冒泡排序 time:0ms
15:33:07.933 [main] INFO com.zhiyis.framework.learn.sort.testSort - 快速排序 time:21ms
15:33:07.933 [main] INFO com.zhiyis.framework.learn.sort.testSort - 归并排序 time:0ms
15:33:07.934 [main] INFO com.zhiyis.framework.learn.sort.testSort - java.util排序 time:1ms6. 总结
我的测试有什么变量控制问题可以提出来
冒泡排序的时间复杂度最好是O(N)，平均和最差O(N^2)；快速排序最好Nlog_2 N，平均也是Nlog_2 N，最差N^2；归并排序最好平均和最差都是Nlog_2 N。根据算法时间复杂度看，归并排序最稳定
根据实验结果看，在排序数量比较少的情况下冒泡排序效率也还可以，但一旦排序数量多了，还是快速和归并效率较高。当然我们往往就用java默认提供给我们的工具类就可以了，不用自己写算法，效率不比归并差。
---------------END----------------
后续的内容同样精彩
长按关注“IT实战联盟”哦
注意：本文归作者所有，未经作者允许，不得转载
