1、冒泡排序

冒泡排序是知名排序方式，逻辑简单，实现起来也容易；
总的来说就是两层for循环，缺点就是时间复杂度较高。
一共进行n-1次循环，总比较次数：(n-1)+(n-2)+(n-3)……2+1=n*(n-1)/2，时间复杂度为O(n²)。
代码如下：

  1. public class BubbleSort {
  3.     public static void main(String[] args) {
  4.         int[] arr = {12, 45, 5677, 344, 56, 3, 546, 2435};
  5.         //冒泡排序
  6.         int[] bubbleSort = bubbleSort(arr);
  7.         System.out.println(Arrays.toString(bubbleSort));
  9.     }
  12.     /**
  13.      * 冒泡排序
  14.      *
  15.      * @param arr
  16.      */
  17.     public static int[] bubbleSort(int[] arr) {
  18.         //i控制循环次数，长度为len的数组只需要循环len-1次，i的起始值为0所以i<len-1
  19.         for (int i = 0; i < arr.length - 1; i++) {
  20.             //但是由于是由arr[j]跟arr[j+1]进行比较，所以为了保证arr[j+1]不越界，j<len-i-1
  21.             for (int l = 0; l < arr.length - i - 1; l++) {
  22.                 if (arr[l] > arr[l + 1]) {
  23.                     //交换两个数,//如果前一个数比后一个数大，则交换位置将大的数往后放。
  24.                     arr[l + 1] = arr[l + 1] ^ arr[l];
  25.                     arr[l] = arr[l + 1] ^ arr[l];
  26.                     arr[l + 1] = arr[l + 1] ^ arr[l];
  27.                 }
  28.             }
  29.         }
  30.         return arr;
  31.     }

2、选择排序

选择排序是比冒泡更为快速的排序方式，时间复杂度有所降低，实现思路如下：

  • 将第一个值看成最小值
  • 然后和后续的比较找出最小值和下标
  • 交换本次遍历的起始值和最小值
  • 说明：每次遍历的时候，将前面找出的最小值，看成一个有序的列表，后面的看成无序的列表，然后每次遍历无序列表找出最小值。

实现代码如下：

  1.  /**
  2.      * 选择排序
  3.      *
  4.      * @return
  5.      */
  6.     public static int[] selectSort(int[] arr) {
  7.         //第一次循环数组
  8.         for (int i = 0; i < arr.length - 1; i++) {
  9.             //定义最小数下标
  10.             int miniIndex = i;
  11.             //第二次循环数组
  12.             for (int l = i + 1; l < arr.length; l++) {
  13.                 //碰到比最小值小的，重新标记最小标
  14.                 if (arr[l] < arr[miniIndex]) {
  15.                     miniIndex = l;
  16.                 }
  17.             }
  18.             //交换下标对于数值
  19.             if (miniIndex != i) {
  20.                 arr[miniIndex] = arr[miniIndex] ^ arr[i];
  21.                 arr[i] = arr[miniIndex] ^ arr[i];
  22.                 arr[miniIndex] = arr[miniIndex] ^ arr[i];
  23.             }
  24.         }
  25.         return arr;
  26.     }

3、归并排序

归并排序体现了分治思想，把排序对象分割成两个，在进行比对大小，思路如下：

  • 将列表按照对等的方式进行拆分
  • 拆分小最小快的时候，在将最小块按照原来的拆分，进行合并
  • 合并的时候，通过左右两块的左边开始比较大小。小的数据放入新的块中
  • 说明：简单一点就是先对半拆成最小单位，然后将两半数据合并成一个有序的列表。

代码实现如下：

  1.  /**
  2.      * 归并排序
  3.      *
  4.      * @return
  5.      */
  6.     public static int[] mergeSort(int[] arr) {
  7.         if (arr.length<=1) {
  8.             return arr;
  9.         }
  10.         //得到数组长度中值
  11.         int num = arr.length >> 1;
  12.         int[] left = Arrays.copyOfRange(arr, 0, num);
  13.         int[] right = Arrays.copyOfRange(arr, num, arr.length);
  14.         //合并方法，递归
  15.         return merge(mergeSort(left), mergeSort(right));
  16.     }
  18.     //归并排序合并方法
  19.     private static int[] merge(int[] a, int[] b) {
  20.         int i = 0, j = 0, k = 0;
  21.         int[] result = new int[a.length + b.length];
  22.         while (i < a.length && j < b.length) {
  23.             if (a[i] <= b[j]) {
  24.                 result[k++] = a[i++];
  25.             } else {
  26.                 result[k++] = b[j++];
  27.             }
  28.         }
  29.         while (i < a.length) {
  30.             result[k++] = a[i++];
  31.         }
  32.         while (j < b.length) {
  33.             result[k++] = b[j++];
  34.         }
  35.         return result;
  36.     }

4、快速排序

快速排序是最近面试常考排序方法，建议多练习；
快速排序也体现了分治思想，思路如下：

  • 选择基点的值（随意，建议去下标中值）
  • 将比基点值小的值放在左边，比基点值大的放在右边，这样基点左边都是比基点小的，右边都是比基点大的
  • 分别对左右两边进行递归运算

代码如下：

  1. import java.util.Arrays;
  3. /**
  4.  * 快速排序
  5.  */
  6. public class QuickSort {
  7.     public static void main(String[] args) {
  8.         int[] arr = {14, 25, 255, 7, 6, 89, 52, -5, 58, -88, -9, 5845, 4};
  9.         quickSort(arr, 0, arr.length - 1);
  10.         System.out.println("arr:" + Arrays.toString(arr));
  11.     }
  13.     /**
  14.      * 排序方法
  15.      *
  16.      * @param arr   数组
  17.      * @param left  左下标
  18.      * @param right 右下标
  19.      */
  20.     private static void quickSort(int[] arr, int left, int right) {
  21.         int l = left;
  22.         int r = right;
  23.         int pivot = arr[(left + right) / 2];
  24.         int temp = 0;
  26.         while (l < r) {
  27.             //找到左边大于等于pivot的值下标
  28.             while (arr[l] < pivot) {
  29.                 l += 1;
  30.             }
  31.             //找到右边小于等于pivot的值下标
  32.             while (arr[r] > pivot) {
  33.                 r -= 1;
  34.             }
  35.             if (l >= r) {
  36.                 break;
  37.             }
  39.             //交换值
  40.             temp = arr[l];
  41.             arr[l] = arr[r];
  42.             arr[r] = temp;
  44.             //如果交换完成后，发现arr[l]==pivot,r--,r左移一位
  45.             if (arr[l] == pivot) {
  46.                 r -= 1;
  47.             }
  48.             //如果交换完成后，发现arr[l]==pivot,r--,r左移一位
  49.             if (arr[r] == pivot) {
  50.                 l += 1;
  51.             }
  53.             //如果l==r，错开，否则造成栈溢出
  54.             if (l == r) {
  55.                 l += 1;
  56.                 r -= 1;
  57.             }
  59.             //向左递归
  60.             if (left < r) {
  61.                 quickSort(arr, left, r);
  62.             }
  63.             //向右递归
  64.             if (right > l) {
  65.                 quickSort(arr, l, right);
  66.             }
  67.         }
  68.     }
  69. }