Java快排入门（面试常见问题）

位置：首页>文章>详情分类：教程分享 > Java教程阅读(798) 2024-04-17 12:33:21

快速排序算法是最常用的排序算法之一，尤其是对大型列表/数组进行排序。快速排序是一种分而治之算法，这意味着原始数组被分成两个数组，每个数组单独排序，然后合并排序输出以生成排序数组。平均而言，它具有O（n log n）复杂性，使快速排序适用于对大数据卷进行排序。

用更标准的话来说，快速排序算法通过与元素进行比较，将未排序的部分反复划分为低阶子节和高阶子节。在递归结束时，我们得到排序数组。请注意，快速排序可以用于“就地”排序。这意味着排序在数组中进行，不需要创建其他数组。pivot

快速排序算法

快速排序算法的基本思想可以描述为以下步骤：
如果数组仅包含一个元素或零个元素，则对数组进行排序。如果数组包含多个元素，则：

选择一个元素作为枢轴元素，通常从中间开始，但不是必需的。
数据元素分为两部分：一部分包含比枢轴元素顺序低的元素，另一部分包含比枢轴元素顺序更高的元素。
通过重复步骤 1 和 2 分别对这两个部分进行排序。

快速排序 Java 示例

下面是快速排序 Java 实现示例。

public class QuickSortExample 
{
  public static void main(String[] args) 
  {
    // 下面是一个无序的数组
    Integer[] array = new Integer[] { 12, 13, 24, 10, 3, 6, 90, 70 };
 
    // 使用快排来给他排序
    quickSort( array, 0, array.length - 1 );
 
    // 输出并验证排序结果
    System.out.println(Arrays.toString(array));
  }
 
  public static void quickSort(Integer[] arr, int low, int high) 
  {
    //检查空数组
    if (arr == null || arr.length == 0){
      return;
    }
     
    if (low >= high){
      return;
    }
 
    //从列表中间获取pivot元素
    int middle = low + (high - low) / 2;
    int pivot = arr[middle];
 
    // 让 left < pivot 并且 right > pivot
    int i = low, j = high;
    while (i <= j) 
    {
      //检查左侧数组上的所有值是否低于pivot
      while (arr[i] < pivot) 
      {
        i++;
      }
      //检查直到左侧数组上的所有值都大于pivot
      while (arr[j] > pivot) 
      {
        j--;
      }
      //现在比较列表两边的值，看看它们是否需要交换
      //交换后，在两个列表上移动迭代器
      if (i <= j) 
      {
        swap (arr, i, j);
        i++;
        j--;
      }
    }
    //递归地执行与上面相同的操作以对两个子数组进行排序
    if (low < j){
      quickSort(arr, low, j);
    }
    if (high > i){
      quickSort(arr, i, high);
    }
  }
   
  public static void swap (Integer array[], int x, int y)
    {
    int temp = array[x];
    array[x] = array[y];
    array[y] = temp;
    }
}

执行输出结果：