1、直接插入排序(direct Insert Sort)，基本思想是：顺序地将待排序的记录按其关键码的大小插入到已排序的记录子序列的适当位置。子序列的记录个数从1 开始逐渐增大，当子序列的记录个数与顺序表中的记录个数相同时排序完毕。
public void InsertSort(SeqList<int> sqList)
{for (int i = 1; i < sqList.Last; ++i) //假设第一个数据i=0是最小的，所以i是从1开始
{
if (sqList[i] < sqList[i - 1]) //依次判断I与前面的数据那个小，
{
int tmp = sqList[i]; //用tmp暂时保存当前小的数据
int j = 0;
for (j = i - 1; j >= 0&&tmp<sqList[j]; --j) //循环判断已经排序中的数据大小与当前的tmp比较
{
sqList[j + 1] = sqList[j]; //如果某个已经排序好的数据比tmp大，则让已经排序好的数据后移一位空一个位置
}
sqList[j + 1] = tmp; //这时候就让空出的那个位置放入tmp
}
}
}
2、冒泡排序(Bubble Sort)，基本思想是：将相邻的记录的关键码进行比较，若前面记录的关键码大于后面记录的关键码，则将它们交换，否则不交换。
public void BubbleSort(SeqList<int> sqList)
{
int tmp; //用于两个数据交换用
for (int i = 0; i < sqList.Last; ++i) //这层循环是用于冒泡排序需要循环n-1次
{
for (int j = sqList.Last - 1; j >= i; --j) //从后向前依次比较出最小的
{
if (sqList[j + 1] < sqList[j]) //把小的很前面大的交换数据
{
tmp = sqList[j + 1];
sqList[j + 1] = sqList[j];
sqList[j] = tmp;
}
}
}
}
3、简单选择排序(Simple Select Sort),算法的基本思想是：从待排序的记录序列中选择关键码最小（或最大）的记录并将它与序列中的第一个记录交换位置；然后从不包括第一个位置上的记录序列中选择关键码最小（或最大）的记录并将它与序列中的第二个记录交换位置；如此重复，直到序列中只剩下一个记录为止。
public void SimpleSelectSort(SeqList<int> sqList)
{
int tmp = 0; //用于数据交换
int t = 0; //用于记录当比较中最小数的index
for (int i = 0; i < sqList.Last; ++i)
{
t = i;
for (int j = i + 1; j <= sqList.Last; ++j) //循环比较找出最小数的index
{
if (sqList[t] > sqList[j]) //判断两个数中哪个数最小
{
t = j; //让最小的index等于t
}
}
tmp = sqList[i]; 让最小的数和当前总排序中最小index的数交换位置
sqList[i] = sqList[t];
sqList[t] = tmp;
}
}
4、快速排序(Quick Sort)，基本思想是：通过不断比较关键码，以某个记录为界（该记录称为支点） ，将待排序列分成两部分。其中，一部分满足所有记录的关键码都大于或等于支点记录的关键码，另一部分记录的关键码都小于支点记录的关键码。把以支点记录为界将待排序列按关键码分成两部分的过程，称为一次划分。对各部分不断划分，直到整个序列按关键码有序为止。
public void QuickSort(SeqList<int> sqList, int low, int high)
{
int i = low; //定义低的一端为low
int j = high; //高的一端为hight
int tmp = sqList[low]; //temp为基数
while (low < high) //判断高低端是否重合，如果重合说明已经排序完成
{
while ((low < high) && (sqList[high] >= tmp)) //如果高端的数大于基数，则继续往左检索直到检索出小于基数的数
{
--high;
}
sqList[low] = sqList[high]; //如果小于基数，则让这个低的数放入低端指向
++low; //低端向右移动一位
while ((low < high) && (sqList[low] <= tmp)) //判断低端的数是否小于基数，如果小于则继续向右检索直到检索出大于
{
++low;
}
sqList[high] = sqList[low]; //让大于基数的这个数放入高端
--high;
}
sqList[low] = tmp; //检索完毕，把基数放入空位处
if (i < low-1)
{
QuickSort(sqList, i, low-1); //检索完毕后，如果基数左侧还有数，则递归重新检索基数左侧
}
if (low+1 < j)
{
QuickSort(sqList, low+1, j); //检索完毕后，如果基数右侧还有数，则递归重新检索基数右侧
}
}
}
5、堆排序，堆分为最大堆和最小堆两种。最大堆的定义如下： 设顺序表sqList中存放了n个记录，对于任意的i(0≤i≤n-1)，如果2i+1<n时有 sqList[i]的关键码不小于 sqList[2i+1]的关键码；如果 2i+2<n 时有sqList[i] 的关键码不小于 sqList[2i+2] 的关键码，则这样的堆为最大堆。 如果把这 n 个记录看作是一棵完全二叉树的结点，则 sqList[0]对应完全二
叉树的根，sqList[1]对应树根的左孩子结点，sqList[2]对应树根的右孩子结点，sqList[3]对应 sqList[1]的左孩子结点，sqList[4]对应 sqList[2]的右孩子结点，如此等等。在此基础上，只需调整所有非叶子结点满足：sqList[i] 的关键码不小于 sqList[2i+1] 的关键码和 sqList[i] 的关键码不小于 sqList[2i+2] 的关键码，则这样的完全二叉树就是一个最大堆。
public void CreateHeap(SeqList<int> sqList, int low, int high) //low为数组最小index，high为数组长度
{
if ((low < high) && (high <= sqList.Last))
{
int j = 0;
int tmp = 0; //用于存放父节点的值
int k = 0;
for (int i = high / 2; i >= low; --i) //i为二叉树最下方的叶子结点的父节点（当前选中的父节点）
{
k = i; //当前的父节点
j = 2 * k + 1; //当前的左孩子
tmp = sqList[i]; //tmp存放父节点的值
while (j <= high)
{
if ((j < high) && (j + 1 <= high) && (sqList[j] < sqList[j + 1])) //判断有没有右孩子，如果有则比较左右孩子的值，把大的值大的值赋值给J
{
++j;
}
if (tmp < sqList[j]) 判断父节点的值与孩子节点的值那个大，如果孩子节点的大则把孩子节点的值给父节点，继续往下查找，值大的孩子节点为父节点
{
sqList[k] = sqList[j];
k = j;
j = 2 * k + 1;
}
else //跳出循环
{
j = high + 1;
}
}
sqList[k] = tmp; //最初父节点的值给最后（n）孩子节点，n为第n次比较后的孩子节点
}
}
}
使用
public void HeapSort(SeqList<int> sqList)
{
int tmp = 0;
CreateHeap(sqList, 0, sqList.Last); //创建最大堆
for (int i = sqList.Last; i > 0; --i) //取出堆顶元素，并重新创建最大堆，依次取出
{
tmp = sqList[0];
sqList[0] = sqList[i];
sqList[i] = tmp;
CreateHeap(sqList, 0, i-1);
}
}
6、归并排序，
基本思想
将待排序序列R[0...n-1]看成是n个长度为1的有序序列，将相邻的有序表成对归并，得到n/2个长度为2的有序表；将这些有序序列再次归并，得到n/4个长度为4的有序序列；如此反复进行下去，最后得到一个长度为n的有序序列。
综上可知：
归并排序其实要做两件事：
（1）“分解”——将序列每次折半划分。
（2）“合并”——将划分后的序列段两两合并后排序。
我们先来考虑第二步，如何合并？
在每次合并过程中，都是对两个有序的序列段进行合并，然后排序。这两个有序序列段分别为 R[low, mid] 和 R[mid+1, high]。先将他们合并到一个局部的暂存数组R2中，带合并完成后再将R2复制回R中。为了方便描述，我们称 R[low, mid] 第一段，R[mid+1, high] 为第二段。每次从两个段中取出一个记录进行关键字的比较，将较小者放入R2中。最后将各段中余下的部分直接复制到R2中。经过这样的过程，R2已经是一个有序的序列，再将其复制回R中，一次合并排序就完成了。
public void Merge(int[] array, int low, int mid, int high) {
int i = low; // i是第一段序列的下标
int j = mid + 1; // j是第二段序列的下标
int k = 0; // k是临时存放合并序列的下标
int[] array2 = new int[high - low + 1]; // array2是临时合并序列
// 扫描第一段和第二段序列，直到有一个扫描结束
while (i <= mid && j <= high) {
// 判断第一段和第二段取出的数哪个更小，将其存入合并序列，并继续向下扫描
if (array[i] <= array[j]) {
array2[k] = array[i];
i++;
k++;
} else {
array2[k] = array[j];
j++;
k++;
}
}
// 若第一段序列还没扫描完，将其全部复制到合并序列
while (i <= mid) {
array2[k] = array[i];
i++;
k++;
}
// 若第二段序列还没扫描完，将其全部复制到合并序列
while (j <= high) {
array2[k] = array[j];
j++;
k++;
}
// 将合并序列复制到原始序列中
for (k = 0, i = low; i <= high; i++, k++) {
array[i] = array2[k];
}
}
int i = 0;
// 归并gap长度的两个相邻子表
for (i = 0; i + 2 * gap - 1 < length; i = i + 2 * gap) {
Merge(array, i, i + gap - 1, i + 2 * gap - 1);
}
// 余下两个子表，后者长度小于gap
if (i + gap - 1 < length) {
Merge(array, i, i + gap - 1, length - 1);
}
}
public int[] sort(int[] list) {
for (int gap = 1; gap < list.length; gap = 2 * gap) {
MergePass(list, gap, list.length);
console.WriteLine("gap = " + gap + ":\t");
this.printAll(list);
}
return list;
}
把记录按步长 gap 分组，对每组记录采用直接插入排序方法进行排序。
随着步长逐渐减小，所分成的组包含的记录越来越多，当步长的值减小到 1 时，整个数据合成为一组，构成一组有序记录，则完成排序。
我们来通过演示图，更深入的理解一下这个过程。
在上面这幅图中：
初始时，有一个大小为 10 的无序序列。
在第一趟排序中，我们不妨设 gap1 = N / 2 = 5，即相隔距离为 5 的元素组成一组，可以分为 5 组。
接下来，按照直接插入排序的方法对每个组进行排序。
在第二趟排序中，我们把上次的 gap 缩小一半，即 gap2 = gap1 / 2 = 2 (取整数)。这样每相隔距离为 2 的元素组成一组，可以分为 2 组。
按照直接插入排序的方法对每个组进行排序。
在第三趟排序中，再次把 gap 缩小一半，即gap3 = gap2 / 2 = 1。 这样相隔距离为 1 的元素组成一组，即只有一组。
按照直接插入排序的方法对每个组进行排序。此时，排序已经结束。
需要注意一下的是，图中有两个相等数值的元素 5 和 5 。我们可以清楚的看到，在排序过程中，两个元素位置交换了。
所以，希尔排序是不稳定的算法。
int gap = list.length / 2;
while (1 <= gap) {
// 把距离为 gap 的元素编为一个组，扫描所有组
for (int i = gap; i < list.length; i++) {
int j = 0;
int temp = list[i];
// 对距离为 gap 的元素组进行排序
for (j = i - gap; j >= 0 && temp < list[j]; j = j - gap) {
list[j + gap] = list[j];
}
list[j + gap] = temp;
}
gap = gap / 2; // 减小增量
}
}
8、基数排序，它不需要比较关键字的大小。
它是根据关键字中各位的值，通过对排序的N个元素进行若干趟“分配”与“收集”来实现排序的。
不妨通过一个具体的实例来展示一下，基数排序是如何进行的。
设有一个初始序列为: R {50, 123, 543, 187, 49, 30, 0, 2, 11, 100}。
我们知道，任何一个阿拉伯数，它的各个位数上的基数都是以0~9来表示的。
所以我们不妨把0~9视为10个桶。
我们先根据序列的个位数的数字来进行分类，将其分到指定的桶中。例如：R[0] = 50，个位数上是0，将这个数存入编号为0的桶中。
分类后，我们在从各个桶中，将这些数按照从编号0到编号9的顺序依次将所有数取出来。
这时，得到的序列就是个位数上呈递增趋势的序列。
按照个位数排序： {50, 30, 0, 100, 11, 2, 123, 543, 187, 49}。
接下来，可以对十位数、百位数也按照这种方法进行排序，最后就能得到排序完成的序列。
public class RadixSort {// 获取x这个数的d位数上的数字
// 比如获取123的1位数，结果返回3
public int getDigit(int x, int d) {
int a[] = {
1, 1, 10, 100
}; // 本实例中的最大数是百位数，所以只要到100就可以了
return ((x / a[d]) % 10);
}
public void radixSort(int[] list, int begin, int end, int digit) {
final int radix = 10; // 基数
int i = 0, j = 0;
int[] count = new int[radix]; // 存放各个桶的数据统计个数
int[] bucket = new int[end - begin + 1];
// 按照从低位到高位的顺序执行排序过程
for (int d = 1; d <= digit; d++) {
// 置空各个桶的数据统计
for (i = 0; i < radix; i++) {
count[i] = 0;
}
// 统计各个桶将要装入的数据个数
for (i = begin; i <= end; i++) {
j = getDigit(list[i], d);
count[j]++;
}
// count[i]表示第i个桶的右边界索引
for (i = 1; i < radix; i++) {
count[i] = count[i] + count[i - 1];
}
// 将数据依次装入桶中
// 这里要从右向左扫描，保证排序稳定性
for (i = end; i >= begin; i--) {
j = getDigit(list[i], d); // 求出关键码的第k位的数字， 例如：576的第3位是5
bucket[count[j] - 1] = list[i]; // 放入对应的桶中，count[j]-1是第j个桶的右边界索引
count[j]--; // 对应桶的装入数据索引减一
}
// 将已分配好的桶中数据再倒出来，此时已是对应当前位数有序的表
for (i = begin, j = 0; i <= end; i++, j++) {
list[i] = bucket[j];
}
}
}
public int[] sort(int[] list) {
radixSort(list, 0, list.length - 1, 3);
return list；
}
}