c# 快速排序算法
发布时间:2021-10-18 07:33:20
标签: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
投稿
猜你喜欢
- 一、消息中间件相关知识1、概述消息队列已经逐渐成为企业IT系统内部通信的核心手段。它具有低耦合、可靠投递、广播、流量控制、最终一致性等一系列
- 来源:https://www.cnblogs.com/dato/p/7027949.html
- C# 结构体在 C# 中,结构体是值类型数据结构。它使得一个单一变量可以存储各种数据类型的相关数据。struct 关键字用于创建结构体。定义
- JAVA枚举,比你想象中还要有用!我经常发现自己在Java中使用枚举来表示某个对象的一组潜在值。在编译时确定类型可以具有什么值的能力是一种强
- Spring介绍:spring 使用基本的 JavaBean 来完成以前只可能由 EJB 完成的事情。然而, Spring的用途不仅限于服务
- 1.背景Java语言相比于C和C++,一个最大的特点就是不需要程序员自己手动去申请和释放内存,这一切交由JVM来完成。在Java中,运行时的
- 一、背景当我们在drools中编写规则时,有些时候存在重复的代码,那么我们是否可以将这些重复代码抽取出来,封装成一个function来调用呢
- 本文实例讲述了C#实现中英文混合字符串截取的方法,是C#字符串操作中非常常用的一个方法。分享给大家供大家参考之用。具体方法如下:具体功能代码
- 1,从System.String[]转到List<System.String>System.String[] str={&quo
- Java中四种访问权限总结一、Java中有四种访问权限, 其中三种有访问权限修饰符,分别为private、public、prot
- 一、首先我们先大致了解一下什么是多线程。(书上的解释)程序是一段静态的代码,它是应用软件的蓝本。进程是程序的一次动态执行过程,对
- 一、重载(Overload)重载是在一个类里面,方法名字相同,而参数不同。返回类型可以相同也可以不同。每个重载的方法(或者构造函数)都必须有
- 1.前言MyBatis框架大家肯定都用过的,废话我就不再多说了,这篇文章就给大家分享一下有关MyBatis框架底层的执行原理吧(Debug!
- Java怎么自动添加重写的toString方法,这里我们将给大家介绍详细的解决方法。首先,添加一个任意的类,具体的类型没有要求,然后在主程序
- mybatis 查询返回Map<String,Object> 类型,平时没太注意怎么用,今天又遇到了总结记录一下,方便以后处理此
- Vector实现了AbstractList抽象类和List接口,和ArrayList一样是基于Array存储的Vector 是线程安全的,在
- 这篇文章主要介绍了设计模式在Spring框架中的应用汇总,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的
- 线程池模型一般的池化模型会有两个方法,用于获取资源和释放资源,就像这样:public interface XXPool{ &n
- 综述在Android系统中,出于对性能优化的考虑,对于Android的UI操作并不是线程安全的。也就是说若是有多个线程来操作UI组件,就会有
- 1、通过查找API文档:2、Map.Entry是一个接口,所以不能直接实例化。3、Map.entrySet( )返回的是一个collecti