不正确的QuickSort实现

Question

我正在从Youtube上了解快速排序，并试图实现这个实现，因为在这里，在左标记之前将用1元素交换枢轴。

这是QuickSort算法的伪码。

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}

但是，当我试图对包含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;
}

Answer 2

Selbie回答确实如预期的那样有效，但这并不是我所期待的实现。我在寻找快速排序的版本，其中支点在左标记之前与一个交换，在每次迭代后都会有一个元素就位。

经过多次尝试和错误后，我意识到我原来的算法是有效的，我不知道当我第一次在问题中发布算法时，它为什么不起作用。

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>();


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

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

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



    }


    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);



    }


}