各位早上好，我想弄清大 O 表示法，以便对 5000 个元素的数组进行快速排序。我以随机顺序（200、20、4 等...）、排序顺序（1、2、3、4、5 等...）和反向排序顺序（4999、4998、4997、4996 等）运行快速排序....) 我从中间选择支点。
当我查找 Big O 表示法时，它告诉我，对于快速排序，它是 O (n log n)，这对我来说意味着......当使用 base 2 log 时，O(5000 * 12.287712) = 61438.56，如果使用 base 10 log O(5000 * 3.69897) = 18494.85 所以我假设我会使用 61438.56，当我查看我的输出（发布在下面）时，它几乎不需要那么长时间。
在进行比较时，我只是想了解一下我通常期望从随机顺序、排序顺序和反向排序测试中看到什么。我已经通过我的 java 代码发布了 5 次运行的结果，也许我想多了，或者在错误的地方进行了比较，但我想我会这样做，尽管在不同通道上的比较会有更大的差异。
如有必要，我可以发布我的代码，只是遇到了问题，因为我无法将其缩进 4 个空格，并且不确定是否有自动化的方法来做到这一点。
第一次运行：随机顺序-交换次数 16196 排序顺序-交换次数 18242 反向排序-交换次数 22790
第 2 次运行：随机顺序 - 交换次数 16072 排序顺序 - 交换次数 18118 反向排序 - 交换次数 22666
第 3 次运行：随机顺序 - 交换次数 16205 排序顺序 - 交换次数 18251 反向排序 - 交换次数 22799
第 4 次运行：Random-Order-Number of swaps made 16333 Sorted-Order-Number of swaps made 18379 Reverse-Sorted-Number of swaps made 22927
5th Run: Random-Order-Number of swaps made 16283 Sorted-Order-Number of swaps made 18329 Reverse-Sorted-Number of swaps made 22877
package QuickSort;
import java.util.Random;
public class QuickSortApp
{
/**
* @param args the command line arguments
*/
public static void main(String[] args)
{
// This for loop just runs through the code 20 times.
for(int loop = 0; loop < 20; loop++)
{
// This creates an array with 5000 random numbers
int maxSize = 5000;
ArrayQuickSort arr;
Random rnd = new Random();
arr = new ArrayQuickSort(maxSize);
ArrayQuickSort.setSwapCount(0);
ArrayQuickSort.setMedianCount(0);
for (int j = 0; j < maxSize; j++)
{
int n = rnd.nextInt(50000);
arr.insert(n);
}
// This creates a sorted array to test
ArrayQuickSort arrSorted;
arrSorted = new ArrayQuickSort(maxSize);
ArrayQuickSort.setSwapCount(0);
ArrayQuickSort.setMedianCount(0);
for (int j = 0; j < maxSize; j++)
{
int n = j + 1;
arrSorted.insert(n);
}
// This creates a reverse sorted array for checks
ArrayQuickSort arrReverseSorted;
arrReverseSorted = new ArrayQuickSort(maxSize);
ArrayQuickSort.setSwapCount(0);
ArrayQuickSort.setMedianCount(0);
for (int j = 5000; j > 0; j--)
{
int n = j;
arrReverseSorted.insert(n);
}
arr.quickSort();
System.out.println("Random-Order-Number of swaps made " + ArrayQuickSort.getSwapCount() + " Recursion Count is " + ArrayQuickSort.getMedianCount() );
arrSorted.quickSort();
System.out.println("Sorted-Order-Number of swaps made " + ArrayQuickSort.getSwapCount() + " Recursion Count is " + ArrayQuickSort.getMedianCount());
arrReverseSorted.quickSort();
System.out.println("Reverse-Sorted-Number of swaps made " + ArrayQuickSort.getSwapCount() + " Recursion Count is " + ArrayQuickSort.getMedianCount());
}
}
}
package QuickSort;
public class ArrayQuickSort {
private int[] theArray;
private int nElms;
private static int swapCount=0;
private static int medianCount = 0;
public ArrayQuickSort(int max) {
theArray = new int[max];
nElms = 0;
}
public void insert(int value) {
theArray[nElms] = value;
nElms++;
}
public void display() {
System.out.print("Array = ");
for (int i = 0; i < nElms; i++)
{
System.out.print(theArray[i] + " ");
if(i%25==0)
System.out.println();
}
System.out.println();
}
private void swap(int dx1, int dx2) {
int temp = theArray[dx1];
theArray[dx1] = theArray[dx2];
theArray[dx2] = temp;
swapCount++; // I am counting here to see how many times numbers are swapped.
}
private int medianOf3(int left, int right)
{
int center =(left+right)/2;
if(theArray[left] > theArray[center])
swap(left, center);
if(theArray[left] > theArray[right])
swap(left, right);
if(theArray[center] > theArray[right])
swap(center, right);
swap(center, right);
medianCount++; // I am counting here to see how many times the pivot is changed
return theArray[right];
}
public void quickSort()
{
recQuickSort(0, nElms -1);
}
private void recQuickSort(int left, int right)
{
int size = right-left+1;
if(size < 5)
insertionSort(left, right);
else
{
int median = medianOf3(left, right);
int partition = partitionIt(left, right, median);
recQuickSort(left, partition-1);
recQuickSort(partition+1, right);
}
}
private int partitionIt(int left, int right, int pivot) {
int leftPtr = left - 1;
int rightPtr = right;
while (true) {
while (theArray[++leftPtr] < pivot)
;
while (theArray[--rightPtr] > pivot)
;
if(leftPtr >= rightPtr)
break;
else
swap(leftPtr, rightPtr);
}
swap(leftPtr, right);
return leftPtr;
}
private void insertionSort(int left, int right) {
int in, out;
for (out = left + 1; out <= right; out++) {
int temp = theArray[out];
in = out;
while (in > left && theArray[in - 1] >= temp) {
theArray[in] = theArray[in - 1];
in--;
}
theArray[in] = temp;
}
}
public static int getMedianCount()
{
return medianCount;
}
public static void setMedianCount(int medianCount)
{
ArrayQuickSort.medianCount = medianCount;
}
public static int getSwapCount()
{
return swapCount;
}
public static void setSwapCount(int swapCount)
{
ArrayQuickSort.swapCount = swapCount;
}
}