为什么自己写的排序算法没有数据库的SQL语句排序快速？
事情是这样的：
我将得到的结果写道数组中。
大概有7万-----8万的数据量。
然后利用“冒泡”排序和“快速排序”算法对其排序。
运行速度慢的惊人。
冒泡排序甚至要20多分钟才能完成
甚至快速排序还出现了堆栈溢出的问题。
后来我索性将结果写入Access数据库的表中。
然后利用SQL语句的排序功能对其排序。
结果是。
一条SQL语句不到1秒钟就执行完毕。
速度快的让人不敢想象。
为什么自己写的排序算法没有数据库的SQL语句排序快速？
[解决办法]
Option Explicit
Const ARRAY_SIZE As Long = 100000
Sub Main()
Dim a(ARRAY_SIZE - 1) As Long
Dim dtStart As Date
Dim dtFinish As Date
InitArray a
dtStart = Now
Quicksort a, 0, ARRAY_SIZE - 1
dtFinish = Now
Debug.Print Format(dtFinish - dtStart, "HH:MM:SS")
Debug.Assert IsSorted(a)
End Sub
Private Sub InitArray(a() As Long)
Dim i As Long
For i = 0 To ARRAY_SIZE - 1
a(i) = ARRAY_SIZE - 1 - i
Next
End Sub
Private Function IsSorted(a() As Long) As Boolean
Dim i As Long
For i = 0 To ARRAY_SIZE - 1
If a(i) <> i Then Exit Function
Next
IsSorted = True
End Function
Private Sub Quicksort(a() As Long, ByVal Low As Long, ByVal High As Long)
Dim PivotIndex As Long
Dim i As Long
Dim j As Long
If Low < High Then
If High - Low = 1 Then
If a(Low) > a(High) Then SwapElement a(Low), a(High)
Else
PivotIndex = Low \ 2 + High \ 2
SwapElement a(High), a(PivotIndex)
i = Low: j = High
Do
Do While (i < j) And (a(i) <= a(High))
i = i + 1
Loop
Do While (j > i) And (a(j) >= a(High))
j = j - 1
Loop
If i < j Then SwapElement a(i), a(j)
Loop While i < j
SwapElement a(i), a(High)
If (i - Low) < (High - i) Then
Quicksort a, Low, i - 1
Quicksort a, i + 1, High
Else
Quicksort a, i + 1, High
Quicksort a, Low, i - 1
End If
End If
End If
End Sub
Private Sub SwapElement(v1 As Long, v2 As Long)
Dim tmp As Long
tmp = v1
v1 = v2
v2 = tmp
End Sub
[解决办法]
package heap;
import time.MethodTimeProxy;
public class MaxHeap {
public int heapSize;
public int parent(int i) {
return i / 2;
}
public int left(int i) {
return 2 * i;
}
public int right(int i) {
return 2 * i + 1;
}
public void maxHeapify(int[] a, int i) {
int l = left(i);
int r = right(i);
int largest = i;
if (l < heapSize) {
if (a[l] > a[i]) {
largest = l;
}
}
if (r < heapSize) {
if (a[r] > a[largest]) {
largest = r;
}
}
if (largest != i) {
int temp = a[i];
a[i] = a[largest];
a[largest] = temp;
maxHeapify(a, largest);
}
}
public void buildMaxHeap(int[] a) {
heapSize = a.length;
for (int i = (a.length - 1) / 2; i >= 0; i--) {
maxHeapify(a, i);
}
}
public void heapSort(int[] a) {
buildMaxHeap(a);
for (int i = a.length - 1; i > 0; i--) {
int temp = a[i];
a[i] = a[0];
a[0] = temp;
heapSize = heapSize - 1;
maxHeapify(a, 0);
}
}
public static void main(String[] args) {
MethodTimeProxy proxy = new MethodTimeProxy();
MaxHeap h = new MaxHeap();
int[] a = new int[100000];
int k = 100000;
for(int j=0;j<100000;j++) {
a[j] = k;
k--;
}
long start = System.currentTimeMillis();
h.heapSort(a);
long end = System.currentTimeMillis();
System.out.println(end-start+"ms");
}
}
JDK1.6,堆排序，复杂度o(n*logn),10万条数据我自己的机器80ms左右
