设被排序的数组是A，快速排序算法的基本思想是用数组的首元素作为标准将A划分成前，后两部分，比首元素小的元素构成数组前部分，比首元素大的元素构成数组的后部分，两个部分构成两个新的子问题，算法接着对这两部分递归地进行排序。
算法的关键在于怎样划分数组A二将其归约成两个子问题。主程序直接调用Quicksort(A,1,n)即可。

伪码描述

Quicksort()排序

查找首元素的位置Partition()

Partition()的作用是，将首元素(相当于一个哨兵)放置到一个合适的位置，这个位置之前的元素都比首元素小，这个元素之后的位置都比首元素大。

真实代码实现

时间复杂度分析和

划分工作量是，一位内每个元素都需要和首元素进行1次比较。
除了这个工作量外，就是两个子问题递归调用的工作量。


得到时间复杂度为

考虑极端不平衡的情况，即划分后的子问题的规模一个是0，另一个是n-1的情况。当输入是从小到大的序列或者是从大到小的逆序列时就会呈现这种划分。
这时的时间复杂度为


得到最坏情况下的复杂度为

插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

算法描述

一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：

动画演示

设输入是n个数组A[1…n]

真实代码实现

将被排序的数组分成相等两个数组，然后使用相同的算法对两个子数组分别排序，最后将两个排好序的数组归并成一个数组。
例如对8个数的数组L进行排序，先将L划分成L[1…4]和L[5…8]两个子数组，然后分别对这两个子数组进行排序。子数组的排序方法与原来数组的方法一样，以L[1…4]的排序为例，先将L[1…4]划分成L[1…2]和L[3…4]两个更小的子数组，分别对他们排序，然后进行归并。当对更小的数组L[1…2]进行排序时，按照算法需要进一步划分。划分结果是L[1]和L[2]，各含有1个元素，不再需要排序。这时算法将停止递归调用并开始归并。对于其他子问题，算法也同样处理。

伪码描述MergeSort()

MergeSort(A,p,q)

伪码描述Merge()

Merge()函数是将两个排好序的小数组A[p…q]与A[q+1…r]合并成一个排好序的大数组。归并的基本思想是：将这两个小数组分别复制到B与C中，A变成空数组，用来存放排好序的大数组。接着，算法比较B与C的首元素，如果哪个首元素比较小，就把它移到A中，比较1次，移走一个元素。如果其中一个变成空数组，那么就把剩下那个的所有元素顺序复制到A中，用伪码描述，过程如下：

二分归并完整代码实现

选择问题通常出现在实际应用中，最常见的是选最大，选最小，选中位数，选第二大等，这些问题可以给出统一的描述。

设L是n个元素的集合，从L中选出第k小的元素，其中1<=k<=n。这里的第k小的元素是指：当L中元素按照从小到大排好序之后，排在第k个位置的元素。当k=1时，选出的就是最小的元素，当k=n时，选出的就是最大元素。当k=n-1时，选出的计时第二大元素，当k=[n/2]就是中位数。