c#快速排序算法
大家知道c#快速排序算法是怎么样的吗?下面小编为大家整理了c#快速排序算法,希望能帮到大家!
快速排序使用分治法(Divide and conquer)策略来把一个串行(list)分为两个子串行(sub-lists)。
步骤为:
1.从数列中挑出一个元素,称为 "基准"(pivot),
2.重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。
3.递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。
递归的'最底部情形,是数列的大小是零或一,也就是永远都已经被排序好了。虽然一直递归下去,但是这个算法总会退出,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。
快速排序通常明显比其他Ο(nlogn) 算法更快
复制代码 代码如下:
public static void Sort(int[] numbers)
{
QuickSort(numbers, 0, th - 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)
{
eLine(item);
} // 1 2 4 7 8 8 13 56 65 121 434 1111 2222
平均时间复杂度 |
---|
-
C语言中gets()函数知识
导语:gets从标准输入设备读字符串函数,其可以无限读取,不会判断上限,以回车结束读取,所以程序员应该确保buffer的空间足够大,以便在执行读操作时不发生溢出。。下面是C语言中gets()函数知识,一起来学习下吧:gets()函数用于从缓冲区中读取字符串,其原型如下:char*gets(cha...
-
C与C++之间相互调用的实例方法
如果使用C语言编写的DLL,希望从中导出函数给C或C++的模块访问,则应使用__cplusplus预处理器宏确定正在编译的语言。如果是从C++语言模块使用,则用C链接声明这些函数。如果使用此技术并为DLL提供头文件,则这些函数可以原封不动地由C和C++模块使用。下面是小编为大家...
-
浅谈高职C语言课程的教学分析与设计
C语言作为学院网络技术专业的人门课程,旨在通过锻炼学生的逻辑思维,墙养学生在职业岗位中实际应用的能力.目前,该专业的学生毕业后主要从事网站开发和网络管理等方面的工作,而在这些领域几乎都以C语言作为应用的开发工具.但从历年教学实践来看,教师往往付出的精力多...
-
C语言的第一个程序
C语言是一门通用计算机编程语言,应用广泛。C语言的设计目标是提供一种能以简易的方式编译、处理低级存储器、产生少量的机器码以及不需要任何运行环境支持便能运行的`编程语言。下面小编带大家看看第一个C语言程序。第一个C语言程序实例说明输出"Hello,world!"是...