（5）排序算法——快速排序

野性酷女 2022-07-29 09:02 59阅读 0赞

快速排序的时间复杂度为O(n\*logn)，空间复杂度比合并排序的小。

public class QuickSort { 
      public static void quickSort(int[] list) {
        quickSort(list, 0, list.length - 1);
      }
    
      private static void quickSort(int[] list, int first, int last) {
        if (last > first) {
          int pivotIndex = partition(list, first, last);
          quickSort(list, first, pivotIndex - 1);
          quickSort(list, pivotIndex + 1, last);
        }
      }
    
      /** Partition the array list[first..last] */
      private static int partition(int[] list, int first, int last) {
        int pivot = list[first]; // Choose the first element as the pivot
        int low = first + 1; // Index for forward search
        int high = last; // Index for backward search
    
        while (high > low) {
          // Search forward from left
          while (low <= high && list[low] <= pivot)
            low++;
    
          // Search backward from right
          while (low <= high && list[high] > pivot)
            high--;
    
          // Swap two elements in the list
          if (high > low) {
            int temp = list[high];
            list[high] = list[low];
            list[low] = temp;
          }
        }
    
        while (high > first && list[high] >= pivot)
          high--;
    
        // Swap pivot with list[high]
        if (pivot > list[high]) {
          list[first] = list[high];
          list[high] = pivot;
          return high;
        }
        else {
          return first;
        }
      }
    
      /** A test method */
      public static void main(String[] args) {
        int[] list = {
       2, 3, 2, 5, 6, 1, -2, 3, 14, 12};
        quickSort(list);
        for (int i = 0; i < list.length; i++)
          System.out.print(list[i] + " ");
      }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，59人围观）

还没有评论，来说两句吧...

相关阅读

相关算法|5.快速排序相关

算法|5.快速排序相关 1.荷兰国旗问题题意：给定一个数组arr，以arr\[R\]为划分值，请把arr\[R\]的数放在数组的左边，等于arr\[R\]的数放在

超、凢脫俗/ 2024年03月16日 09:27/ 0 赞/ 14 阅读

相关【排序算法】- 快速排序

文章目录 1 快速排序法介绍: 2 快速排序法示意图: 3 快速排序法应用实例: 1 快速排序法介绍: 快速排序（Quicksort）是对`冒泡

桃扇骨/ 2022年12月20日 06:04/ 0 赞/ 247 阅读

相关排序算法——快速排序

排序算法——快速排序 > 快速排序通过一趟排序将待排序序列分隔成独立的两部分，其中一部分序列的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个

你的名字/ 2022年11月20日 08:04/ 0 赞/ 282 阅读

相关（5）排序算法——快速排序

快速排序的时间复杂度为O(n\logn)，空间复杂度比合并排序的小。 public class QuickSort { public static vo

野性酷女/ 2022年07月29日 09:02/ 0 赞/ 60 阅读

相关算法——排序——快速排序

快速排序： 1.原地排序 2.O(nlogn)（最坏O(n^2) 这也是严重缺点之一） 3.要尽量保证输入的元素是基本无序的，因为在有序情况下，其时间复杂度是O(n^2)

朴灿烈づ我的快乐病毒、/ 2022年07月27日 11:50/ 0 赞/ 252 阅读

相关排序算法——快速排序

前言快速排序采用了分治法，即将原问题划分成为若干个规模更小且与原问题相似的子问题，然后递归地解决这些子问题，最后将他们组合起来。快速排序的思想是：假设数据元素存放在

淡淡的烟草味﹌/ 2022年06月12日 00:20/ 0 赞/ 355 阅读

相关排序算法-快速排序

快速排序是最高效、不占用空间的一种排序算法快排的精髓是在于找到中间基数。比中间基数小的放在左边，比中间基数大的放在右边然后左右各自进行快排。参考

蔚落/ 2022年06月01日 06:17/ 0 赞/ 308 阅读

相关排序算法-快速排序

quick sorting(快速排序) \\理论：\\在一组需要被排序的数中，以第一个数位基数，将小与它的数排它左边，大于它的数排右边，这样给这个基数排好位置，左边又是一

一时失言乱红尘/ 2022年05月28日 07:05/ 0 赞/ 341 阅读

相关排序算法：快速排序

一、前言快速排序是一种交换排序，它由C. A. R. Hoare在1962年提出。 -------------------- 二、算法思想快

我不是女神ヾ/ 2022年04月05日 14:00/ 0 赞/ 404 阅读

相关排序算法---快速排序

基本思路：快速排序，数组冲两边出发。首先取一个关键字。在第一次排序后。大于和小于关键字的各在关键字两边。然后在对两边重复上面步骤，取关键字，排序。直

电玩女神/ 2022年03月11日 04:47/ 0 赞/ 352 阅读