快速排序算法

2019-11-06 06:31:52

字体：大中小

来源：转载

供稿：网友

快速排序算法通常是用于排序的最佳选择，尽管它在最坏情况下的运行时间是O(n²)，但平均性能是O(nlgn)，并且逻辑简单。快速排序算法一共有两个子过程

Partition(int[] array,int p,int r)，它把数组的p至r部分就地重排，并返回一个q，并且使数组满足以下条件：q左边的数值全部小于或等于q的数值，q右边的数值都大于或等于q的数值。QuickSort(int[] array,int p,int r)，它会巧妙地调用Partition函数，以及递归调用自身，最终完成对数组array的排序。

下面首先来看以下Partition函数

static int Partition(int[] array, int p, int r){ int x = array[r]; int i = p - 1; for (int j = p; j < r; j++) { if (array[j] < x) { i++; //exchange array[i] and array[j] int temp = array[i]; array[i] = array[j]; array[j] = temp; } } //exchange array[i+1] and array[r] int temp2 = array[i + 1]; array[i + 1] = array[r]; array[r] = temp2; return i + 1;}

假设输入的数组arrray为7, 2, 101, 15, 1, 6, 21，那么调用Partition(array, 0, 6)的话，会返回5，并且数组被修改为7, 2, 15, 1, 6, 21, 101。可以看出来，排序后的数组的索引位置为5的值是21，在此之前的所有数字都小于或等于21，在此之后的所有数字都大于等于21。

接下来看看QuickSort函数

static void QuickSort(int[] array, int p, int r){ if (p < r) { int q = Partition(array, p, r); QuickSort(array, p, q -1); QuickSort(array, q + 1, r); }}

QuickSort函数在调用Partition函数之后，获取到一个q值，这个q在数组中的位置已经是正确的了，所以，无需再对q位置的数组进行排序，所以会递归调用两次QuickSort，第一次调用的最后一个参数是q-1，第二次调用的最后一个参数是q+1。知道p>=r，说明整个数组的所有位置都已经正确的排序了。

下面是main函数

static void Main(string[] args){ int[] array = { 7, 2, 101, 15, 1, 6, 21 }; QuickSort(array, 0, array.Length - 1);}

上一篇：POJ1251 Jungle Roads(最小生成树，Kruskal)

下一篇：多线程（基本知识）