C#递归算法之快速排序

2024-12-13 14:45:45

上两片第归算法学习：

1）递归算法之分而治之策略
2）递归算法之归并排序

　　上一篇学习中介绍了了递归算法在排序中的一个应用：归并排序，在排序算法中还有一种算法用到了递归，那就是快速排序，快速排序也是一种利用了分而治之策略的算法，它由C.A.R发明，它依据中心元素的值，利用一系列递归调用将数据表划分成越来越小的子表。在每一步调用中，经过多次的交换，最终为中心元素找到最终的位置。与归并算法不同，快速排序是就地排序，而归并排序需要把元素在临时向量中拷贝，下面通过对以下向量进行排序来理解和加深快速排序算法的步骤：

v={800,150,300,650,550,500,400,350,450,400,900};

　　利用快速排序算法对此数据表进行排序的第0级划分过程如下：向量v的索引范围为:[first,last) = [0,10),则中心点的索引为mid = (0+10)/2=5,中心点的值为v[5] = 500

　　快速排序算法的第一次划分的目的就是将向量v依据v[5]的值划分成两个子表subList1和subList2，其中subList1中的值都小于v[5],而subList2中的值都大于v[5],我们将subList1称为左子表，subList2称为右子表，并且确定v[5]的最终位置

下面就是实现这一目的需要我们作出的工作步骤：

1）首先将中心元素与起始位置的元素进行交换。

2）分别扫描左子表和右子表，左子表扫描起始位置为 first+1, 右子表从last-1开始。左子表从左向右扫描扫描，右子表从右向左扫描。直到左子表扫描位置大于或者等于右子表扫描位置时候结束。

在第一个步骤中，得到如下的数据表

500 150 300 650 550 800 400 350 450 400

　　而此时的左子表扫描位置处于索引1处，右子表扫描位置处于索引9处，先从左子表扫描，直到找到数据值大于中间值500的位置停止扫描，然后扫描右子表，直到找到数据值小于中间值500并且右子表的扫描位置（scanDown)要小于左子表开始位置，防止数据溢出。找到之后，交换左子表与右子表中中扫描位置的元素，图示如下：

在交换v[3](650>500)与v[8](450<500)后，继续扫描左子表和右子表，如图

　　直到满足条件scanUp>=scanDown，然后scanDown所在位置就是中心元素500的最终位置，交换v[0]与v[scanDown)=v[5],第一次划分级别的最终结果数据集为：400,150,300,450,350,500,800,550,650,900,此时得到的左子表为:400,150,300,450,350,右子表为:800,550,650,900

　　下一个划分级别是处理上一级别产生的子表，按照相同的处理方法分别处理左子表和右子表，左子表索引位置[0,5),右子表索引位置[6,10),按照上面的处理步骤处理左子表(400,150,300,450,350)得到的最终结果为:150,300,400,450,350 右子表最终处理结果为:550,650,800,900 在处理结果中300与650分别是中心值，他们现在的位置就是最终位置

　　在接下来的处理中，总是处理上一步骤中留下的子表，当子表数目<=1的时候就不用处理子表了，而子表有两个元素的时候，比较大小，然后交换两元素位置即可。

大于2个元素的子表都和上面的处理步骤一样，我们将上面的处理过程编写出一个函数

private int PivotIndex(int[] v, int first, int last)，那么快速排序算法就是对此函数的递归调用

/// <summary>
/// 交换位置
/// </summary>
/// <param name="v"></param>
/// <param name="index1"></param>
/// <param name="index2"></param>
private void Swrap(int[] v, int index1, int index2)
{
 int temp = v[index1];
 v[index1] = v[index2];
 v[index2] = temp;
}
/// <summary>
/// 将向量V中索引{first,last)划分成两个左子表和右子表
/// </summary>
/// <param name="v">向量V</param>
/// <param name="first">开始位置</param>
/// <param name="last">结束位置</param>
private int PivotIndex(int[] v, int first, int last)
{
 if (last == first)
 {
  return last;
 }
 if (last - first == 1)
 {
  return first;
 }
 int mid = (first + last) / 2;
 int midVal = v[mid];
 //交换v[first]和v[mid]
 Swrap(v, first, mid);
 int scanA = first + 1;
 int scanB = last - 1;
 for (; ; )
 { 

  while (scanA <= scanB && v[scanA] < midVal)
  {
   scanA++;
  }
  while (scanB > first && midVal <= v[scanB])
  {
   scanB--;
  }
  if (scanA >= scanB)
  {
   break;
  }
  Swrap(v, scanA, scanB);
  scanA++;
  scanB--;
 }
 Swrap(v, first, scanB);
 return scanB; 

}
public void Sort(int[] v, int first, int last)
{
 if (last - first <= 1)
 {
  return;
 }
 if (last - first == 2)
 {
  //有两个元素的子表
  if (v[first] > v[last - 1])
  {
   Swrap(v, first, last - 1);
  }
  return;
 }
 else
 {
  int pivotIndex = PivotIndex(v, first, last);
  Sort(v, first, pivotIndex);
  Sort(v, pivotIndex + 1, last);
 }
}

　　快速排序因为每次划分都能将中心值元素找到最终的位置，并且左边值都小于中心值，右边都大于中心值，它的时间复杂度平均和归并算法一致为O(nlog2n);

　　任何一种基于比较的排序算法的时间复杂度不可能小于这个数，除非不使用比较的方法进行排序。

算法程序：http://xiazai.jb51.net/201606/yuanma/QuickSort(jb51.net).rar

C#递归算法之归并排序

归并排序是利用递归和分而治之的技术将数据序列划分成为越来越小的半子表,再对半子表排序,最后再用递归步骤将排好序的半子表合并成为越来越大的有序序列,归并排序包括两个步骤,分别为: 1)划分子表 2)合并半子表首先我们来讨论归并算法,归并算法将一系列数据放到一个向量中,索引范围为[first,last],这个序列由两个排好序的子表构成,以索引终点(mid)为分界线,以下面一个序列为例 7,10,19,25,12,17,21,30,48 这样的一个序列中,分为两个子序列 7,10,19,25 和
C#堆排序实现方法

本文实例讲述了C#堆排序实现方法.分享给大家供大家参考.具体如下: private static void Adjust (int[] list, int i, int m) { int Temp = list[i]; int j = i * 2 + 1; while (j <= m) { //more children if(j < m) if(list[j] < list[j + 1]) j = j + 1; //compare roots and the older childre
C#选择法排序实例分析

本文实例讲述了C#选择法排序实现方法.分享给大家供大家参考.具体实现方法如下: public int[] SelectionSort(int[] arr) { //1. Find min //2. Swap it with first element //3. Repeat starting from secong position onwards. int _min = 0; for (int i = 0; i < arr.Length; i++) { _min = i; for (int j
关于C#中排序函数的总结

sort 函数对数组中的数据进行升序排序,(其中,sort函数有很多重载的形式,这里不再一一的说明) Reverse函数对数组中的数据进行降序排序, static void Main(string[] args) { // sort ,Reverse 排序的应用举例 int[] intArr = { 1,4,2,3,99,34,22,16,8,100}; Console.WriteLine("原数组为:"); for (int i = 0; i < intArr.Length;
C#实现冒泡排序算法的代码示例

1.原理:从数组的第一个位置开始两两比较array[index]和array[index+1],如果array[index]大于array[index+1]则交换array[index]和array[index+1]的位置,止到数组结束; 从数组的第一个位置开始,重复上面的动作,止到数组长度减一个位置结束; 从数组的第一个位置开始,重复上面的动作,止到数组长度减二个位置结束; .... 2.时间复杂度:O(N²),进行了(n-1)*(n-2)....=n*(n-1)/2次比较和约比较次数一半的交
C#中哈希表(HashTable)用法实例详解(添加/移除/判断/遍历/排序等)

本文实例讲述了C#中哈希表(HashTable)用法.分享给大家供大家参考,具体如下: 1. 哈希表(HashTable)简述在.NET Framework中,Hashtable是System.Collections命名空间提供的一个容器,用于处理和表现类似keyvalue的键值对,其中key通常可用来快速查找,同时key是区分大小写:value用于存储对应于key的值.Hashtable中keyvalue键值对均为object类型,所以Hashtable可以支持任何类型的keyvalue键
逐步讲解快速排序算法及C#版的实现示例

算法思想快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序.它采用了一种分治的策略,通常称其为分治法(Divide-and-ConquerMethod). 该方法的基本思想是: 1．先从数列中取出一个数作为基准数. 2．分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边. 3．再对左右区间重复第二步,直到各区间只有一个数. 虽然快速排序称为分治法,但分治法这三个字显然无法很好的概括快速排序的全部步骤.因此我的对快速排序作了进一步的说明:挖坑填数+分治法:
C#中使用基数排序算法对字符串进行排序的示例

开始之前假设最长字符串的长度是L,以L作为输入的长度, 然后假定所有的字符串都"补齐"到此长度,这个补齐只是逻辑上的,我们可以假想有一种"空字符", 它小于任何其它字符,用此字符补齐所有长度不足的字符串.例如:最长的字符串长度为9,有一个字符串A长度为6, 那么当比较第7位字符的时候,我们让A[7]为"空字符". 如果要包含所有的字符似乎并不容易,我们先定义一个字符集, 待排序字符串中的所有字符都包含在这个字符集里 //字符集 private
C#插入法排序算法实例分析

本文实例讲述了C#插入法排序算法.分享给大家供大家参考.具体如下: public static void InsertSort (int[] list) { for (int i = 1; i < list.Length; i++) { int Temp = list [i]; int j = i - 1; while (j > = 0 && list [j] > Temp) { list [j + 1] = list [j]; j-; } list [j + 1] =
C语言非递归算法解决快速排序与归并排序产生的栈溢出

目录 1.栈溢出原因和递归的基本认识 2.快速排序(非递归实现) 3.归并排序(非递归实现) 建议还不理解快速排序和归并排序的小伙伴们可以先去看我上一篇博客哦!C语言超详细讲解排序算法下篇 1.栈溢出原因和递归的基本认识我们先简单来了解下内存分布结构: 栈区:用于存放地址.临时变量等: 堆区:程序运行期间动态分配所使用的场景: 静态区
C#递归算法之快速排序

上两片第归算法学习: 1)递归算法之分而治之策略 2)递归算法之归并排序上一篇学习中介绍了了递归算法在排序中的一个应用:归并排序,在排序算法中还有一种算法用到了递归,那就是快速排序,快速排序也是一种利用了分而治之策略的算法,它由C.A.R发明,它依据中心元素的值,利用一系列递归调用将数据表划分成越来越小的子表.在每一步调用中,经过多次的交换,最终为中心元素找到最终的位置.与归并算法不同,快速排序是就地排序,而归并排序需要把元素在临时向量中拷贝,下面通过对以下向量进行排序来理解和加深快速排序算法
PHP 递归效率分析

而且是差了3倍的效率.所以,PHP中的递归一定要小心的对待. 最近写了一个快速排序的算法,发现PHP中的递归效率不能一刀切,在各种不同的服务器中,可能会表现不一样. 复制代码代码如下: function qsort(&$arr) { _quick_sort($arr, 0, count($arr) - 1); } /** * 采用递归算法的快速排序. * * @param array $arr 要排序的数组 * @param int $low 最低的排序子段 * @param int $hig
java数据结构与算法之快速排序详解

本文实例讲述了java数据结构与算法之快速排序.分享给大家供大家参考,具体如下: 交换类排序的另一个方法,即快速排序. 快速排序:改变了冒泡排序中一次交换仅能消除一个逆序的局限性,是冒泡排序的一种改进:实现了一次交换可消除多个逆序.通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列. 步骤: 1.从数列中挑出一个元素,称为 "基准"(piv
C#递归算法寻找数组中第K大的数

1.概述国人向来喜欢论资排辈的,每个人都想当老大,实在当不成,当个老二,老三,老K也不错,您一定看过这样的争论: 两个人吵架,一个人非常强势,另外一个忍受不住了便说:"你算老几呀?",下面就通过这篇文章就是要解决找出老几的问题! 2.应用场景在向量V[first,last)中查找出第K大元素的值 3.分析如果利用排序算法将向量V排好序,那么第K大元素就是索引为v.length-k的元素了,这样能解决问题,但效率不高,因为这相当于为了歼灭敌人一个小队而动用了我们全军的力量,得不偿失
java 合并排序算法、冒泡排序算法、选择排序算法、插入排序算法、快速排序算法的描述

算法是在有限步骤内求解某一问题所使用的一组定义明确的规则.通俗点说,就是计算机解题的过程.在这个过程中,无论是形成解题思路还是编写程序,都是在实施某种算法.前者是推理实现的算法,后者是操作实现的算法. 一个算法应该具有以下五个重要的特征: 1.有穷性: 一个算法必须保证执行有限步之后结束: 2.确切性: 算法的每一步骤必须有确切的定义: 3.输入:一个算法有0个或多个输入,以刻画运算对象的初始情况: 4.输出:一个算法有一个或多个输出,以反映对输入数据加工后的结果.没有输出的算法是毫无意义的:
PHP四种排序算法实现及效率分析【冒泡排序,插入排序,选择排序和快速排序】

本文实例讲述了PHP四种排序算法实现及效率分析.分享给大家供大家参考,具体如下: PHP的四种基本排序算法为:冒泡排序.插入排序.选择排序和快速排序. 下面是我整理出来的算法代码: 1. 冒泡排序: 思路:对数组进行多轮冒泡,每一轮对数组中的元素两两比较,调整位置,冒出一个最大的数来. //简单版: function bubbleSort($arr) { $n = count($arr); for($i=1;$i<$n;$i++) { //冒泡的轮数(最多$n-1轮) for($j=0;$j<
C语言实现快速排序

快速排序算法是一种分治排序算法.它将数组划分为两个部分,然后分别对两个部分进行排序.我们将看到,划分的准确位置取决于输入数组中元素的初始位置.关键在于划分过程,它重排数组,使得以下三个条件成立:(i)对于某个i,a[i]在最终位置上 (ii)a[left],...,a[i-1]中的元素都比a[i]小 (iii)a[i+1],...a[right]中的元素都比a[i]大.我们通过划分来完成排序,然后递归地应用该方法处理子数组. 我们使用一般策略来实现划分.首先,我们任选一个a[right]作为划分
Linux静态链接库使用类模板的快速排序算法

快速排序的本质是从数组中选一个参考值ref,比该参考值的大的,将其放在ref的右边,比ref小的放在左边,然后不断的对两边重复执行该动作我们先列出来快速排序的步骤: 1.从数组中选一个参考值ref,比该参考值的大的,将其放在ref的右边, 上面的动作将数组划分为两部分: A ref B A是比ref小的数组元素集合,它仍然是数组,B是比ref大的元素集合,它也仍然是数组 2.在对ref左右两边的元素重复上述动作,直到A和B都只剩下一个元素,那么排序就算完成了. 重点是如何分别选出来两个集合A和
图解Java经典算法快速排序的原理与实现

目录快速排序算法原理图解 Java代码实现算法分析快速排序通过一趟排序将待排元素分成独立的两部分,其中一部分为比基准数小的元素,另一部分则是比基准数大的元素.然后对这两部分元素再按照前面的算法进行排序,直到每一部分的元素都只剩下一个. 本质上来看,快速排序应该算是在冒泡排序基础上的递归分治法. 算法原理从数列中挑出一个元素作为基准点重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面然后基准值左右两边,重复上述步骤通过递归把基准值元素左右两侧的

C#递归算法之快速排序

相关推荐

随机推荐