C/C++实现三路快速排序算法原理

书接上文,上次讲到了双路快速排序,双路快速排序是将等于v(标志数)的数也进行交换,从而避免了在处理有大量重复数据的数组分组时的不平衡。而三路快速排序则是将等于v的数也分成一组,同样可以解决上述问题。其原理如下:

1、采用随机排序的方法将某个数作为分割数,放在数组开头,该数定义为v。将小于v的一段数组开头的数索引定义为lt,将需要遍历的数组的索引定义为i,将小于v的一段数组的索引定义为gt,数组的开头和结尾的索引分别为lr。原理图如下:

2、对索引i进行维护,逐个比较索引i对应的数与v的关系。如果arr[i]<v,那么将arr[i]和arr[lt+1]交换,之后将索引ilt分别向后移动一位。如下图蓝色的e和灰绿色的那块相交换


3、如果arr[i]=v,则将arr[i]纳入等于v的那一部分,之后将索引i向后移动一位

4、如果arr[i]>v,则将arr[i]与arr[gt-1]交换位置,之后将索引gt向前移动一位,但是要注意,这时,索引i不需要移动,因为交换过来的数不知道大小,下一步还需要接着判断。

5、按照这个流程,gt会和i重合,则结束比较的过程

6、最后,不要忘了将arr[l]和arr[lt]交换位置,注意:这里交换位置的是arr[lt]。排序完成

代码如下:

#ifndef QUICKSORT3_H
#define QUICKSORT3_H
//三路快速排序算法
#include <iostream>
#include <stdlib.h>

using namespace std;

template <typename T>
void __QuickSort3way(T *arr,int l,int r)
{
 //递归的终止条件
 if (l>=r)
 {
 return;
 }
 else
 {
 //随机快速排序选取的随机值,为了避免在整体大致有序的情况下产生分组不平衡现象,使算法退化
 int RAND = (rand() % (r - l) + l);
 swap(arr[l], arr[RAND]);
 T v = arr[l];
 //小于v的分组的初始索引
 int lt = l;
 //大于v的分组的初始索引
 int gt = r + 1;
 //等于v的分组的初始索引,并且,此索引是数组遍历值的索引
 int i = l + 1;
 while (i<gt)
 {
  //如果遍历的数据小于v
  if (arr[i]<v)
  {
  //将该数组与第一个等于v的数据交换
  swap(arr[lt + 1], arr[i]);
  //维护小于v的索引和待遍历的数据的索引
  lt++;
  i++;
  }
  //如果数据大于v
  else if (arr[i]>v)
  {
  //交换该数与大于v的第一个数,但是在这里不需要维护i的索引
  swap(arr[i], arr[gt - 1]);
  gt--;
  }
  else//arr[i]==v
  {
  i++;//直接维护i的索引
  }
 }
 //最后将数组第一个数v和小于v的最后一个数互换
 swap(arr[l],arr[lt]);

 __QuickSort3way(arr,l,lt);
 __QuickSort3way(arr,gt,r);
 }
}

template <typename T>
void QuickSort3way(T *arr,int n)
{
 __QuickSort3way(arr, 0, n - 1);
}

#endif // !QUICKSORT3_H

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

(0)

相关推荐

  • 解读堆排序算法及用C++实现基于最大堆的堆排序示例

    1.堆排序定义 n个关键字序列Kl,K2,-,Kn称为堆,当且仅当该序列满足如下性质(简称为堆性质): (1) ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤   ) 若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构,则堆实质上是满足如下性质的完全二叉树:树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字. [例]关键字序列(10,15,56,25,30,70)和(70,56,30,25,15,10)分别满足堆性质(1

  • C++冒泡排序算法实例

    冒泡排序 大学学习数据结构与算法最开始的时候,就讲了冒泡排序:可见这个排序算法是多么的经典.冒泡排序是一种非常简单的排序算法,它重复地走访过要排序的数列,每一次比较两个数,按照升序或降序的规则,对比较的两个数进行交换.比如现在我要对以下数据进行排序: 10 3 8 0 6 9 2 当使用冒泡排序进行升序排序时,排序的步骤是这样的: 3 10 8 0 6 9 2  // 10和3进行对比,10>3,交换位置 3 8 10 0 6 9 2  // 10再和8进行对比,10>8,交换位置 3 8 0

  • C++中十种内部排序算法的比较分析

    C++中十种内部排序算法的比较分析 #include<iostream> #include<ctime> #include<fstream> using namespace std; #define MAXSIZE 1000 //可排序表的最大长度 #define SORTNUM 10 //测试10中排序方法 #define max 100 //基数排序时数据的最大位数不超过百位: typedef struct node { int data3; int next; }

  • c++中八大排序算法

    概述 排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存. 我们这里说说八大排序就是内部排序. 当n较大,则应采用时间复杂度为O(nlog2n)的排序方法:快速排序.堆排序或归并排序序. 快速排序:是目前基于比较的内部排序中被认为是最好的方法,当待排序的关键字是随机分布时,快速排序的平均时间最短:  1.插入排序-直接插入排序(Straight Insertion Sort) 基本思想: 将一个记录插入

  • C++实现八个常用的排序算法:插入排序、冒泡排序、选择排序、希尔排序等

    本文实现了八个常用的排序算法:插入排序.冒泡排序.选择排序.希尔排序 .快速排序.归并排序.堆排序和LST基数排序 首先是算法实现文件Sort.h,代码如下: /* * 实现了八个常用的排序算法:插入排序.冒泡排序.选择排序.希尔排序 * 以及快速排序.归并排序.堆排序和LST基数排序 * @author gkh178 */ #include <iostream> template<class T> void swap_value(T &a, T &b) { T t

  • C++堆排序算法的实现方法

    本文实例讲述了C++实现堆排序算法的方法,相信对于大家学习数据结构与算法会起到一定的帮助作用.具体内容如下: 首先,由于堆排序算法说起来比较长,所以在这里单独讲一下.堆排序是一种树形选择排序方法,它的特点是:在排序过程中,将L[n]看成是一棵完全二叉树的顺序存储结构,利用完全二叉树中双亲节点和孩子节点之间的内在关系,在当前无序区中选择关键字最大(或最小)的元素. 一.堆的定义 堆的定义如下:n个关键字序列L[n]成为堆,当且仅当该序列满足: ①L(i) <= L(2i)且L(i) <= L(2

  • C++归并排序算法实例

    归并排序 归并排序算法是采用分治法的一个非常典型的应用.归并排序的思想是将一个数组中的数都分成单个的:对于单独的一个数,它肯定是有序的,然后,我们将这些有序的单个数在合并起来,组成一个有序的数列.这就是归并排序的思想.它的时间复杂度为O(N*logN). 代码实现 复制代码 代码如下: #include <iostream> using namespace std;   //将有二个有序数列a[first...mid]和a[mid...last]合并. void mergearray(int

  • C++实现各种排序算法类汇总

    C++可实现各种排序算法类,比如直接插入排序.折半插入排序.Shell排序.归并排序.简单选择排序.基数排序.对data数组中的元素进行希尔排序.冒泡排序.递归实现.堆排序.用数组实现的基数排序等. 具体代码如下: #ifndef SORT_H #define SORT_H #include <iostream> #include <queue> using namespace std; // 1.直接插入排序 template<class ElemType> void

  • C++选择排序算法实例

    选择排序 选择排序是一种简单直观的排序算法,它的工作原理如下.首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾.以此类推,直到所有元素均排序完毕. 选择排序的主要优点与数据移动有关.如果某个元素位于正确的最终位置上,则它不会被移动.选择排序每次交换一对元素,它们当中至少有一个将被移到其最终位置上,因此对n个元素的表进行排序总共进行至多n-1次交换.在所有的完全依靠交换去移动元素的排序方法中,选择排序属于非常

  • C++插入排序算法实例

    插入排序 没事喜欢看看数据结构和算法,增加自己对数据结构和算法的认识,同时也增加自己的编程基本功.插入排序是排序中比较常见的一种,理解起来非常简单.现在比如有以下数据需要进行排序: 10 3 8 0 6 9 2 当使用插入排序进行升序排序时,排序的步骤是这样的: 10 3 8 0 6 9 2 // 取元素3,去和10进行对比 3 10 8 0 6 9 2 // 由于10比3大,将10向后移动,将3放置在原来10的位置:再取8与前一个元素10进行对比 3 8 10 0 6 9 2 // 同理移动1

随机推荐