算法-快速排序

简介: 快速排序是广泛使用的排序算法,它在平均情况下进行n log n比较,以对 n 个元素的数组进行排序。该算法遵循分而治之的方法。分而治之是一种将算法分解为子问题,然后解决子问题,并将结果组合在一起以解决原始问题的技术。

一、简介

快速排序是一种基于分治法的排序算法,其中

  1. 通过选择枢轴元素(从数组中选择的元素)将数组划分为子数组。

    在划分数组时,枢轴元素的位置应使小于枢轴的元素保留在左侧,大于枢轴的元素位于枢轴的右侧。
  2. 左右子阵列也使用相同的方法进行划分。这个过程一直持续到每个子数组包含一个元素。
  3. 此时,元素已经排序。最后,将元素组合成一个排序数组。

二、快速排序算法步骤

(一)选择枢轴元素

快速排序有不同的变体,其中枢轴元素是从不同的位置选择的。在这里,我们将选择数组最右边的元素作为枢轴元素。

选择一个枢轴元素

(二)重新排列数组

现在数组的元素被重新排列,使小于枢轴的元素放在左边,大于枢轴的元素放在右边。

下面是我们如何重新排列数组:

  1. 指针固定在枢轴元素上。枢轴元素与从第一个索引开始的元素进行比较。

  1. 如果元素大于枢轴元素,则为该元素设置第二个指针

  1. 现在,将枢轴与其他元素进行比较。如果到达小于枢轴元素的元素,则将较小的元素与先前找到的较大元素交换

  1. 同样,重复该过程以将下一个更大的元素设置为第二个指针。并且,将其与另一个较小的元素交换。

  1. 该过程一直持续到到达倒数第二个元素。

  1. 最后,枢轴元素与第二个指针交换。

(三)划分子数组

再次分别为左侧和右侧子部分选择枢轴元素。并且,重复步骤 2 。子数组被划分,直到每个子阵列由单个元素形成。至此,数组已经排好序了。

(四)快速排序算法的可视化插图

您可以借助下图了解快速排序算法的工作原理。

使用递归对枢轴左侧的元素进行排序

使用递归对枢轴右侧的元素进行排序

Java实现快速排序

importjava.util.Arrays;
classQuicksort {
// method to find the partition positionstaticintpartition(intarray[], intlow, inthigh) {
// choose the rightmost element as pivotintpivot=array[high];
// pointer for greater elementinti= (low-1);
// traverse through all elements// compare each element with pivotfor (intj=low; j<high; j++) {
if (array[j] <=pivot) {
// if element smaller than pivot is found// swap it with the greatr element pointed by ii++;
// swapping element at i with element at jinttemp=array[i];
array[i] =array[j];
array[j] =temp;
      }
    }
// swapt the pivot element with the greater element specified by iinttemp=array[i+1];
array[i+1] =array[high];
array[high] =temp;
// return the position from where partition is donereturn (i+1);
  }
staticvoidquickSort(intarray[], intlow, inthigh) {
if (low<high) {
// find pivot element such that// elements smaller than pivot are on the left// elements greater than pivot are on the rightintpi=partition(array, low, high);
// recursive call on the left of pivotquickSort(array, low, pi-1);
// recursive call on the right of pivotquickSort(array, pi+1, high);
    }
  }
}
classMain {
publicstaticvoidmain(Stringargs[]) {
int[] data= { 8, 7, 2, 1, 0, 9, 6 };
System.out.println("Unsorted Array");
System.out.println(Arrays.toString(data));
intsize=data.length;
// call quicksort() on array dataQuicksort.quickSort(data, 0, size-1);
System.out.println("Sorted Array in Ascending Order: ");
System.out.println(Arrays.toString(data));
  }
}



相关文章
|
29天前
|
搜索推荐 C语言
【排序算法】快速排序升级版--三路快排详解 + 实现(c语言)
本文介绍了快速排序的升级版——三路快排。传统快速排序在处理大量相同元素时效率较低,而三路快排通过将数组分为三部分(小于、等于、大于基准值)来优化这一问题。文章详细讲解了三路快排的实现步骤,并提供了完整的代码示例。
52 4
|
13天前
|
存储 搜索推荐 Python
用 Python 实现快速排序算法。
快速排序的平均时间复杂度为$O(nlogn)$,空间复杂度为$O(logn)$。它在大多数情况下表现良好,但在某些特殊情况下可能会退化为最坏情况,时间复杂度为$O(n^2)$。你可以根据实际需求对代码进行调整和修改,或者尝试使用其他优化策略来提高快速排序的性能
111 61
|
2月前
|
算法 搜索推荐 Shell
数据结构与算法学习十二:希尔排序、快速排序(递归、好理解)、归并排序(递归、难理解)
这篇文章介绍了希尔排序、快速排序和归并排序三种排序算法的基本概念、实现思路、代码实现及其测试结果。
27 1
|
2月前
|
搜索推荐 Java Go
深入了解快速排序算法
深入了解快速排序算法
46 2
|
2月前
|
存储 搜索推荐 算法
【排序算法(二)】——冒泡排序、快速排序和归并排序—>深层解析
【排序算法(二)】——冒泡排序、快速排序和归并排序—>深层解析
|
2月前
|
算法 Python
Python算法编程:冒泡排序、选择排序、快速排序
Python算法编程:冒泡排序、选择排序、快速排序
27 0
|
2月前
|
搜索推荐 C语言 C++
【C语言】指针篇-精通库中的快速排序算法:巧妙掌握技巧(4/5)
【C语言】指针篇-精通库中的快速排序算法:巧妙掌握技巧(4/5)
|
4月前
|
搜索推荐 算法 Java
现有一个接口DataOperation定义了排序方法sort(int[])和查找方法search(int[],int),已知类QuickSort的quickSort(int[])方法实现了快速排序算法
该博客文章通过UML类图和Java源码示例,展示了如何使用适配器模式将QuickSort类和BinarySearch类的排序和查找功能适配到DataOperation接口中,实现算法的解耦和复用。
47 1
现有一个接口DataOperation定义了排序方法sort(int[])和查找方法search(int[],int),已知类QuickSort的quickSort(int[])方法实现了快速排序算法
|
4月前
|
算法 搜索推荐
算法设计 (分治法应用实验报告)基于分治法的合并排序、快速排序、最近对问题
这篇文章是关于分治法应用的实验报告,详细介绍了如何利用分治法实现合并排序和快速排序算法,并探讨了使用分治法解决二维平面上的最近对问题的方法,包括伪代码、源代码实现及时间效率分析,并附有运行结果和小结。
|
5月前
|
算法 搜索推荐 编译器
算法高手养成记:Python快速排序的深度优化与实战案例分析
【7月更文挑战第11天】快速排序是编程基础,以O(n log n)时间复杂度和原址排序著称。其核心是“分而治之”,通过选择基准元素分割数组并递归排序两部分。优化包括:选择中位数作基准、尾递归优化、小数组用简单排序。以下是一个考虑优化的Python实现片段,展示了随机基准选择。通过实践和优化,能提升算法技能。**
61 3