我已经在Java中实现了所有四种排序算法。只是为此，我决定查看每种算法中的掉期数量和比较数量。对于20尺寸的随机数组，这是我的结果
气泡排序：87个交换，87个比较
插入排序：87个交换，87个比较
选择排序：19个掉期，29比较
快速排序：11940交换，我什至不知道在哪里计算
的比较为什么气泡排序和选择排序相同？我的意思是查看我几乎可以看到的代码。循环几乎是一样的，我只是想有人为我指出。
我可以看到为什么选择排序的交换数量最少
快速排序对我来说是个谜（该死的递归）。我认为这就是为什么掉期数量疯狂的原因。为什么我的实施这么慢？其他三个完成方式。
*****代码 - 让我知道是否缺少任何东西*******
交换对于所有三个实施
均为互换private void swap(int firstIndex, int secondIndex) {
int temp = array[firstIndex];
array[firstIndex] = array[secondIndex];
array[secondIndex] = temp;
}
气泡
public void sort() {
for(int out = nElements-1; out > 1; out--) {// outer backwards loop
for(int in = 0; in < out; in++) { // inner forward loop
if(array[in] > array[in+1]) {
swap(in, in + 1);
totalSwaps++;
totalComparisons++;
}
}
}
}
选择
public void sort() {
for (int i = 0; i < nElements-1; i++) {
int currentMinIndex = i;
for (int j = i + 1; j < nElements; j++)
if (array[j] < array[currentMinIndex]) {
currentMinIndex = j;
totalComparisons++;
}
swap(i, currentMinIndex);
totalSwaps++;
}
}
插入
public void sort() {
for(int i = 1; i < nElements; i++) {
for(int j = i; j > 0; j--) {
if(array[j] < array[j-1]) {
swap(j, j - 1);
totalSwaps++;
totalComparisons++;
}
}
}
}
快速排序
public void sort() {
sort(this.array, 0, array.length - 1);
}
private void sort(int[] array, int left, int right) {
if(left >= right)
return;
int randomIndex = new Random().nextInt(array.length);
int pivot = array[randomIndex];
// returns the dividing point between the left side and the right side
int index = partition(array, left, right, pivot);
sort(array, left, index - 1);
sort(array, index, right);
}
private int partition(int[] array, int left, int right, int pivot) {
while(left <= right) {
while(array[left] < pivot) // will break when there's an element to the left of the pivot that's greater
left++;
while(array[right] > pivot) // breaks when there's an element to the right of the pivot that's less
right--;
if(left <= right) {
swap(left, right);
left++;
right--;
totalSwaps++;
}
}
return left; // left will be at the partition point
}
主
import java.util.Random;
public class Sorting {
private static final int maxSize = 50;
private static int[] randomArray() {
int[] array = new int[maxSize];
Random random = new Random();
random.setSeed(0);
for(int i = 0; i < maxSize; i++)
array[i] = random.nextInt(50);
return array;
}
public static void main(String[] args) {
int[] randomArr = randomArray();
BubbleSort bubbleSort = new BubbleSort(randomArr);
bubbleSort.display();
bubbleSort.sort();
bubbleSort.display();
randomArr = randomArray();
SelectionSort selectionSort = new SelectionSort(randomArr);
selectionSort.sort();
selectionSort.display();
randomArr = randomArray();
InsertionSort insertionSort = new InsertionSort(randomArr);
insertionSort.sort();
insertionSort.display();
System.out.println("Bubble Sort: Swaps = " + bubbleSort.totalSwaps + " Comparisons = " + bubbleSort.totalComparisons);
System.out.println("Selection Sort: Swaps = " + selectionSort.totalSwaps + " Comparisons = " + selectionSort.totalComparisons);
System.out.println("Insertion Sort: Swaps = " + insertionSort.totalSwaps + " Comparisons = " + insertionSort.totalComparisons);
randomArr = randomArray();
QuickSort quickSort = new QuickSort(randomArr);
quickSort.sort();
quickSort.display();
System.out.println("Quick Sort: Swaps = " + quickSort.totalSwaps);
}
}
输出
10 48 29 47 15 3 41 11 19 4 27 27 23 12 45 44 34 25 41 20 // original
3 4 10 11 12 15 19 20 23 25 27 27 29 34 41 41 44 45 47 48 // bubble
3 4 10 11 12 15 19 20 23 25 27 27 29 34 41 41 44 45 47 48 // selection
3 4 10 11 12 15 19 20 23 25 27 27 29 34 41 41 44 45 47 48 // insertion
Bubble Sort: Swaps = 87 Comparisons = 87
Selection Sort: Swaps = 19 Comparisons = 29
Insertion Sort: Swaps = 87 Comparisons = 87
3 4 10 11 12 15 19 20 23 25 27 27 29 34 41 41 44 45 47 48 // quick
Quick Sort: Swaps = 25283
关于如何计数操作，您总是可以考虑添加一层间接。例如，使用此类类以执行和计数操作：
class Instrumentation {
int compares = 0;
int swaps = 0;
boolean compareLess(int left, int right) {
compares++;
return left < right;
}
boolean compareGreater(int left, int right) {
compares++;
return left > right;
}
void swap(int[] array, int index1, int index2) {
int temp = array[index1];
array[index1] = array[index2];
array[index2] = temp;
swaps++;
}
void printResult(String label) {
System.out.print(label);
System.out.print(": Swaps = ");
System.out.print(swaps);
System.out.print(" Comparisons = ");
System.out.println(compares);
}
}
修改了您的代码足以使用该仪器类来计数操作，我得到了这些结果：
Original data:
10 48 29 47 15 3 41 11 19 4 27 27 23 12 45 44 34 25 41 20
BubbleSort: Swaps = 87 Comparisons = 189
3 4 10 11 12 15 19 20 23 25 27 27 29 34 41 41 44 45 47 48
SelectionSort: Swaps = 19 Comparisons = 190
3 4 10 11 12 15 19 20 23 25 27 27 29 34 41 41 44 45 47 48
InsertionSort: Swaps = 87 Comparisons = 190
3 4 10 11 12 15 19 20 23 25 27 27 29 34 41 41 44 45 47 48
QuickSort: Swaps = 3221 Comparisons = 110575
3 4 10 11 12 15 19 20 23 25 27 27 29 34 41 41 44 45 47 48
现在观察到比较的主要特征是在最坏的情况下，它们涉及将每个元素与其他每个元素进行比较。对于20个元素，这是20 * 19/2 = 190比较，这基本上是您的比较 - 选项实现在每种情况下都会产生的（较少用于泡泡排序）。
实际上，在每种情况下，您对气泡和选择排序的期望，但是不是在平均情况下插入的期望。这是因为您的插入排序实现存在缺陷：这种前提是它依赖于其中间结果（将数组的第一部分放在顺序中）来减少所需的比较数量。内部循环中的比较第一次失败，因此无需互换，您应该从（内部）环中断出来，因为您知道在外部循环的下一次迭代之前，不需要进一步的互换。实施将比较数减少为105的特定数据。
比较类别之间的互换数量也很有意义：气泡排序和插入排序将每个元素通过具有相邻元素的一系列互换移动到最终位置。确实，您的实现实际上是彼此镜像的图像。但是，我不准备超越这只手来挥舞着实际的证据。
对于选择排序，是的，对于排序 n 元素，它总是执行（ n *（ n - 1））/2比较，最多可达 n -1换次（如果您执行并计数自swaps，则完全 n - 1个。
，然后是您的快速排序。显然，这不是很快 - 它有很大的问题。更多的仪器告诉我，它降至 far 太大的递归深度（平均约400个，而即使在最坏的情况下，它也不应超过 n ）。问题在于您的随机枢轴选择。您没有从整个数组中选择它的子阵列中选择一个枢轴。要解决这个问题，请更换
int randomIndex = new Random().nextInt(array.length);
int randomIndex = left + new Random().nextInt(right + 1 - left);
应该为您提供比较和掉期的更有利计数，但是您不会真正注意到快速排序比其他优势提供了多少优势，直到您开始对更大的数组进行分类为止。
您还可以做更多的事情来改善您的QuickSort实现，但是我看不到任何其他 bona fide 错误。