【八大经典排序算法】快速排序

简介: 【八大经典排序算法】快速排序

一、概述

说到快速排序就不得不提到它的创始人 hoare了。在20世纪50年代,计算机科学家们开始研究如何对数据进行排序,以提高计算机程序的效率。当时,常用的排序算法包括冒泡排序、插入排序和选择排序等。

然而,这些算法的效率都相对较低,特别是在处理大量数据时。于是,人们开始寻找更快速的排序算法。Tony Hoare 在研究中发现了一种基于分治思想的排序方法,即快速排序。

二、思路实现

快速排序的思想是任取待排序元素序列中的某元素作为基准值,按照该排序码将待排序集合分割成两子序列,左子序列中所有元素均小于基准值,右子序列中所有元素均大于基准值,然后最左右子序列重复该过程,直到所有元素都排列在相应位置上为止。

代码如下:

// 假设按照升序对array数组中[left, right]区间中的元素进行排序
void QuickSort(int* a, int begin, int end)
{
  if (begin >= end)
    return;
  // 按照基准值对数组的 [left, right)区间中的元素进行划分
  int keyi = PartSort(a, begin, end);
  //分成[begin,keyi-1] keyi [keyi+1,end]
  
   // 递归排[left, div)
  QuickSort(a, begin, keyi - 1);
   // 递归排[div+1, right)
  QuickSort(a, keyi + 1, end);
}

上述为快速排序递归实现的主框架,发现与二叉树前序遍历规则非常像,接下来只需分析如何按照基准值来对区间中数据进行划分的方式即可。

待排序集合分割时,将区间按照基准值划分为左右两半部分的常见方式有以下3种。

2.1 hoare版本

思路

  1. 选择一个基准元素(key),可以是最左边也可以是最右边。
  2. 定义两个指针,一个指向数组的第一个元素(左指针),一个指向数组的最后一个元素(右指针)。(需要注意的是:若选择最左边的数据作为key,则需要right先走;若选择最右边的数据作为key,则需要left先走
  3. 移动左指针,直到找到一个大于等于基准元素(key)的元素;移动右指针,直到找到一个小于等于基准元素(key)的元素。之后交换交换左右指针所指向的元素。然后不断重复上述步骤直到左指针大于右指针
  4. 最后将基准元素与右指针所指向的元素交换位置,此时基准元素位于正确的位置。此时左边元素>=key,右边元素<=key。

Tips:博主在这里解释一下为什么“若选择最左边的数据作为key,则需要right先走;若选择最右边的数据作为key,则需要left先走”,后续其他方法同理。

① :左边作key,右边先走,保证了相遇位置的值小于key或就是key的位置。

②:右边作key,左边先走,保证了相遇位置的值大于key或就是key的位置。

以①为例,L和R相遇无非就两种情况:L遇R,R遇L。

情况一:L遇R。在R停下来后,L还在走。由于R先走,R停下来的位置一定小于Key。相遇位置为R停下来的位置,一定比key小。

情况二:R遇L。再相遇的这一轮,L就不动了,R在移动。相遇位置即为L的位置。而L的位置就是key的位置 or 已经交换过一些轮次了,此时相遇位置一定比key小。

【动画演示】:

代码如下:

//[left, right]--采用左闭右闭
int PartSort(int* a, int left, int right)
{
  int keyi = left;
  while (left < right)
  {
    //找到右边比key小的数
    while (left < right && a[right] <= a[keyi])
    {
      right--;
    }
    //找到左边比key大的数
    while (left < right && a[left] >= a[keyi])
    {
      left++;
    }
    Swap(&a[left], &a[right]);
  }
  Swap(&a[keyi], &a[left]);
  return left;
}
void Swap(int* p1, int* p2)
{
  int tmp = *p1;
  *p1 = *p2;
  *p2 = tmp;
}

2.2 挖坑法

思路

  1. .选出一个数据(一般是最左边或是最右边的)存放在key变量中,同时该数据位置形成一个坑。
  2. 还是左右指针left和right,left从左向右走,right从右向左走。(若在最左边挖坑,则需要R先走;若在最右边挖坑,则需要L先走)
  3. 移动右指针找到第一个比key小的数并填到坑位,此时右指针所在位置变成新的坑。然后移动左指针找到第一个比key大的数并填到坑位,此时左指针所在位置变成新的坑。然后和hoare版本一样,不断重复上述步骤即可

【动画演示】:

代码如下:

//挖坑法
int PartSort(int* a, int left, int right)
{
  int key = a[left];
  int hole = left;
  while (left < right)
  {
    //找到右边比key小的值
    while (left < right && a[right] >= key)
    {
      right--;
    }
    a[hole] = a[right];
    hole = right;
    //左边比key大的值
    while (left < right && a[left] <= key)
    {
      left++;
    }
    a[hole] = a[left];
    hole = left;
  }
  a[hole] = key;
  return hole;
}
void Swap(int* p1, int* p2)
{
  int tmp = *p1;
  *p1 = *p2;
  *p2 = tmp;
}

2.3 前后指针版本

思路

  1. 选出一个key,一般是最左边或是最右边的。
  2. 起始时,prev指针指向序列开头,cur指针指向prev+1。
  3. 若cur指向的内容小于key,则prev先向后移动一位,然后交换prev和cur指针指向的内容,然后cur指针++;若cur指向的内容大于key,则cur指针直接++。如此进行下去,直到cur到达end位置,此时将key和++prev指针指向的内容交换即可。

【动画演示】:

代码如下:

//前后指针法
int PartSort(int* a, int left, int right)
{
  int keyi = left;
  int prev = left;
  int cur = left + 1;
  while (cur <= right)
  {
    if (a[cur] < a[keyi] && ++prev != cur)
    {
      Swap(&a[prev], &a[cur]);
    }
    cur++;
  }
  Swap(&a[prev], &a[keyi]);
  keyi = prev;
  return keyi;
}
void Swap(int* p1, int* p2)
{
  int tmp = *p1;
  *p1 = *p2;
  *p2 = tmp;
}

三、优化

虽然已经可以解决问题了,但还有一个问题:

当选取的key每次都是中位数时,效率最好,时间复杂度为O(N*logN);但当数组有序时变成最坏,时间复杂度变为O(N^2)!

对于上述情况,这里有两种优化方式:

  1. 三数取中法选key
  2. 递归到小的子区间时,可以考虑使用插入排序

3.1 三数取中

这里博主给出一直最简单的方法:

int GetMidIndix(int* a, int left, int right)
{
  int mid = left + (right - left) / 2;
  if (a[left] < a[mid])
  {
    if (a[mid] < a[right])
      return mid;
    else if (a[mid] > a[right])
      return right;
    else
      return left;
  }
  else//a[left]>=a[mid]
  {
    if (a[mid] > a[right])
      return mid;
    else if (a[mid] < a[right])
      return right;
    else
      return left;
  }
}

3.1.1 最终代码

void Swap(int* p1, int* p2)
{
  int tmp = *p1;
  *p1 = *p2;
  *p2 = tmp;
}
int GetMidIndix(int* a, int left, int right)
{
  int mid = left + (right - left) / 2;
  if (a[left] < a[mid])
  {
    if (a[mid] < a[right])
      return mid;
    else if (a[mid] > a[right])
      return right;
    else
      return left;
  }
  else//a[left]>=a[mid]
  {
    if (a[mid] > a[right])
      return mid;
    else if (a[mid] < a[right])
      return right;
    else
      return left;
  }
}
// hoare
// [left, right]
//int PartSort(int* a, int left, int right)
//{
//  int midi = GetMidIndix(a, left, right);
//  Swap(&a[left], &a[midi]);
//
//  int keyi = left;
//  while (left < right)
//  {
//    //找到右边比key小的数
//    while (left < right && a[right] <= a[keyi])
//    {
//      right--;
//    }
//
//    //找到左边比key大的数
//    while (left < right && a[left] >= a[keyi])
//    {
//      left++;
//    }
//    Swap(&a[left], &a[right]);
//  }
//  Swap(&a[keyi], &a[left]);
//  return left;
//}
//挖坑法
//int PartSort(int* a, int left, int right)
//{
//  int midi = GetMidIndix(a, left, right);
//  Swap(&a[left], &a[midi]);
//
//  int key = a[left];
//  int hole = left;
//  while (left < right)
//  {
//    //找到右边比key小的值
//    while (left < right && a[right] >= key)
//    {
//      right--;
//    }
//    a[hole] = a[right];
//    hole = right;
//
//    //左边比key大的值
//    while (left < right && a[left] <= key)
//    {
//      left++;
//    }
//    a[hole] = a[left];
//    hole = left;
//  }
//  a[hole] = key;
//  return hole;
//}
//前后指针法
int PartSort(int* a, int left, int right)
{
  int midi = GetMidIndix(a, left, right);
  Swap(&a[left], &a[midi]);
  int keyi = left;
  int prev = left;
  int cur = left + 1;
  while (cur <= right)
  {
    if (a[cur] < a[keyi] && ++prev != cur)
    {
      Swap(&a[prev], &a[cur]);
    }
    cur++;
  }
  Swap(&a[prev], &a[keyi]);
  keyi = prev;
  return keyi;
}
void QuickSort(int* a, int begin, int end)
{
  if (begin >= end)
    return;
  int keyi = PartSort(a, begin, end);
  //分成[begin,keyi-1] keyi [keyi+1,end]
  QuickSort(a, begin, keyi - 1);
  QuickSort(a, keyi + 1, end);
}

3.1.2 快速排序的特性总结

  1. 时间复杂度:O(N*logN)

  1. 空间复杂度:O(logN)
  2. 稳定性:不稳定

四、非递归实现快排

思路:

  1. 定义一个栈,然后将待排序的数组的起始索引和结束索引入栈。
  2. 通过前面将的三种分割区间的方法将数组的起始索引和结束索引之间的元素分成两部分,左边部分小于等于基准元素,右边部分大于等于基准元素。
  3. 由于非递归实现时,我们是通过从栈中两两取出维护待排序数组的下标,所以接下来就是如果左边部分的长度大于1,则将左边部分的起始索引和结束索引入栈;如果右边部分的长度大于1,则将右边部分的起始索引和结束索引入栈。最后循环此操作,直到栈为空。

代码如下:

//前后指针法
int PartSort(int* a, int left, int right)
{
  int midi = GetMidIndix(a, left, right);
  Swap(&a[left], &a[midi]);
  int keyi = left;
  int prev = left;
  int cur = left + 1;
  while (cur <= right)
  {
    if (a[cur] < a[keyi] && ++prev != cur)
    {
      Swap(&a[prev], &a[cur]);
    }
    cur++;
  }
  Swap(&a[prev], &a[keyi]);
  keyi = prev;
  return keyi;
}
//快排非递归
void QuickSortNonR(int* a, int begin, int end)
{
  ST st;
  STInit(&st);
  STPush(&st, end);
  STPush(&st, begin);
  while (!STEmpty(&st))
  {
    int left = STTop(&st);
    STPop(&st);
    int right = STTop(&st);
    STPop(&st);
    int keyi = PartSort(a, left, right);
    //[left,keyi-1] keyi [keyi+1,right]
    if (keyi + 1 < right)
    {
      STPush(&st, right);
      STPush(&st, keyi + 1);
    }
    if (keyi - 1 > left)
    {
      STPush(&st, keyi - 1);
      STPush(&st, left);
    }
  }
  STDestroy(&st);
}


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