Java迭代快速排序程序

在本程序中，我们将使用Java对整数数组进行迭代快速排序。程序使用迭代方法而不是递归方法，并使用辅助栈来管理排序过程。输出将在应用快速排序算法后显示排序后的数组。

问题陈述

编写一个Java程序，使用迭代快速排序方法对整数数组进行排序。以下是演示 -

输入

{34, 76, 41, 32, 11, 0, 91, 102, -11}

输出

After iteratively performing quick sort, the array is
-11 0 11 32 34 41 76 91 102

迭代快速排序步骤

以下是迭代快速排序的步骤 -

  • 定义一个名为Demo的类，其中包含用于交换值、对数组进行分区以及执行迭代快速排序的方法。
  • 在quick_sort方法中使用while循环来处理来自栈的子数组索引。
  • 使用if语句将子数组索引推入栈中以进行进一步分区。
  • 在主方法中，创建Demo的实例，初始化数组，并调用quick_sort方法。
  • 打印排序后的数组。

Learn Java in-depth with real-world projects through our Java certification course. Enroll and become a certified expert to boost your career.

Java迭代快速排序程序

以下是迭代快速排序的Java程序 -

Open Compiler
public class Demo{
   void swap_vals(int arr[], int i, int j){
      int temp = arr[i];
      arr[i] = arr[j];
      arr[j] = temp;
   }
   int partition(int arr[], int l, int h){
      int x = arr[h];
      int i = (l - 1);
      for (int j = l; j <= h - 1; j++){
         if (arr[j] <= x){
            i++;
            swap_vals(arr, i, j);
         }
      }
      swap_vals(arr, i + 1, h);
      return (i + 1);
   }
   void quick_sort(int arr[], int l, int h){
      int my_list[] = new int[h - l + 1];
      int top = -1;
      my_list[++top] = l;
      my_list[++top] = h;
      while (top >= 0){
         h = my_list[top--];
         l = my_list[top--];
         int p = partition(arr, l, h);
         if (p - 1 > l){
            my_list[++top] = l;
            my_list[++top] = p - 1;
         }  
         if (p + 1 < h){
            my_list[++top] = p + 1;
            my_list[++top] = h;
         }
      }
   }
   public static void main(String args[]){
      Demo my_ob = new Demo();
      int my_arr[] = { 34, 76, 41, 32, 11, 0 , 91, 102, -11};
      my_ob.quick_sort(my_arr, 0, my_arr.length - 1);
      int i;
      System.out.println("After iteratively performing quick sort, the array is ");
      for (i = 0; i < my_arr.length; ++i)
      System.out.print(my_arr[i] + " ");
   }
}

输出

After iteratively performing quick sort, the array is
-11 0 11 32 34 41 76 91 102

代码说明

名为Demo的类包含3个函数，'swap_vals'用于使用临时变量交换值，'partition'函数根据枢纽值将数组分成两半，以及'quick_sort'函数，该函数使用枢纽值并基于此值对数组中的值进行排序。

在主函数中，创建了Demo类的实例以及一个数组。在该数组上调用'quick_sort'函数，并在控制台上显示输出。

更新于: 2024年11月18日

645 次浏览

开启你的职业生涯

通过完成课程获得认证

开始学习
广告