1 冒泡排序
冒泡排序 (Bubble Sort) 一种交换排序，它的基本思想是：两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。
思路
从第 0 个到第 n 个，和相邻的元素进行相比，如果比相邻的大的话，那么就交换二者顺序，这样的话 0 到 n 范围内的最大的数就放到 n 的位置。接着下一次操作，第 0 个到第 n-1 个，将 0 到 n-1 范围内的最大值放到 n-1。重复执行，最后数组从小到大排列。
void BubbleSort(SqList *L)
{
int i,j;
for ( i = 1; i < L->length; i++)
{
for ( j = L->length - 1; j >= i; j--) /* 注意j是从后往前循环 */
{
if (L->r[j] > L->r[j+1]) /* 若前者大于后者（注意这里与上一算法差异) */
{
swap(L, j, j+1) /* 交换L->r[j]与L->r[j+1]的值 */
}
}
}
}
优化
如果再一次冒泡过程中，没有发生任何数组交换，那么该数组肯定是有序的，可以提前结束冒泡。
void BubbleSort2(SqList* L)
{
int i,j;
Status Flag = TRUE; /* flag用来作为标记 */
for ( i = 1; i < L->length && flag; i++) /* 若flag为true则退出循环 */
{
flag == FALSE;
for ( j = L->length - 1; j >= i; j--) /* 注意j是从后往前循环 */
{
if (L->r[j] > L->r[j+1]) /* 若前者大于后者（注意这里与上一算法差异) */
{
swap(L, j, j+1) /* 交换L->r[j]与L->r[j+1]的值 */
flag = TRUE; /* 如果有数据交换，则flag 为 true */
}
}
}
}
复杂度分析
O(n2)
2 快速排序
快速排序(Quick Sort)的基本思想是：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序的目的。
思路
最核心的思想是实现在一个范围内，以 n 为基准点，左边的数不大于基准点，右边的数不小于基准点。接下来左边的作为一个整体，同样实现上面的要求，右边的作为一个整体也实现上面的要求（左边的数不大于基准点，右边的数不小于基准点）。自顶向下执行下去，最后局部有序实现整体有序。
public static void quickSort(int array[],int start,int end){
if(start < end){
int n = findPoint(array,start,end);
quickSort(array,start,n-1);
quickSort(array,n+1,end);
}
}
public static int findPoint(int array[],int start,int end){
int temp = array[start];
while(start < end){
while(start < end && array[end] >= temp){
end--;
}
if(start < end){
array[start] = array[end];
}
while(start < end && array[start] <= temp){
start++;
}
if(start < end){
array[end] = array[start];
}
}
array[start] = temp;
return start;
}
复杂度分析
O(nlogn)，不稳定
快速排序优化
1. 优化选取枢轴
三数取中法：取三个关键字先进行排序，将中间数作为枢轴，一般是取左端、右端和中间三个数，也可以随机选取。
对于非常大的待排序的序列，还有个九数取中法：先从数组中分三次取样，每次取三个数， 三个样品各取出中数，然后从这三个中数当中再取出 一个中数作为枢轴。
/* 优化之一： 枢轴的选择 */
int m = low + (high - low) / 2 ; /* 计算数组中间元素的下标 */
if (L->r[low] > L->r[high])
swap(L, low, high); /* 交换左端与右端数据，保证左端小 */
if (L->r[m] > L->r[high])
swap(L, high, m); /* 交换中间与右端数据，保证中间小 */
if (L->r[m] > L->r[low])
swap(L, m, low); /* 交换中间与左端数据，保证左端小 */
/* 此时L.r[low]已经为整个序列左中右三个关键数字的中间值 */
2. 优化不必要的交换
/* 优化之二：优化不必要的交换 */
int Partition1(SqList *L, int low, int high){
int pivotkey;
pivotkey = L->r[low]; /* 用于表的第一个记录作枢轴记录 */
L->r[0] = pivotkey; /* 将枢轴关键字备份到L->r[0] */
while (low < high){
while (low < high && L->r[high] >= pivotkey)
high--;
L->r[low] = L->r[high]; /* 采用替换而不是交换的方式进行操作 */
while (low < high && L->r[low] <= pivotkey)
low++;
L->r[high] = L->r[low]; /* 采用替换而不是交换的方式进行操作 */
}
L->r[low] = L->r[0]; /* 将枢轴数值替换返回 L.r[low] */
return low; /* 返回枢轴所在位置 */
}
3. 优化小数组时的排序方案
如果数组非常小，其实快速排序反而不如直接插入排序来得更好(直接插入是简单排序中性能最好的)。
/* 优化之三： 优化小数组时的排序方案 */
#define MAX_LENGTH_INSERT_SORT 7 /* 数组长度阈值 */
/* 对顺序表L中的子序列L.r[low...high]作快速排序 */
void QSort(SqList *L, int low, int high){
int pivot;
if (high - low > MAX_LENGTH_INSERT_SORT){
/* 当high-low大于常数时用快速排序 */
pivot = Partition(L, low, high); /* 将L->r[low...high]一分为二，算出枢轴值pivot */
QSort(L, low, pivot - 1); /* 对低子表递归排序 */
QSort(L, pivot + 1, high); /* 对高子表递归排序 */
}
else /* 当high-low小于等于常数时用直接插入排序 */
InsertSort(L);
}
4. 优化递归操作
/* 优化之四: 尾递归 */
/* 对顺序表L中的子序列L-r[low...high]作快速排序 */
void QSort1(SqList *L, int low, int high)
{
int pivot;
if ((high - low) > MAX_LENGTH_INSERT_SORT)
{
while (low < high)
{
pivot = Partition(L, low, high); /* 将L->r[low...high]一分为二，算出枢轴值pivot */
QSort(L, low, pivot - 1); /* 对低子表递归排序 */
low = pivot + 1; /* 尾递归 */
}
}
else
InsertSort(L);
}