c# 快速排序算法

快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。

步骤为：

1.从数列中挑出一个元素，称为 "基准"（pivot），

2.重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。

3.递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。





平均时间复杂度

快速排序通常明显比其他Ο(n log n) 算法更快

代码如下:

public static void Sort(int[] numbers)
{
    QuickSort(numbers, 0, numbers.Length - 1);
}
private static void QuickSort(int[] numbers, int left, int right)
{
    if (left < right)
    {
        int middle = numbers[(left + right) / 2];
        int i = left - 1;
        int j = right + 1;
        while (true)
        {
            while (numbers[++i] < middle) ;

while (numbers[--j] > middle) ;

if (i >= j)
                break;

Swap(numbers, i, j);
        }

QuickSort(numbers, left, i - 1);
        QuickSort(numbers, j + 1, right);
    }
}

private static void Swap(int[] numbers, int i, int j)
{
    int number = numbers[i];
    numbers[i] = numbers[j];
    numbers[j] = number;
}

调用：

代码如下:

int[] y = new int[] {4,8,2222,2,1,121,13,434,56,1111,65,7,8 };
Sort(y);
foreach (var item in y)
{
    Console.WriteLine(item);
} // 1 2 4 7 8 8 13 56 65 121 434 1111 2222

赞 (0)

相关推荐

  • C#七大经典排序算法系列（下）

    C#七大经典排序算法系列（下）

    今天跟大家聊聊最后三种排序: 直接插入排序,希尔排序和归并排序. 直接插入排序: 这种排序其实蛮好理解的,很现实的例子就是俺们斗地主,当我们抓到一手乱牌时,我们就要按照大小梳理扑克,30秒后,扑克梳理完毕,4条3,5条s,哇塞...... 回忆一下,俺们当时是怎么梳理的. 最左一张牌是3,第二张牌是5,第三张牌又是3,赶紧插到第一张牌后面去,第四张牌又是3,大喜,赶紧插到第二张后面去,第五张牌又是3,狂喜,哈哈,一门炮就这样产生了. 怎么样,生活中处处都是算法,早已经融入我们的生活和血液. 下面

  • c# 冒泡排序算法(Bubble Sort) 附实例代码

    c# 冒泡排序算法(Bubble Sort) 附实例代码

    冒泡排序(Bubble Sort) 冒泡排序算法的运作如下: 1.比较相邻的元素.如果第一个比第二个大,就交换他们两个.2.对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对.在这一点,最后的元素应该会是最大的数.3.针对所有的元素重复以上的步骤,除了最后一个.4.持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较. 平均时间复杂度 复制代码 代码如下: /// <summary> /// 冒泡排序 /// </summary> /// <param

  • C#数组排序的两种常用方法

    本文实例讲述了C#数组排序的两种常用方法.分享给大家供大家参考.具体如下: 1.第一个例子 定义代码 #region Array数组排序1 public class Pigeon : IComparable<Pigeon> //类元素本身继承比较接口 { int XValue; int YValue; public string BatchNo { get; set; } public int CompareTo(Pigeon other) { if (other == null) throw

  • C# 排序算法之堆排序

    C# 排序算法之堆排序

    一.基本概念 堆:这里是指一种数据结构,而不是我们在C#中提到的用于存储引用类型对象的地方.它可以被当成一棵完全二叉树.  为了将堆用数组来存放,这里对每个节点标上顺序.事实上,我们可以用简单的计算公式得出父节点,左孩子,右孩子的索引: parent(i) = left(i) = 2i right(i)=2i + 1 最大堆和最小堆: 最大堆是指所有父节点的值都大于其孩子节点的堆,即满足以下公式: A[parent[i]]A[i](A是指存放该堆的数组) 最小堆相反. 最大堆和最小堆是堆排序的关

  • C#对DataTable里数据排序的方法

    直接给个实例代码吧 复制代码 代码如下: protected void Page_Load(object sender, EventArgs e)    {        DataTable dt = new DataTable();        dt.Columns.Add("Name");        dt.Columns.Add("Age");//因为是字符串,所以排序不对        dt.Rows.Add("小明", "

  • C#实现对数组进行随机排序类实例

    本文实例讲述了C#实现对数组进行随机排序类.分享给大家供大家参考.具体如下: 这个一个扩充C#随机数发生器的类,可以随机生成指定范围的数字,可以随机对数组进行排序,非常好用 using System; namespace DotNet.Utilities { /// <summary> /// 使用Random类生成伪随机数 /// </summary> public class RandomHelper { //随机数对象 private Random _random; #reg

  • C#基础之数组排序、对象大小比较实现代码

    从个小例子开始: 复制代码 代码如下: int[] intArray = new int[]{2,3,6,1,4,5}; Array.Sort(intArray); Array.ForEach<int>(intArray,(i)=>Console.WriteLine(i)); 这个例子定义了一个int数组,然后使用Array.Sort(arr)静态方法对此数组进行排序,最后输出排序后的数组.以上例子将毫无意外的依次输出1,2,3,4,5,6. 为什么Array的Sort方法可以正确的对i

  • C#归并排序的实现方法(递归,非递归,自然归并)

    C#归并排序的实现方法(递归,非递归,自然归并)

    //Main: 复制代码 代码如下: using System;using System.Collections.Generic;using System.Linq;using System.Text; namespace Merge{    class Program    {        static void Main(string[] args)        {            while (true)            {                Console.W

  • C#排序算法之快速排序

    快速排序实现: 复制代码 代码如下: namespace QuickSort { class QuickSort { public static void Sort(int[] array) { DoSort(array,0, array.Length-1); } private static void DoSort( int[] array, int start, int end) { if( start < end) { int temp = Partition(array, start,

  • PHP 快速排序算法详解

    PHP 快速排序算法详解

    概念 这里借用百度百科的一张图来,非常形象: 快速排序算法是对冒泡算法的一个优化.他的思想是先对数组进行分割, 把大的元素数值放到一个临时数组里,把小的元素数值放到另一个临时数组里(这个分割的点可以是数组中的任意一个元素值,一般用第一个元素,即$array[0]),然后继续把这两个临时数组重复上面拆分,最后把小的数组元素和大的数组元素合并起来.这里用到了递归的思想. PHP实现 复制代码 代码如下: /*     快速排序 */ function quickSort($array) {    

  • Go语言展现快速排序算法全过程的思路及代码示例

    快速排序算法 快速排序是一个递归的思想,首先选择一个数作为基数,把数组中小于它的数放在它的左边,把大于它的数放在它的右边,然后对左右两边的数递归进行排序. 算法的关键部分是实现数组的划分,即怎么把数组的元素划分成两部分,使得左边的数比基数小,右边的数比基数大.划分有许多不同的实现方法,这里主要使用单向扫描的方法,后面再稍微介绍双向扫描的方法. 选择最右边的数字作为基数.使用一个变量j记录当前左边数字(比基数小的数)的最右的下标值.然后使用变量i从左到右遍历数组,如果a[i]比基数小,说明a[i]

  • 深入解析快速排序算法的原理及其Go语言版实现

    深入解析快速排序算法的原理及其Go语言版实现

    快速排序是一种基于分治技术的重要排序算法.不像归并排序是按照元素在数组中的位置对它们进行划分,快速排序按照元素的值对它们进行划分.具体来说,它对给定数组中的元素进行重新排列,以得到一个快速排序的分区.在一个分区中,所有在s下标之前的元素都小于等于A[s],所有在s下标之后的元素都大于等于A[s]. 显然,建立了一个分区以后,A[s]已经位于它在有序数组中的最终位置,接下来我们可以继续对A[s]前和A[s]后的子数组分别进行排序(使用同样的方法). 为了排序一个数组A的全部元素,初始调用的是QUI

  • Java实现快速排序算法(Quicktsort)

    快速排序算法介绍快速排序和归并排序都使用分治法来设计算法,区别在于归并排序把数组分为两个基本等长的子数组,分别排好序之后还要进行归并(Merge)操作,而快速排序拆分子数组的时候显得更有艺术,取一个基准元素,拆分之后基准元素左边的元素都比基准元素小,右边的元素都不小于基准元素,这样只需要分别对两个子数组排序即可,不再像归并排序一样需要归并操作.基准元素的选取对算法的效率影响很大,最好的情况是两个子数组大小基本相当.为简单起见,我们选择最后一个元素,更高级的做法可以先找一个中位数并把中位数与最后一

  • 浅析java快速排序算法

    浅析java快速排序算法

    快速排序是找出一个元素(理论上可以随便找一个)作为基准(pivot),然后对数组进行分区操作,使基准左边元素的值都不大于基准值,基准右边的元素值 都不小于基准值,如此作为基准的元素调整到排序后的正确位置.递归快速排序,将其他n-1个元素也调整到排序后的正确位置.最后每个元素都是在排序后的正 确位置,排序完成.所以快速排序算法的核心算法是分区操作,即如何调整基准的位置以及调整返回基准的最终位置以便分治递归. 一趟快速排序的算法是: 1)设置两个变量i.j,排序开始的时候:i=0,j=N-1: 2)

  • C#快速排序算法实例分析

    本文实例讲述了C#快速排序算法.分享给大家供大家参考.具体实现方法如下: public static int[] QuickSort(int[] arr) { if (arr.Length <= 1) return arr; int pivot = arr.Length - 1; int[] less = GetLessThanEqualToPivot(arr, pivot); int[] greater = GetGreaterThanPivot(arr, pivot); return Con

  • 详解Java中使用泛型实现快速排序算法的方法

    快速排序算法概念 快速排序一般基于递归实现.其思路是这样的: 1.选定一个合适的值(理想情况中值最好,但实现中一般使用数组第一个值),称为"枢轴"(pivot). 2.基于这个值,将数组分为两部分,较小的分在左边,较大的分在右边. 3.可以肯定,如此一轮下来,这个枢轴的位置一定在最终位置上. 4.对两个子数组分别重复上述过程,直到每个数组只有一个元素. 5.排序完成. 基本实现方式: public static void quickSort(int[] arr){ qsort(arr,

  • Python实现的快速排序算法详解

    本文实例讲述了Python实现的快速排序算法.分享给大家供大家参考,具体如下: 快速排序基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列. 如序列[6,8,1,4,3,9],选择6作为基准数.从右向左扫描,寻找比基准数小的数字为3,交换6和3的位置,[3,8,1,4,6,9],接着从左向右扫描,寻找比基准数大的数字为8,交换6和8的位置

  • java实现快速排序算法

    java实现快速排序算法

    1.算法概念. 快速排序(Quicksort)是对冒泡排序的一种改进.由C. A. R. Hoare在1962年提出. 2.算法思想. 通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列. 3.实现思路. ①以第一个关键字 K 1 为控制字,将 [K 1 ,K 2 ,-,K n ] 分成两个子区,使左区所有关键字小于等于 K 1 ,右区所有关键字大于

  • 常用排序算法整理分享(快速排序算法、希尔排序)

    整理了几个排序算法,通过测试来看,最快的还是快速排序算法,简直不是一个数量级的速度. 复制代码 代码如下: #include <stdio.h>#include <stdlib.h>#include <stdint.h>#include <stdbool.h>#include <time.h>#include <unistd.h> //一些排序算法整理//插入排序算法//直接插入排序voiddirect_insert_sort(int

随机推荐