常见的排序算法如下：

性能比较如下：

一般不会要求写太复杂的排序算法，能写几个简单的排序算法即可

冒泡排序

冒泡排序思路比较简单：

1. 将序列当中的左右元素，依次比较，保证右边的元素始终大于左边的元素；
2. （ 第一轮结束后，序列最后一个元素一定是当前序列的最大值；）
3. 对序列当中剩下的n-1个元素再次执行步骤1。
4. 对于长度为n的序列，一共需要执行n-1轮比较
5. （利用while循环可以减少执行次数）

简单选择排序

在要排序的一组数中，选出最小（或者最大）的一个数与第1个位置的数交换；然后在剩下的数中再找最小（或者最大）的与第2个位置的数交换，以此类推，知道第n-1个元素（倒数第二个数）和第n个元素（最后一个数）比较为止。

快速排序

1. 从数列中取出一个数作为基准数
2. 分区过程，将比它大的数全放到它的右边，小于或等于它的数全放到它的左边
3. 再对左右区间重复第二步，直到各区间只有一个数

归并排序

假设初始序列含有n个记录，则可看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到个长度为2或1的有序子序列，在两两归并，…，如此重复，直至得到一个长度为n的有序序列为止，这种排序方法称为2-路归并排序

方便大家粘贴，放一下文字格式

冒泡排序

public class BubbleSort {
 //交换元素顺序
 public static void swap(int[] a, int i, int j) {
 int temp = a[i];
 a[i] = a[j];
 a[j] = temp;
 }
 //冒泡排序
 public static void bubbleSort(int[] a) {
 for (int i=0; i<a.length - 1; i++) {
 for (int j=0; j<a.length - 1 - i; j++) {
 if (a[i] > a[i + 1]) {
 swap(a, i, i + 1);
 }
 }
 }
 }
 public static void main(String[] args) {
 int[] a = {1, 5, 2, 4, 7, 6};
 bubbleSort(a);
 //[1, 2, 4, 5, 6, 7]
 System.out.println(Arrays.toString(a));
 }
}

选择排序

public class SelectSort {
 public static void swap(int[] a, int i, int j) {
 int temp = a[i];
 a[i] = a[j];
 a[j] = temp;
 }
 public static void selectSort(int[] a) {
 for (int i=0; i<a.length; i++) {
 int min = a[i];
 int index = i;
 for (int j=i; j<a.length; j++) {
 if (a[j] < min) {
 min = a[j];
 index = j;
 }
 }
 if (index != i) {
 swap(a, i, index);
 }
 }
 }
 public static void main(String[] args) {
 int[] a = {1, 5, 2, 4, 7, 6};
 selectSort(a);
 //[1, 2, 4, 5, 6, 7]
 System.out.println(Arrays.toString(a));
 }
}

快速排序

public class QuickSort {
 public static int sort(int[] a, int low, int high) {
 int key = a[low];
 while (low < high) {
 //从high所指位置向前搜索找到第一个关键字小于key的记录和key互相交换
 while (low < high && a[high] >= key) {
 high--;
 }
 a[low] = a[high];
 //从low所指位置向后搜索，找到第一个关键字大于key的记录和key互相交换
 while (low < high && a[low] <= key) {
 low++;
 }
 a[high] = a[low];
 }
 //此时low和key相等
 a[low] = key;
 return low;
 }
 public static void quickSort(int[] a, int low, int high) {
 if (low < high) {
 int key = sort(a, low, high);
 quickSort(a, low, key - 1);
 quickSort(a, key + 1, high);
 }
 }
 public static void main(String[] args) {
 int[] a = {1, 5, 2, 4, 7, 6};
 quickSort(a, 0, a.length - 1);
 //[1, 2, 4, 5, 6, 7]
 System.out.println(Arrays.toString(a));
 }
}

归并排序

public class MergeSort {
 public static void sort(int[] src) {
 int[] temp = new int[src.length];
 msort(src,temp,0,src.length-1);
 }
 public static void msort(int[] src,int[] dest,int left,int right) {
 if (left < right) {
 int mid = (left + right) / 2;
 msort(src,dest,0,mid);
 msort(src,dest,mid+1,right);
 merge(src,dest,0,mid,right);
 }
 }
 public static void merge(int[] src,int[] dest,int left,int mid,int right) {
 int i = left;//左边数组的游标
 int j = mid + 1;//右边数组的游标
 int index = 0;//dest起一个中途存储的作用，这个是dest数组的游标
 while (i <= mid && j <= right) {
 if (src[i] <= src[j]) {
 dest[index++] = src[i++];
 } else {
 dest[index++] = src[j++];
 }
 }
 //复制左边剩余的数组
 while (i <= mid) {
 dest[index++] = src[i++];
 }
 //复制右边剩余的数组
 while (j <= right) {
 dest[index++] = src[j++];
 }
 index = 0;
 while (left <= right) {
 src[left++] = dest[index++];
 }
 }
 
 public static void main(String[] args) {
 int[] arr = {7,5,3,4,2,1,6,2,9,8};
 sort(arr);
 //[1, 2, 2, 3, 4, 5, 6, 7, 8, 9]
 System.out.println(Arrays.toString(arr));
 }
}