java-如何计算快速排序中的比较和交换？

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了java-如何计算快速排序中的比较和交换？，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2956字，纯文字阅读大概需要5分钟。

内容图文

public class IntQuickSorter
{
   public static int numOfComps = 0,
                     numOfSwaps = 0;

    public static void main(String[] args)
   {
      // Create an int array with test values.
      int[] values = { 1, 2, 3, 4, 5,  6 };
      //int[] values = { 5, 1, 3, 6, 4, 2 };
      //int[] values = { 5, 7, 2, 8, 9, 1 };

        System.out.println("\n\nQuick Sort:");

      // Display the array's contents.
      System.out.println("\nOriginal order: ");
      for (int element : values)
         System.out.print(element + " ");

      // Sort the array.
      quickSort(values);

      //System.out.println("\n\nNumber of comps = " + numOfComps);
      //System.out.println("Number of swaps = " + numOfSwaps);

      // Display the array's contents.
      System.out.println("\nSorted order: ");
      for (int element : values)
         System.out.print(element + " ");

      System.out.println();
   }

   public static void quickSort(int array[])
   {
      doQuickSort(array, 0, array.length - 1);
      System.out.println("\n\nNumber of comps = " + numOfComps);
       System.out.println("Number of swaps = " + numOfSwaps);
   }

   private static void doQuickSort(int array[], int start, int end)
   {
      int pivotPoint;

      if (start < end)
      {
         numOfComps++;

         // Get the pivot point.
         pivotPoint = partition(array, start, end);

         // Sort the first sub list.
         doQuickSort(array, start, pivotPoint - 1);

         // Sort the second sub list.
         doQuickSort(array, pivotPoint + 1, end);
      }
   }

   private static int partition(int array[], int start, int end)
   {
      int pivotValue;    // To hold the pivot value
      int endOfLeftList; // Last element in the left sub list.
      int mid;           // To hold the mid-point subscript

      // Find the subscript of the middle element.
      // This will be our pivot value.
      mid = (start + end) / 2;

      // Swap the middle element with the first element.
      // This moves the pivot value to the start of 
      // the list.
      swap(array, start, mid);

      // Save the pivot value for comparisons.
      pivotValue = array[start];

      // For now, the end of the left sub list is
      // the first element.
      endOfLeftList = start;

      // Scan the entire list and move any values that
      // are less than the pivot value to the left
      // sub list.
      for (int scan = start + 1; scan <= end; scan++)
      {

         if (array[scan] < pivotValue)
         {
            endOfLeftList++;
            swap(array, endOfLeftList, scan);

                numOfSwaps ++;
         }
         numOfComps++;
      }

      // Move the pivot value to end of the
      // left sub list.
      swap(array, start, endOfLeftList);

      // Return the subscript of the pivot value.
      return endOfLeftList;
   }

   private static void swap(int[] array, int a, int b)
   {
      int temp;

         temp = array[a];
         array[a] = array[b];
         array[b] = temp;
    }
}

如何用Java编写此quicksort程序的代码,以计算比较次数和交换次数？我现在拥有交换代码的地方,即使使用排序的数字数组也可以计算交换次数,但不应该这样.比较代码是否在正确的位置？谢谢你的帮助.

解决方法:

Where I have the swap code now, it counts swaps even with a sorted array of numbers and it shouldn’t.

那不是很准确.排序后的数组将与quicksort进行一些交换,这就是数据透视和分区的工作方式.这是使用排序列表的典型快速排序的动画. Animation gist

另外,删除此比较：

if (start < end)
      {
         numOfComps++;

因为这不是数组中两件事的“关键比较”,只是索引的“关键比较”.
除此之外,您的比较和交换看起来在正确的位置.

内容总结

以上是互联网集市为您收集整理的java-如何计算快速排序中的比较和交换？全部内容，希望文章能够帮你解决java-如何计算快速排序中的比较和交换？所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---