冒泡排序：
冒泡排序是相邻两节点进行比较，大的向后移一个，经过第一轮两两比较和移动，最大的元素移动到了最后，第二轮次大的位于倒数第二个，依次进行。这是最基本的冒泡排序，还可以进行一些优化。
优化一：如果某一轮两两比较中没有任何元素交换，这说明已经都排好序了，算法结束，可以使用一个Flag做标记，默认为false，如果发生交互则置为true，每轮结束时检测Flag，如果为true则继续，如果为false则返回。
优化二：某一轮结束位置为j，但是这一轮的最后一次交换发生在lastSwap的位置，则lastSwap到j之间是排好序的，下一轮的结束点就不必是j--了，而直接到lastSwap即可，代码如下：
void bubble_sort (int a[], int n) { int i, j, lastSwap, tmp; for (j=n-1; j>0; j=lastSwap) { lastSwap=0; //每一轮要初始化为0，防止某一轮未发生交换，lastSwap保留上一轮的值进入死循环 for (i=0; i<j; i++) { if (a[i] > a[i+1]) { tmp=a[i]; a[i]=a[i+1]; a[i+1]=tmp; //最后一次交换位置的坐标 lastSwap = i; } } } }
快速排序：
快速排序首先找到一个基准，下面程序以第一个元素作为基准（pivot），然后先从右向左搜索，如果发现比pivot小，则和pivot交换，然后从左向右搜索，如果发现比pivot大，则和pivot交换，一直到左边大于右边，此时pivot左边的都比它小，而右边的都比它大，此时pivot的位置就是排好序后应该在的位置，此时pivot将数组划分为左右两部分，可以递归采用该方法进行。快排的交换使排序成为不稳定的。
int one_sort(int a[],int l,int r)
{
int midd = a[l];
while(l<r)
{
while(l<r && midd <= a[r]) r--;
if(l<r) a[l++]=a[r];
while(l<r && midd >= a[l]) l++;
if(l<r) a[r--]=a[l];
}
a[l] = midd;
return l;
}
void quick_sort(int a[],int l,int r)
{
if(l<r){
int n = one_sort(a,l,r);
quick_sort(a,l,n-1);
quick_sort(a,n+1,r);
}
}
堆排序
堆排序是把数组看作堆，第i个结点的孩子结点为第2*i+1和2*i+2个结点（不超出数组长度前提下），堆排序的第一步是建堆，然后是取堆顶元素然后调整堆。建堆的过程是自底向上不断调整达成的，这样当调整某个结点时，其左节点和右结点已经是满足条件的，此时如果两个子结点不需要动，则整个子树不需要动，如果调整，则父结点交换到子结点位置，再以此结点继续调整。
下述代码使用的大顶堆，建立好堆后堆顶元素为最大值，此时取堆顶元素即使堆顶元素和最后一个元素交换，最大的元素处于数组最后，此时调整小了一个长度的堆，然后再取堆顶和倒数第二个元素交换，依次类推，完成数据的非递减排序。
堆排序的主要时间花在初始建堆期间，建好堆后，堆这种数据结构以及它奇妙的特征，使得找到数列中最大的数字这样的操作只需要O(1)的时间复杂度，维护需要logn的时间复杂度。堆排序不适宜于记录数较少的文件
void heapAdjust(int a[], int i, int nLength) { int nChild; int nTemp; for (nTemp = a[i]; 2 * i + 1 < nLength; i = nChild) { // 子结点的位置=2*（父结点位置）+ 1 nChild = 2 * i + 1; // 得到子结点中较大的结点 if ( nChild < nLength-1 && a[nChild + 1] > a[nChild]) ++nChild; // 如果较大的子结点大于父结点那么把较大的子结点往上移动，替换它的父结点 if (nTemp < a[nChild]) { a[i] = a[nChild]; a[nChild]= nTemp; } else // 否则退出循环 break; } } // 堆排序算法 void heap_sort(int a[],int length) { int tmp; // 调整序列的前半部分元素，调整完之后第一个元素是序列的最大的元素 //length/2-1是第一个非叶节点，此处"/"为整除 for (int i = length / 2 - 1; i >= 0; --i) heapAdjust(a, i, length); // 从最后一个元素开始对序列进行调整，不断的缩小调整的范围直到第一个元素 for (int i = length - 1; i > 0; --i) { // 把第一个元素和当前的最后一个元素交换， // 保证当前的最后一个位置的元素都是在现在的这个序列之中最大的 /// Swap(&a[0], &a[i]); tmp = a[i]; a[i] = a[0]; a[0] = tmp; // 不断缩小调整heap的范围，每一次调整完毕保证第一个元素是当前序列的最大值 heapAdjust(a, 0, i); } }
归并排序
归并排序是采用分治法（Divide and Conquer）的一个非常典型的应用。首先考虑下如何将将二个有序数列合并。这个非常简单，只要从比较二个数列的第一个数，谁小就先取谁，取了后就在对应数列中删除这个数。然后再进行比较，如果有数列为空，那直接将另一个数列的数据依次取出即可。这需要将待排序序列中的所有记录扫描一遍，因此耗费O(n)时间，而由完全二叉树的深度可知，整个归并排序需要进行.logn.次，因此，总的时间复杂度为O(nlogn)。
归并排序在归并过程中需 要与原始记录序列同样数量的存储空间存放归并结果，因此空间复杂度为O(n)。
归并算法需要两两比较，不存在跳跃，因此归并排序是一种稳定的排序算法。
void mergearray(int a[], int first, int mid, int last, int temp[]) { int i = first, j = mid + 1; int m = mid, n = last; int k = 0; while (i <= m && j <= n) { if (a[i] <= a[j]) temp[k++] = a[i++]; else temp[k++] = a[j++]; } while (i <= m) temp[k++] = a[i++]; while (j <= n) temp[k++] = a[j++]; for (i = 0; i < k; i++) a[first + i] = temp[i]; } void merge_sort(int a[], int first, int last, int temp[]) { if (first < last) { int mid = (first + last) / 2; merge_sort(a, first, mid, temp); //左边有序 merge_sort(a, mid + 1, last, temp); //右边有序 mergearray(a, first, mid, last, temp); //再将二个有序数列合并 } }
计数排序
如果通过比较进行排序，那么复杂度的下界是O(nlogn)，但是如果数据本身有可以利用的特征，可以不通过比较进行排序，就能使时间复杂度降低到O(n)。
计数排序要求待排序的数组元素都是整数，有很多地方都要去是0-K的正整数，其实负整数也可以通过都加一个偏移量解决的。
计数排序的思想是，考虑待排序数组中的某一个元素a，如果数组中比a小的元素有s个，那么a在最终排好序的数组中的位置将会是s+1，如何知道比a小的元素有多少个，肯定不是通过比较去觉得，而是通过数字本身的属性，即累加数组中最小值到a之间的每个数字出现的次数（未出现则为0），而每个数字出现的次数可以通过扫描一遍数组获得。
计数排序的步骤：
- 找出待排序的数组中最大和最小的元素（计数数组C的长度为max-min+1，其中位置0存放min，依次填充到最后一个位置存放max）
- 统计数组中每个值为i的元素出现的次数，存入数组C的第i项
- 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
- 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1（反向填充是为了保证稳定性）
以下代码中寻找最大和最小元素参考编程之美，比较次数为1.5n次。
计数排序适合数据分布集中的排序，如果数据太分散，会造成空间的大量浪费，假设数据为（1,2,3,1000000），这就需要1000000的额外空间，并且有大量的空间浪费和时间浪费。
void findArrMaxMin(int a[], int size, int *min, int *max) { if(size == 0) { return; } if(size == 1) { *min = *max = a[0]; return; } *min = a[0] > a[1] ? a[1] : a[0]; *max = a[0] <= a[1] ? a[1] : a[0]; int i, j; for(i = 2, j = 3; i < size, j < size; i += 2, j += 2) { int tempmax = a[i] >= a[j] ? a[i] : a[j]; int tempmin = a[i] < a[j] ? a[i] : a[j]; if(tempmax > *max) *max = tempmax; if(tempmin < *min) *min = tempmin; } //如果数组元素是奇数个，那么最后一个元素在分组的过程中没有包含其中， //这里单独比较 if(size % 2 != 0) { if(a[size -1] > *max) *max = a[size - 1]; else if(a[size -1] < *min) *min = a[size -1]; } } void count_sort(int a[], int b[], int n) { int max, min; findArrMaxMin(a, n, &min, &max); int numRange = max-min+1; int* counter = new int[numRange]; int i, j, k; for (k=0; k<numRange; k++) counter[k]=0; for (i=0; i<n; i++) counter[a[i]-min]++; for (k=1; k<numRange; k++) counter[k] += counter[k-1]; for (j=n-1; j>=0; j--) { int v = a[j]; int index = counter[v-min]-1; b[index]=v; counter[v-min]--; } }