冒泡、选择、插入和快速排序中的交换和比较次数
number of swaps and comparisons in bubble, selection, insertion and quick sorts
我已经实现了Java中的所有四种排序算法。只是为了它，我决定查看每种算法中的交换次数和比较次数。对于大小为 20 的随机数组，这是我的结果
冒泡排序：87 次交换，87 次比较
插入排序：87 次交换，87 次比较
选择排序：19 次交换，29 次比较
快速排序：11940次交换，我什至不知道从哪里算比较
为什么冒泡排序和选择排序相同？我的意思是看代码我几乎可以看到它。循环都差不多，我只是希望有人为我指出它。
我明白为什么选择排序的交换次数最少
快速排序对我来说是个谜（该死的递归）。我认为这就是掉期数量如此之多的原因。为什么我的实施这么慢？其他三个比它早完成。
***** 代码 - 如果缺少任何内容请告诉我 *******
Swap 对于所有三个实现都是相同的
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 来执行和计数操作：
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);
}
}
修改您的代码足以使用该检测 class 来计算操作，我得到这些结果：
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 次交换（恰好 n - 其中 1 次，如果你执行和计算自交换）。
然后是快速排序。显然它不是很快——它有一些非常错误的地方。更多的仪器告诉我它下降到 far 递归深度太大（平均大约 400，而它不应超过 n 即使在最坏的情况下）。问题在于您的随机枢轴选择。不是从正在排序的子数组中选择一个枢轴，而是从整个数组中选择它。要解决此问题，请替换
int randomIndex = new Random().nextInt(array.length);
和
int randomIndex = left + new Random().nextInt(right + 1 - left);
这应该会给您带来更有利的比较和交换计数，但是在您开始对更大的数组进行排序之前，您不会真正注意到快速排序相对于其他排序有多大优势。
您可以做更多的事情来改进您的 QuickSort 实施，但我没有看到任何其他 真正的 错误。
我已经实现了Java中的所有四种排序算法。只是为了它，我决定查看每种算法中的交换次数和比较次数。对于大小为 20 的随机数组，这是我的结果
冒泡排序：87 次交换，87 次比较
插入排序：87 次交换，87 次比较
选择排序：19 次交换，29 次比较
快速排序：11940次交换，我什至不知道从哪里算比较
为什么冒泡排序和选择排序相同？我的意思是看代码我几乎可以看到它。循环都差不多，我只是希望有人为我指出它。
我明白为什么选择排序的交换次数最少
快速排序对我来说是个谜（该死的递归）。我认为这就是掉期数量如此之多的原因。为什么我的实施这么慢？其他三个比它早完成。
***** 代码 - 如果缺少任何内容请告诉我 *******
Swap 对于所有三个实现都是相同的
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 来执行和计数操作：
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);
}
}
修改您的代码足以使用该检测 class 来计算操作，我得到这些结果：
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 次交换（恰好 n - 其中 1 次，如果你执行和计算自交换）。
然后是快速排序。显然它不是很快——它有一些非常错误的地方。更多的仪器告诉我它下降到 far 递归深度太大（平均大约 400，而它不应超过 n 即使在最坏的情况下）。问题在于您的随机枢轴选择。不是从正在排序的子数组中选择一个枢轴，而是从整个数组中选择它。要解决此问题，请替换
int randomIndex = new Random().nextInt(array.length);
和
int randomIndex = left + new Random().nextInt(right + 1 - left);
这应该会给您带来更有利的比较和交换计数，但是在您开始对更大的数组进行排序之前，您不会真正注意到快速排序相对于其他排序有多大优势。
您可以做更多的事情来改进您的 QuickSort 实施，但我没有看到任何其他 真正的 错误。