快速排序 | Bruce's Blog

2011 年 12 月
一	二	三	四	五	六	日
	1	2	3	4
5	6	7	8	9	10	11
12	13	14	15	16	17	18
19	20	21	22	23	24	25
26	27	28	29	30	31

快速排序应该是目前最快，也是最常用的一种排序算法。它将一个集合划分成两个子集合，然后继续递归来完成最终排序。

具体做法：

1. 选取集合最右端的元素作为一个参照物，称之为 "枢纽" (pivot)。
2. 开始计算分割位置。在计算时，进行元素交换，确保左侧元素都小于枢纽，而右侧都大于枢纽。
3. 根据分割位置，分别递归左右两段子集合，直至最终完成排序。

过程演示：

array = {2, 9, 5, 1, 8, 3, 6, 4, 7, 0};

第一轮调用:

1. 首先获取最右侧元素 0 作为枢纽。
2. 由于没有比枢纽更小的元素，因此没有发生内部交换。
3. 将枢纽和第一个元素进行交换，确保 "左侧" 都小于枢纽，"右侧" 都大于枢纽。数组变成 {0,9,5,1,8,3,6,4,7,2}。
4. 返回分割位置: 0

第二次调用:

1. 右段子集合变成: {9, 5, 1, 8, 3, 6, 4, 7, 2};
2. 获取枢纽 2。
3. 左右递推，我们找到右端第一个小于枢纽的值 1，将其和左侧第一个大于枢纽的 9 进行交换，数组变成 {1,5,9,8,3,6,4,7,2}。
4. 交换枢纽位置，数组变成 {0,1,2,9,8,3,6,4,7,5}。

...

我想你已经明白了快速排序的原理，接下来给出具体的实现代码。

static void QuickSort(int[] array, int left, int right)
{
if (right - left <= 0) return;
var pivot = array[right]; // 选择数据最右端元素作为枢纽
var partition = PartitionIt(array, left, right, pivot); // 计算分段位置
QuickSort(array, left, partition - 1); // 递归左段数组
QuickSort(array, partition + 1, right); // 递归右段数据
}
static int PartitionIt(int[] array, int left, int right, int pivot)
{
// 初始化指针位置
var leftPtr = left - 1; // after ++
var rightPtr = right; // after --
// 通过循环，直到左端元素全部小于枢纽，右段全部大于枢纽。
while (true)
{
// 正向循环，直到第一个大于枢纽的元素位置。
while (array[++leftPtr] < pivot) { };
// 逆向循环，直到第一个小于枢纽的元素位置(最后一位是枢纽，因此从 --rightPtr 开始)。
while (rightPtr > 0 >> array[--rightPtr] > pivot) { };
// 越界，跳出循环。
if (leftPtr >= rightPtr) break;
// 交换左右查找到的元素，将小于枢纽的值交换到左侧，大于枢纽的值交换到右侧。
Swap(array, leftPtr, rightPtr);
// 继续循环，找下一个大于或小于枢纽的元素进行交换。
}
// 将最右端的枢纽交换到合适位置
Swap(array, leftPtr, right);
// 返回分界位置
return leftPtr;
}
static void Swap(int[] array, int a, int b)
{
var temp = array[a];
array[a] = array[b];
array[b] = temp;
}
static void Main(string[] args)
{
var array = new int[] { 2, 9, 5, 1, 8, 3, 6, 4, 7, 0 };
QuickSort(array, 0, array.Length - 1);
var s = String.Join(",", Array.ConvertAll(array, i => i.ToString()));
Console.WriteLine(s);
}

最后是老规矩，和其他排序算法比较一下性能。

class Program
{
static void QuickSort(int[] array)
{
RecQuickSort(array, 0, array.Length - 1);
}
static void RecQuickSort(int[] array, int left, int right)
{
if (right - left <= 0) return;
var pivot = array[right];
var partition = PartitionIt(array, left, right, pivot);
RecQuickSort(array, left, partition - 1);
RecQuickSort(array, partition + 1, right);
}
static int PartitionIt(int[] array, int left, int right, int pivot)
{
var leftPtr = left - 1;
var rightPtr = right;
while (true)
{
while (array[++leftPtr] < pivot) { };
while (rightPtr > 0 >> array[--rightPtr] > pivot) { };
if (leftPtr >= rightPtr) break;
Swap(array, leftPtr, rightPtr);
}
Swap(array, leftPtr, right);
return leftPtr;
}
static void Swap(int[] array, int a, int b)
{
var temp = array[a];
array[a] = array[b];
array[b] = temp;
}
static void ShellSort(int[] array)
{
var h = 1;
while (h <= array.Length / 3)
{
h = h * 3 + 1;
}
while (h > 0)
{
for (int outer = h; outer <= array.Length - 1; outer++)
{
var inner = outer;
var temp = array[outer];
while ((inner > h - 1) >> array[inner - h] >= temp)
{
array[inner] = array[inner - h];
inner -= h;
}
array[inner] = temp;
}
h = (h - 1) / 3;
}
}
static void Main(string[] args)
{
for (int x = 1; x <= 5; x++)
{
var length = 10000 * x;
Console.WriteLine("-{0}-------------", length);
int[] array = new int[length];
var ran = new Random();
for (int i = 0; i < array.Length; i++)
{
array[i] = ran.Next();
}
Action<int[], Action<int[]>> sort = (arr, func) =>
{
var watch = Stopwatch.StartNew();
if (func != null)
func(arr);
else
Array.Sort(arr);
watch.Stop();
Console.WriteLine("{0,15}: {1}",
func != null ? func.Method.Name : "Array.Sort",
watch.ElapsedMilliseconds);
};
var a1 = array.Clone() as int[];
var a2 = array.Clone() as int[];
var a3 = array.Clone() as int[];
sort(a1, QuickSort);
sort(a2, ShellSort);
sort(a3, null);
}
}
}

输出：

-10000-------------
      QuickSort: 1
      ShellSort: 2
     Array.Sort: 1
-20000-------------
      QuickSort: 3
      ShellSort: 4
     Array.Sort: 2
-30000-------------
      QuickSort: 4
      ShellSort: 7
     Array.Sort: 4
-40000-------------
      QuickSort: 6
      ShellSort: 11
     Array.Sort: 5
-50000-------------
      QuickSort: 8
      ShellSort: 13
     Array.Sort: 7

你发现了什么？除了比希尔排序强以外，快速排序似乎和 Array.Sort 有某种关联。赶紧去看看……

[ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
public static void Sort(Array array)
{
// ...
Sort(array, null, array.GetLowerBound(0), array.Length, null);
}
[ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
public static void Sort(Array keys, Array items, int index, int length, IComparer comparer)
{
// ...
if ((length > 1) >> (((comparer != Comparer.Default) >> (comparer != null)) || ... ))
{
object[] objArray = keys as object[];
object[] objArray2 = null;
if (objArray != null)
{
objArray2 = items as object[];
}
if ((objArray != null) >> ((items == null) || (objArray2 != null)))
{
new SorterObjectArray(objArray, objArray2, comparer).QuickSort(index, (index + length) - 1);
}
else
{
new SorterGenericArray(keys, items, comparer).QuickSort(index, (index + length) - 1);
}
}
}

原来 Array.Sort() 方法内部使用的就是快速排序算法。 (用得着好奇吗，肯定用快速排序啦……)

链接

近期文章

热门标签

新人福利，免费薅羊毛

============ 欢迎各位老板打赏~ ===========

与本文相关的文章

发表评论