以下列出中常用的几种排序，只是简单实现了排序的功能，还有待改进，望指教（以下均假设数组的长度为n）：

1）冒泡排序：

依次比较相邻的两个元素，通过一次比较把未排序序列中最大（或最小）的元素放置在未排序序列的末尾。

public class BubbleSort { public static void sort(int data[]) {  for (int i = 0; i < data.length -1; i++) {   for (int j = 0; j < data.length - i - 1; j++) {    if (data[j] > data[j + 1]) {     int temp = data[j];     data[j] = data[j + 1];     data[j + 1] = temp;    }   }  } }}

 

2）选择排序：

每一次从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。

public class SelectionSort { public static void sort(int data[]) {  int minVal;  int minIndex;  for (int i = 0; i < data.length - 1; i++) {   minVal = data[i];   minIndex = i;   for (int j = i + 1; j < data.length; j++) {    if (data[j] < minVal) {     minVal = data[j];     minIndex = j;    }   }   if (minVal != data[i] && minIndex != i) {    data[minIndex] = data[i];    data[i] = minVal;   }  } }}

注：冒泡排序与选择排序有点类似，都是先通过依次比较将最小/大的元素放到最后；不同的是冒泡排序一次操作中，每次比较后，若需要都进行位置交换；而选择排序是每次比较之后，将最小的值的位置记录下来，最后与末尾位置交换。

3）插入排序：

将数列分为有序和无序两个部分，每次处理就是将无序数列的第一个元素与有序数列的元素从后往前逐个进行比较，找出插入位置，将该元素插入到有序数列的合适位置中。

public class InsertionSort { public static void sort(int data[]) {  for (int i = 1; i < data.length; i++) {   for (int j = i; j > 0; j--) {    if (data[j] < data[j - 1]) {     int temp = data[j];     data[j] = data[j - 1];     data[j - 1] = temp;    }   }  } }}

注：插入排序的特点是从序列的第二个元素开始，与第一个元素排序，完成一轮；第二轮从第三个元素，依次与前面比较，然后排序， 其实就是做冒泡排序。

4）归并排序：

将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。排序过程如下：

（1）申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列（2）设定两个指针，最初位置分别为两个已经排序序列的起始位置（3）比较两个指针所指向的元素，选择相对小的元素放入到合并空间（注：如果是降序排列则选择相对较大的元素放入到合并空间），并移动指针到下一位置（4）重复步骤3直到某一指针达到序列尾（5）将另一序列剩下的所有元素直接复制到合并序列尾

public class MergeSort { public static void sort(int data[], int start, int end) {  if (start < end) {   int mid = (start + end) / 2;   sort(data, start, mid);   sort(data, mid + 1, end);   merge(data, start, mid, end);  } } public static void merge(int data[], int start, int mid, int end) {  int temp[] = new int[end - start + 1];  int i = start;  int j = mid + 1;  int k = 0;  while (i <= mid && j <= end) {   if (data[i] < data[j]) {    temp[k++] = data[i++];   } else {    temp[k++] = data[j++];   }  }  while (i <= mid) {   temp[k++] = data[i++];  }  while (j <= end) {   temp[k++] = data[j++];  }  for (k = 0, i = start; k < temp.length; k++, i++) {   data[i] = temp[k];  } }}

例如：降序排{10，5，9，6}分为{10，5}，{9，6}然后{5，10}，{6，9}然后{5，6，9，10}。

5）快速排序：

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

public class QuickSort { public static void sort(int data[], int start, int end) {  if (end - start <= 0) {   return;  }  int last = start;  for (int i = start + 1; i <= end; i++) {   if (data[i] < data[start]) {    int temp = data[++last];    data[last] = data[i];    data[i] = temp;   }  }  int temp = data[last];  data[last] = data[start];  data[start] = temp;  sort(data, start, last - 1);  sort(data, last + 1, end); }}

示例

假设用户输入了如下数组：

下标	0	1	2	3	4	5
数据	6	2	7	3	8	9

创建变量i=0（指向第一个数据）, j=5(指向最后一个数据), k=6(为第一个数据的值)。

我们要把所有比k小的数移动到k的左面，所以我们可以开始寻找比6小的数，从j开始，从右往左找，不断递减变量j的值，我们找到第一个下标3的数据比6小，于是把数据3移到下标0的位置，把下标0的数据6移到下标3，完成第一次比较：

下标	0	1	2	3	4	5
数据	3	2	7	6	8	9

i=0 j=3 k=6

接着，开始第二次比较，这次要变成找比k大的了，而且要从前往后找了。递加变量i，发现下标2的数据是第一个比k大的，于是用下标2的数据7和j指向的下标3的数据的6做交换，数据状态变成下表：

下标	0	1	2	3	4	5
数据	3	2	6	7	8	9

i=2 j=3 k=6

称上面两次比较为一个循环。

接着，再递减变量j，不断重复进行上面的循环比较。

在本例中，我们进行一次循环，就发现i和j“碰头”了：他们都指向了下标2。于是，第一遍比较结束。得到结果如下，凡是k(=6)左边的数都比它小，凡是k右边的数都比它大：

下标	0	1	2	3	4	5
数据	3	2	6	7	8	9

如果i和j没有碰头的话，就递加i找大的，还没有，就再递减j找小的，如此反复，不断循环。注意判断和寻找是同时进行的。

然后，对k两边的数据，再分组分别进行上述的过程，直到不能再分组为止。

注意：第一遍快速排序不会直接得到最终结果，只会把比k大和比k小的数分到k的两边。为了得到最后结果，需要再次对下标2两边的数组分别执行此步骤，然后再分解数组，直到数组不能再分解为止（只有一个数据），才能得到正确结果。