java - 快速排序的错误实现

Question

我正在了解 Quick Sort来自 Youtube，我正在尝试实现如图所示的实现，其中枢轴将与左标记之前的 1 个元素交换

这是快速排序算法的伪代码

Method
Divide-and-conquer
Pick an element (pivot) from the list
Pivot is arbitrarily chosen
Normally, the first element is selected
Partition the list into two halves such that:
All the elements in the first half is smaller than the pivot
All the elements in the second half is greater than the pivot
After the rearrangement, the pivot element (pivot) occupies a proper position in a sorting of the list.
Recursively
Quick-sort the 1st half
Quick-sort the 2nd half

Java 代码

import java.io.File;
import java.io.FileNotFoundException;
import java.util.*;



public class QuickSort 
{
    public static void main(String args[])
    {
        Vector<Integer> container = new Vector<Integer>();

        String userinput = "data1.txt";
        Scanner myScanner = new Scanner("foo"); // variable used to read file

        try
        {
            //open filename

            File inputfile = new File("C:\\Users\\8382c\\workspace\\AdvanceAlgorithmA3_Quicksort\\src\\" + userinput);
             myScanner = new Scanner(inputfile);

        }
        catch(FileNotFoundException e)
        {
            System.out.println("File cant be found");
        }


         String line = myScanner.nextLine(); //read 1st line which contains the number of numbers to be sorted

         while(myScanner.hasNext())
         {
             container.add(myScanner.nextInt());
         }


        System.out.println(line);

        /*container.add(7);
        container.add(2);
        container.add(3);
        container.add(4);
        container.add(8);
        container.add(6);
        container.add(8);
        container.add(9);*/

        quickSort(container,0,7);

        for (int i =0;i<container.size();i++)
        {
            System.out.println(container.get(i));
        }

        //http://www.algolist.net/Algorithms/Sorting/Quicksort




    }


    public static int partition(Vector<Integer> container, int left, int right)
    {
          int i = left, j = right;
          int tmp;


          int pivot = container.get(left);

          i++;

          while (i <= j) 
          {
                while ( container.get(i) < pivot)
                      i++;
                while ( container.get(j) > pivot)
                      j--;
                if (i <= j) 
                {
                      tmp =  container.get(i);

                      container.set(i, container.get(j));
                      container.set(j, tmp);

                      i++;
                      j--;
                }
          };

          tmp = container.get(left);

          container.set(left, container.get(i-1));
          container.set(i-1, tmp);

          return i-1;
    }

    public static void quickSort(Vector<Integer> container, int left, int right) 
    {
          int index = partition(container, left, right);
          if (left < index - 1)
                quickSort(container, left, index - 1);
          if (index+1 < right)
                quickSort(container, index+1, right);
    }


}

该算法适用于以下数字:{7,23,4,8,6,8,9}

但是，当我尝试对 text file 进行排序时，它不起作用其中包含 10000 个数字

我在算法中做错了什么？？？

Answer 1

已更新

首先，这个声明:

quickSort(container,0,7);

应该阅读:

quickSort(container,0,container.size()-1);

我不确定这是否是问题所在。现在让我们清理您的代码。

您的核心职能:

public static void quickSort(Vector<Integer> container, int left, int right) 
{
      int index = partition(container, left, right);
      if (left < index - 1)
            quickSort(container, left, index - 1);
      if (index+1 < right)
            quickSort(container, index+1, right);
}

在索引加/减 1 方面似乎存在差一错误。这看起来更合适:

public static void quickSort(Vector<Integer> container, int left, int right) 
{
      if (left < right)
      {
          int index = partition(container, left, right);
          quickSort(container, left, index);
          quickSort(container, index+1, right);
      }
}

你的分区函数也需要一些清理。我第一次发帖的时候就搞砸了。现在我测试了它，我知道它可以工作。

public static int partition(Vector<Integer> container, int left, int right)
{
      int i = left-1;
      int j = right+1;

      int pivot = container.get(left);

      while (true) 
      {
          do
          {
              i++;
          } while (container.get(i) < pivot);

          do
          {
              j--;
          } while (container.get(j) > pivot);

          if (i < j) 
          {
                int tmp =  container.get(i);
                container.set(i, container.get(j));
                container.set(j, tmp);
          }
          else
          {
              break;
          }
      };
      return j;
}