常见排序算法——快速排序

简介: 快速排序核心就是分治法,通过划分将待排序的序列分成前后两部分,其中前一部分的数据都比后一部分的数据要小,然后再递归调用函数对两部分的序列分别进行快速排序,以此使整个序列达到有序,其时间复杂度为O(nlogn)。该算法步骤如下: 1、从序列中任选一个数作为基准数,一般就使用第一个数; 2、分区,将大于

常见排序算法——快速排序


快速排序核心就是分治法,通过划分将待排序的序列分成前后两部分,其中前一部分的数据都比后一部分的数据要小,然后再递归调用函数对两部分的序列分别进行快速排序,以此使整个序列达到有序,其时间复杂度为O(nlogn)。该算法步骤如下:


1、从序列中任选一个数作为基准数,一般就使用第一个数;


2、分区,将大于基准得数房右边,小于基准得数放左边,注意一定要先右后左;


3、对左右区间分别执行1、2步骤,直到每个区间只有一个数为止。


public void sort(int leftLimit, int rightLimit, int[] nums){
  int i = leftLimit;
  int j = rightLimit;
  int mid = nums[i];
  while(i<j){
    while(i<j&&nums[j]>mid){
      j--;
    }
    if(i<j){
      nums[i++]=nums[j];
    }
    while(i<j&&nums[i]<mid){
      i++;
    }
    if(i<j){
      nums[j--]=nums[i];
    }
  }
  nums[i]=mid;
  if(leftLimit<i-1){
    sort(leftLimit, i-1, nums);
  }
  if(i+1<rightLimit){
    sort(i+1, rightLimit, nums);
  }
}


分类: 数据结构与算法

相关文章
|
11月前
|
搜索推荐 C语言
【排序算法】快速排序升级版--三路快排详解 + 实现(c语言)
本文介绍了快速排序的升级版——三路快排。传统快速排序在处理大量相同元素时效率较低,而三路快排通过将数组分为三部分(小于、等于、大于基准值)来优化这一问题。文章详细讲解了三路快排的实现步骤,并提供了完整的代码示例。
347 4
|
6月前
|
算法 搜索推荐
快速排序-数据结构与算法
快速排序(Quick Sort)是一种基于分治法的高效排序算法。其核心思想是通过选择基准(pivot),将数组划分为左右两部分,使得左侧元素均小于基准,右侧元素均大于基准,然后递归地对左右两部分进行排序。时间复杂度平均为 O(n log n),最坏情况下为 O(n²)(如数组已有序)。空间复杂度为 O(1),属于原地排序,但稳定性不佳。 实现步骤包括编写 `partition` 核心逻辑、递归调用的 `quickSort` 和辅助函数 `swap`。优化方法有随机化基准和三数取中法,以减少最坏情况的发生。
416 13
|
11月前
|
存储 搜索推荐 Python
用 Python 实现快速排序算法。
快速排序的平均时间复杂度为$O(nlogn)$,空间复杂度为$O(logn)$。它在大多数情况下表现良好,但在某些特殊情况下可能会退化为最坏情况,时间复杂度为$O(n^2)$。你可以根据实际需求对代码进行调整和修改,或者尝试使用其他优化策略来提高快速排序的性能
261 61
|
算法 搜索推荐 Shell
数据结构与算法学习十二:希尔排序、快速排序(递归、好理解)、归并排序(递归、难理解)
这篇文章介绍了希尔排序、快速排序和归并排序三种排序算法的基本概念、实现思路、代码实现及其测试结果。
342 1
|
搜索推荐
冒泡排序(Bubble Sort)以及选择排序(Selection Sort)和快速排序(Quick Sort)详细解析
冒泡排序(Bubble Sort)以及选择排序(Selection Sort)和快速排序(Quick Sort)详细解析
196 1
|
搜索推荐 Java Go
深入了解快速排序算法
深入了解快速排序算法
266 2
|
搜索推荐 算法 Java
现有一个接口DataOperation定义了排序方法sort(int[])和查找方法search(int[],int),已知类QuickSort的quickSort(int[])方法实现了快速排序算法
该博客文章通过UML类图和Java源码示例,展示了如何使用适配器模式将QuickSort类和BinarySearch类的排序和查找功能适配到DataOperation接口中,实现算法的解耦和复用。
184 1
现有一个接口DataOperation定义了排序方法sort(int[])和查找方法search(int[],int),已知类QuickSort的quickSort(int[])方法实现了快速排序算法
|
存储 搜索推荐 算法
【排序算法(二)】——冒泡排序、快速排序和归并排序—>深层解析
【排序算法(二)】——冒泡排序、快速排序和归并排序—>深层解析
|
算法 Python
Python算法编程:冒泡排序、选择排序、快速排序
Python算法编程:冒泡排序、选择排序、快速排序
137 0
|
搜索推荐 C语言 C++
【C语言】指针篇-精通库中的快速排序算法:巧妙掌握技巧(4/5)
【C语言】指针篇-精通库中的快速排序算法:巧妙掌握技巧(4/5)
110 0

热门文章

最新文章