干净利落地快速排序

Question

我离开编程和科技产业已经有一段时间了。我想我应该看看并尝试一些老的基本的东西。我浏览了QuickSort，发现它的大多数现有实现，无论是在文本中还是在网络上，都有点复杂。因此，我试图简化实现，使之更符合算法的精神。告诉我你的想法。

设计理念:我用排序产生的' vibe‘来解释/实现Bubble排序，以及用它的'vibe’快速排序:将算法直接解释为代码的氛围。如前所述，这就是我在实现中描述快速排序的方式，而不是“高”或“低”，而是真正地提炼到我所看到的内容:一种排序算法，根据其余的值是小于还是大于支点，将其余的元素分解成两个列表，并递归地重复这个过程。我希望避免通常可用的代码‘感觉’与算法的本质脱节。

package com.progint;

import java.util.ArrayList;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.security.SecureRandom;


public class QuickSortenDine {

  private ArrayList<Integer> listToSort;
  private ArrayList<Integer> sortedList;
  private SecureRandom pivotPicker; /*We're going to pick a Random pivot*/
    
  public QuickSortenDine() {
      listToSort =  new ArrayList<Integer>();
      sortedList = new ArrayList<Integer>();
      pivotPicker = new SecureRandom();
  }
  
  void quickSort() {
      quickSort(listToSort);
  }
  
  void quickSort(ArrayList<Integer> currentList) {
      int listSize = currentList.size();
      if (listSize == 1) sortedList.add(currentList.get(0));
      if (listSize <= 1) return;
      int low = 0 , high = listSize;
      int pivot = pivotPicker.nextInt(listSize);

      ArrayList<Integer>  lowerList = new ArrayList<Integer>();
      ArrayList<Integer>  higherList = new ArrayList<Integer>();
      int pivotValue = currentList.get(pivot);
      
      int currentIndex = low;
      while (currentIndex < high) {
          if (currentIndex == pivot) {currentIndex++; continue;}
          int currentElement = currentList.get(currentIndex++);
          if (currentElement < pivotValue) {lowerList.add(currentElement);}
          else/************* > **********/ {higherList.add(currentElement);}
      }
      quickSort(lowerList); sortedList.add(pivotValue); quickSort(higherList); 
  }
  
  public void readListToBeSorted() throws IOException {
      int len;
      BufferedReader consoleReader = new BufferedReader(new InputStreamReader(System.in));
      System.out.println("Enter the size of the List: ");
      len = Integer.parseInt(consoleReader.readLine());
      if (len<=0) {System.out.println("\nQuitting"); System.exit(0);}
      System.out.println("Enter the numbers: ");
      for (int i=0; i<len; i++) {
          int number;
          try {
              number = Integer.parseInt(consoleReader.readLine());
          }
          catch (NumberFormatException ne) {
              System.out.println("\nEnter Numbers Only\n");
              i--;
              continue;
          }
          listToSort.add(number);
          System.out.println();
      }  
  }
  
  void printList() {
      for (int i=0; i<sortedList.size(); i++) {
          System.out.print(sortedList.get(i));
          if (i==sortedList.size()-1) continue;
          else System.out.print(",");
      }
  }
  
  public static void main(String args[]) throws IOException {
      QuickSortenDine quickEn = new QuickSortenDine();
      quickEn.readListToBeSorted();
      System.out.println("\nQuick Sorting...");
      quickEn.quickSort();
      quickEn.printList();
  }
}

Answer 1

该算法的“精神”是一个主观的观点，因此不能作为评价的坚实标准。因此，我将完全忽略这一方面。

首先，该算法由于不必要的内存分配而死亡。我从未见过没有在给定输入列表中执行其修改的快速排序。如果有4个元素的源数据，则算法创建7个临时ArrayList对象，每个对象分配一个Integer[]对象。您创建的ArrayLists中没有一个具有预定义的初始大小，因此，如果您有大量数据，并且子列表超过16个元素(这个数字随实现而异)，那么您最终也会重新分配和复制数据。对于几百个元素来说，这是不明显的，但是如果您有数百万个元素，则分配会显著降低性能。调查java.util.Collections.swap(List, int, int)。

您应该将算法实现为一个使用泛型类型的可重用库，这样它就可以接受任何List<T>，并将比较实现委托给类似地提供的Comparator<T>。类似于：

public class QuickSort {
    public static <T> void sort(List<T> list, Comparator<T> comparator) {
        ...
    }
}

您应该决定是否要在单行if-语句中使用大括号，并坚持使用。代码应该在风格上是一致的，这样读代码的人就不需要每隔几行就调整自己以适应新的缩进样式。我建议您使用“始终使用大括号”，因为如果代码块中有多行代码，则没有特殊情况，但这是个人偏好。无论你做什么决定，都不要这样做：

if (currentElement < pivotValue) {lowerList.add(currentElement);}

它不会提高代码的可读性，而且违背了所有常见的Java编码约定。

不要试图通过在一行上放置多个语句来压缩代码。对于太长的方法来说，这是一个代码嗅觉。而且，由于它不遵循任何常见的编码约定，因此很难阅读。

Answer 2

考虑到算法的名称引用了速度，我认为任何忽略重要性能因素的方法都非常违背算法的“精神”。因此，您绝对不应该不必要地创建额外的列表并将列表元素复制到它们中。为了正确地实现快速排序，必须按照算法的精神，以高性能的方式进行排序。为此，方法的递归部分必须将List中要排序的区域的索引边界作为参数，而不是单独构建的List。由于这些多余的性能耗尽子列表副本也是将List本身包含在参数中的唯一原因，所以List不应该是一个方法参数。

因此，排序方法的签名应该是void quickSort(int low, int high)。

将列表分成几个部分是正确的，方法是从列表两端的一对空区域开始，然后将这些区域扩展到它们在枢轴处相遇。这些区域严格地是概念性的，而不是单独的列表，只有在增长时跟踪它们的边界索引才能在代码中跟踪它们。

从概念上讲，这些区域是通过以下算法生长的：

1. 每个区域：
   1. 检查区域边界上的元素。如果它属于该区域，则移动边界以包括它。
   2. 重复，直到在区域边界找到不属于该区域的元素。

2. 如果区域边界已经满足，那么你就完成了支点和分离，是时候恢复了。
3. 否则，在每个区域的边界上找到各自属于另一个区域的元素后，交换这两个元素。然后循环回步骤1。

Answer 3

排序泛型列表

在我看来，用比较器对一个泛型类型的列表进行排序，更符合算法的精神。这是一个ArrayList实现的接口。

特别是，这使您可以将原始ArrayList分割为两个subList并对它们进行递归。这将极大地提高您的性能，因为subList返回一个视图而不是复制元素。