21xrx.com
2024-12-15 01:05:55 Sunday
登录
文章检索 我的文章 写文章
快速排序算法的Java实现
2023-11-22 21:54:31 深夜i     --     --
快速排序 算法 Java实现 排序 分治算法

快速排序是一种常用的排序算法,利用分治的思想,通过递归的方式将待排序的序列分为两部分,然后对这两部分分别进行排序,最后将两部分合并起来,完成整个排序过程。下面是快速排序算法的Java实现。

首先,我们需要定义一个方法来实现快速排序。该方法需要接收一个待排序的整型数组,以及数组的开始和结束位置作为参数。


public static void quickSort(int[] array, int start, int end) {

  if (start < end) {

    int pivot = partition(array, start, end); // 将数组划分为两部分

    quickSort(array, start, pivot - 1); // 对左子序列进行排序

    quickSort(array, pivot + 1, end); // 对右子序列进行排序

  }

}

在快速排序的过程中,我们需要选择一个基准元素,将数组划分为两部分。基准元素可以是任意一个已存在于数组中的元素,通常选择数组的开始位置或结束位置的元素作为基准。这里我们选择将数组的开始位置的元素作为基准。

接下来,我们需要实现一个方法来划分数组,并返回基准元素的位置。


public static int partition(int[] array, int start, int end) {

  int pivot = array[start]; // 选择开始位置的元素作为基准

  int left = start + 1; // 左指针

  int right = end; // 右指针

  while (left <= right) {

    if (array[left] <= pivot) {

      left++;

    } else if (array[right] >= pivot)

      right--;

    else {

      // 交换左右指针所指向的元素

      int temp = array[left];

      array[left] = array[right];

      array[right] = temp;

      left++;

      right--;

    }

  }

  // 将基准元素与右指针所指向的元素进行交换

  int temp = array[start];

  array[start] = array[right];

  array[right] = temp;

  return right;

}

最后,我们可以使用上述的快速排序方法对一个整型数组进行排序。


public static void main(String[] args) {

  int[] array = 1;

  quickSort(array, 0, array.length - 1);

  System.out.println("排序结果:");

  for (int num : array) {

    System.out.print(num + " ");

  }

}

运行程序后,我们可以看到排序结果为:1 2 3 4 5 6 7 8,证明快速排序算法的实现是正确的。

总结来说,快速排序是一种高效的排序算法,借助分治的思想和递归的方式,可以在平均情况下达到O(nlogn)的时间复杂度。通过上述的Java实现,我们可以轻松地对一个整型数组进行排序。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复