导语：面试官：常见的排序算法有哪些？可以写一下吗？

常见的排序算法如下：

性能比较如下：

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

冒泡排序

冒泡排序思路比较简单：

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

简单选择排序

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

快速排序

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

归并排序

假设初始序列含有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)); }}

本文内容由小苹整理编辑！