快速排序使用分治法(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
如对本文有疑问,
点击进行留言回复!!
相关文章:
-
-
-
C#实现猜数字游戏
本文实例为大家分享了c#实现猜数字游戏具体代码,供大家参考,具体内容如下给定一个0-100的随机数字猜其大小题目样式:电脑产生一个0到100之间的随机数字,并且...
[阅读全文]
-
-
C# 可空类型的具体使用
在项目中我们经常会遇到可为空类型,那么到底什么是可为空类型呢?下面我们将从4个方面为大家剖析。1、可空类型基础知识顾名思义,可空类型指的就是某个对象类型可以为空...
[阅读全文]
-
-
-
C#实现猜数字小游戏
本文实例为大家分享了c#实现猜数字小游戏的具体代码,供大家参考,具体内容如下效果如图:代码:using system;using system.collecti...
[阅读全文]
-
-
C#实现简单俄罗斯方块
最近在看《.net游戏编程入门经典 c#篇》 第一章介绍了如何制作俄罗斯方块,自己试了试按照书上的步骤,可算是完成了。于是写下这篇文章留作纪念。1.类的设计在充...
[阅读全文]
-
网友评论