1、冒泡排序

冒泡原理：比较两个相邻的元素，如果第一个比第二个大，则交换两者的位置。

1）分析：一共需要进行 n-1 轮的比较，第一轮会将最大的数交换到 n-1 的位置，第二轮会将第二大的数交换到 n-2 的位置，如此类推。第一轮因为有n个数需要比较，那么就需要比较n-1次，第二轮因为已经求出最大的数了，只需要比较n-1个数，所以只需要比较n-2次便可。
2）所以，需要进行对一个n个元素的数组进行排序，一共需要进行n-1轮的比较，每一轮的比较结果是将剩余元素之中的最大值交换到最后位置，而每一轮需要n-i-1次的比较。

  1.        1, 4, 7, 2, 5, 8, 3, 6, 9, 0, 10
  2. 第一轮：1, 4, 2, 5, 7, 3, 6, 8, 0, 9, 10
  3. 第二轮：1, 2, 4, 5, 3, 6, 7, 0, 8, 9, 10
  4. 以此类推。。。
  • 代码实现
    1. public void bubbleSort(int[] arr) {
    2.   int temp;
    3.   for (int i = 0; i < arr.length - 1; i++) {
    4.       for (int j = 0; j < arr.length - i - 1; j++) {
    5.           if (arr[j] > arr[j + 1]) {
    6.               temp = arr[j];
    7.               arr[j] = arr[j + 1];
    8.               arr[j + 1] = temp;
    9.           }
    10.       }
    11.   }
    12. }

2、选择排序

1）原理：将待排序序列中的最小值放到已排序序列的末尾，直到待排序序列中的元素个数为0。
2）分析：第一次将未排序中的最小值放到序列的起始位置。然后再从未排序的序列中寻找最小的元素，然后存放在头部中已排序的序列的末尾。这样子数组序列就分成了两部分，前一部分是排好序的，后一部分是未排序的。直到未排序的序列个数为0，那么此时数组序列就已经排好序了。
3）所以，对于n个元素的数组，也可以进行比较，每一轮都会将已排序的当前序列的尾部和未排序中的元素进行比较，谁小就谁放在已排序序列的尾部。

  1. // 进行n-1轮的比较，每一轮都会将未排序中的元素和已排序中的尾部元素进行比较，谁小谁在前
  2. public void selectSort(int[] arr) {
  3.     int temp;
  4.     for (int i = 0; i < arr.length - 1; i++) {
  5.         for (int j = i + 1; j < arr.length; j++) {
  6.             if (arr[i] > arr[j]) {
  7.                 temp = arr[i];
  8.                 arr[i] = arr[j];
  9.                 arr[j] = temp;
  10.             }
  11.         }
  12.     }
  13. }

3、插入排序

1）原理：将待排序中的元素按照大小逐个的插入到已排序的序列中，直到未排序的个数为0。
分析：首先将数组的第一个元素当作是一个有序的已排序序列，后面的都是未排序序列。然后将后面的元素逐个的插入到前面已排序的序列之中。
2）需要进行 n-1 轮的比较，因为第一个元素默认时有序的，所以从第二个元素开始，和已排序的序列的尾部元素开始比较。将待排序的元素纳入待已排序的序列中，开始比较，从后往前，如果待插入元素比前一个元素小，就交换位置后继续比较，如果不是，终止排序。直到整个数组的最后一个元素排好序。

  • 代码实现
    1. public void insertSort(int[] arr) {
    2.   int current; // 是待排序中当前需要插入到有序序列的元素
    3.   for (int i = 1; i < arr.length; i++) {
    4.       current = arr[i];
    5.       int preIndex = i-1; // 有序序列中最后一个元素的下标
    6.       /**
    7.        * 使用待插入元素和已排序的元素逐个比较，从后往前的顺序
    8.        * 如果待插入元素比已排序的元素下，则继续比较，直到待插入元素已排序元素小或者相等时停止
    9.        */
    10.       while (preIndex >= 0 && arr[preIndex] > current) {
    11.           arr[preIndex + 1] = arr[preIndex]; // 已排序的元素往后移一位
    12.           preIndex--; // 已排序中待比较的元素
    13.       }
    14.       // 找到当前元素
    15.       arr[preIndex + 1] = current;
    16.   }
    17. }