1.冒泡排序

  1.     //冒泡排序，依次比较相邻的两个元素的大小，如果前面的大于后面的，那么交换两者位置
  2.     public static void bubbleSort(int[] a) {
  3.         int temp;
  4.         for (int i = 1; i < a.length; i++) {
  5.             for (int j = 0; j < a.length - i; j++) {
  6.                 if (a[j] > a[j + 1]) {
  7.                     temp = a[j];
  8.                     a[j] = a[j + 1];
  9.                     a[j + 1] = temp;
  10.                 }
  11.             }
  12.             System.out.print("第" + i + "步排序结果");
  13.             for (int k = 0; k < a.length; k++) {
  14.                 System.out.print(" " + a[k]);
  15.             }
  16.             System.out.print("\n");
  17.         }
  18.     }

调用：

  1.     int a[] = {118, 101, 105, 127, 112};
  2.     bubbleSort(a);

输出

  1. 第1步排序结果 101 105 118 112 127
  2. 第2步排序结果 101 105 112 118 127
  3. 第3步排序结果 101 105 112 118 127
  4. 第4步排序结果 101 105 112 118 127

2.选择排序

  1.    /**
  2.     * 选择排序，找出最小的，和第一个元素交换顺序，再找出剩下的里面最小的那个和第二个元素交换位置，以此类推
  3.     */
  4.     public static void selectSort(int[] a) {
  5.         int index, temp;
  6.         for (int i = 0; i < a.length; i++) {
  7.             index = i;
  8.             for (int j = 1 + 1; j < a.length; j++) {
  9.                 if (a[j] < a[index]) {
  10.                     index = j;
  11.                 }
  12.             }
  13.             if (index != i) {
  14.                 temp = a[i];
  15.                 a[i] = a[index];
  16.                 a[index] = temp;
  17.             }
  18.             System.out.print("第" + i + "步排序结果");
  19.             for (int k = 0; k < a.length; k++) {
  20.                 System.out.print(" " + a[k]);
  21.             }
  22.             System.out.print("\n");
  23.         }
  24.     }

调用：

  1.     int a[] = {118, 101, 105, 127, 112};
  2.     selectSort(a);

输出：

  1. 第0步排序结果 105 101 118 127 112
  2. 第1步排序结果 105 101 118 127 112
  3. 第2步排序结果 105 101 112 127 118
  4. 第3步排序结果 105 101 127 112 118
  5. 第4步排序结果 105 101 127 118 112

3.插入排序

  1.     //插入排序，先将前两个元素进行排序，然后将第三个和前两个比较插入合适的位置，以此类推
  2.     public static void insertionSort(int[] a) {
  3.         int temp, j;
  4.         for (int i = 1; i < a.length; i++) {
  5.             temp = a[i];
  6.             j = i - 1;
  7.             while (j >= 0 && temp < a[j]) {
  8.                 a[j + 1] = a[j];
  9.                 j--;
  10.             }
  11.             a[j + 1] = temp;
  13.             System.out.print("第" + i + "步排序结果");
  14.             for (int k = 0; k < a.length; k++) {
  15.                 System.out.print(" " + a[k]);
  16.             }
  17.             System.out.print("\n");
  18.         }
  19.     }

调用：

  1.     int a[] = {118, 101, 105, 127, 112};
  2.     insertionSort(a);

输出：

  1. 第1步排序结果 101 118 105 127 112
  2. 第2步排序结果 101 105 118 127 112
  3. 第3步排序结果 101 105 118 127 112
  4. 第4步排序结果 101 105 112 118 127

4. shell排序算法

  1.   /*
  2.     shell排序算法（缩小增量排序、希尔排序），
  3.     将有n个元素的数组分为n/2个数字序列，
  4.     第一个和第n/2+1个元素为一对进行排序，
  5.     然后再分为n/4个序列，重复上述步骤进行排序
  6.      */
  7.     public static void shellSort(int[] a) {
  8.         int temp, m = 0;
  9.         for (int r = a.length / 2; r >= 1; r /= 2) {
  10.             for (int i = r; i < a.length; i++) {
  11.                 temp = a[i];
  12.                 int j = i - r;
  13.                 while (j >= 0 && temp < a[j]) {
  14.                     a[j + r] = a[j];
  15.                     j -= r;
  16.                 }
  17.                 a[j + r] = temp;
  18.             }
  19.             m++;
  20.             System.out.print("第" + m + "步排序结果");
  21.             for (int k = 0; k < a.length; k++) {
  22.                 System.out.print(" " + a[k]);
  23.             }
  24.             System.out.print("\n");
  25.         }
  26.     }

调用：

  1.     int a[] = {118, 101, 105, 127, 112};
  2.     shellSort(a);

输出：

  1. 第1步排序结果 105 101 112 127 118
  2. 第2步排序结果 101 105 112 118 127

5. 快速排序算法

  1.     /**
  2.      * 快速排序算法
  3.      * 设定一个分界值，通过该分界值将数组分为左右两个部分
  4.      * 将大于等于分界值的数据集中到数组右边，小于分界值的数据集中到数组左边。
  5.      * 然后左右的数据可以分别重复上面的步骤进行独立排序
  6.      */
  7.     public static void quickSort(int[] arr, int left, int right) {
  8.         int lTemp = left, rTemp = right;
  9.         int temp;
  10.         int f = arr[(left + right) / 2];//分界值
  11.         System.out.print("当前排序：");
  12.         for (int anArr : arr) {
  13.             System.out.print(" " + anArr);
  14.         }
  15.         System.out.print("\n");
  16.         System.out.println("分界值：" + f+ " left："+left+ " right："+right);
  17.         while (lTemp < rTemp) {
  18.             while (arr[lTemp] < f) {
  19.                 ++lTemp;
  20.             }
  21.             while (arr[rTemp] > f) {
  22.                 --rTemp;
  23.             }
  24.             if (lTemp <= rTemp) {
  25.                 temp = arr[lTemp];
  26.                 arr[lTemp] = arr[rTemp];
  27.                 arr[rTemp] = temp;
  28.                 --rTemp;
  29.                 ++lTemp;
  30.             }
  31.         }
  32.         if (lTemp == rTemp) {
  33.             lTemp++;
  34.         }
  35.         if (left < rTemp) {
  36.             quickSort(arr, left, lTemp - 1);//递归调用
  37.         }
  38.         if (right > lTemp) {
  39.             quickSort(arr, rTemp + 1, right);//递归调用
  40.         }
  41.     }

调用：

  1.         int a[] = {118, 101, 105, 127, 112};
  2.         quickSort(a, 0, a.length - 1);
  3.         System.out.print("\n");
  4.         System.out.print("排序结果 " );
  5.         for (int anA : a) {
  6.             System.out.print(" " + anA);
  7.         }

输出：

  1. 当前排序： 118 101 105 127 112
  2. 分界值：105 left：0 right：4
  3. 当前排序： 105 101 118 127 112
  4. 分界值：105 left：0 right：1
  5. 当前排序： 101 105 118 127 112
  6. 分界值：127 left：2 right：4
  7. 当前排序： 101 105 118 112 127
  8. 分界值：118 left：2 right：3
  10. 排序结果  101 105 112 118 127

6. 堆排序算法

  1.     /*
  2.     堆排序算法
  3.     将数组构建为一个二叉树(大根堆)，然后将每个节点和两个子节点进行比较，父节点必须必两个子节点都大，否则交换顺序。
  4.     最终根节点便是最大的那个值，拿出这个值，放入数组最末端，
  5.     将二叉树的终结点放入根节点位置，再重复之前的操作，拿出剩下的值中最大的，放入之前那个值的前面，。
  6.     再重复这种操作。。最终完成排序，
  7.     */
  8.     public static void heapSort(int[] a, int n) {
  9.         for (int i = n / 2; i >= 0; i--) {//将a[0.n-1]建成大根堆
  10.             while (2 * i + 1 < n) {//第i个节点的右子树（关于某个节点的左右子树编号计算公式请查看《java常用算法手册》第66页 第二章 数据结构 2.7 树结构 ）
  11.                 int j = 2 * i + 1;
  12.                 if ((j + 1) < n) {
  13.                     if (a[j] < a[j + 1]) {//若左子树小于右子树，则需要比较右子树
  14.                         j++;//序号加1，指向右子树，（左子树序号+1=右子树序号，详情参考《java常用算法手册》）
  15.                     }
  16.                 }
  17.                 if (a[i] < a[j]) {//比较i与j为序号的数据（父节点于子节点的值）
  18.                     int temp = a[i];
  19.                     a[i] = a[j];
  20.                     a[j] = temp;
  21.                     i = j;//堆被破坏，需要重新调整
  22.                 } else {
  23.                     break;
  24.                 }
  25.             }
  26.         }
  27.         //输出构成的堆
  28.         System.out.print("原数据构成的堆:");
  29.         for (int h = 0; h < n; h++) {
  30.             System.out.print(" " + a[h]);
  31.         }
  32.         System.out.print("\n");
  34.         for (int i = n - 1; i > 0; i--) {
  35.             int temp = a[0];//与第i个记录交换
  36.             a[0] = a[i];
  37.             a[i] = temp;
  38.             int k = 0;
  39.             while (2 * k + 1 < i) {//第i个节点有右子树
  40.                 int j = 2 * k + 1;
  41.                 if ((j + 1) < i) {
  42.                     if (a[j] < a[j + 1]) {//若左子树小于右子树，则需要比较右子树
  43.                         j++;//序号增加1，指向右子树
  44.                     }
  45.                 }
  46.                 if (a[k] < a[j]) {//比较k与j为序号的数据（父节点于子节点中的那个较大值）
  47.                     temp = a[k];//小于，交换位置
  48.                     a[k] = a[j];
  49.                     a[j] = temp;
  50.                     k = j;
  51.                 } else {//父节点就是三个节点中的最大值，跳出
  52.                     break;
  53.                 }
  54.             }
  55.             System.out.print("第" + (n - i) + "步排序结果");
  56.             for (int h = 0; h < n; h++) {
  57.                 System.out.print(" " + a[h]);
  58.             }
  59.             System.out.print("\n");
  60.         }
  61.     }

调用：

  1.  int a[] = {118, 101, 105, 127, 112};
  2.  heapSort(a, a.length);

输出：

  1. 原数据构成的堆: 127 118 105 101 112
  2. 第1步排序结果 118 112 105 101 127
  3. 第2步排序结果 112 101 105 118 127
  4. 第3步排序结果 105 101 112 118 127
  5. 第4步排序结果 101 105 112 118 127

7. 合并排序

  1.     /**
  2.      * 合并排序
  3.      * 将待排序数据序列看做有n个长度为1的有序字表组成，
  4.      * 将他们两两合并，得到长度为2的坐杆有序字表
  5.      * 然后再将这些字表两两合并，得到长度为4的有序子表，
  6.      * 一直重复到最后字表长度为n，完成排序。
  7.      * 此合并方法以二路合并为例，这种排序算法往往需要申请较大的辅助空间，这个辅助空间和待排序原始序列空间一样多。
  8.      */
  9.     public static void mergeSort(int a[], int n) {
  10.         int count = 0;//排序步骤
  11.         int len = 1;//有序序列的长度
  12.         int f = 0;//变量f做标志
  13.         int[] p = new int[n];
  14.         while (len < n) {
  15.             if (f == 1) {
  16.                 mergeOne(p, a, n, len);//p合并到a
  17.             } else {
  18.                 mergeOne(a, p, n, len);//a合并到p
  19.             }
  20.             len *= 2;//增加有序序列长度
  21.             f = 1 - f;
  22.             count++;
  23.             System.out.print("第" + count + "步排序结果：");
  24.             for (int anA : a) {
  25.                 System.out.print(" " + anA);
  26.             }
  27.             System.out.print("\n");
  28.         }
  29.         if (f == 1) {
  30. //            for (int h = 0; h < n; h++) {//将p中的数据复制回数组a
  31. //                a[h] = p[h];
  32. //            }
  33.             System.arraycopy(p, 0, a, 0, n);//将p中的数据复制回数组a
  34.         }
  36.     }
  39.     /**
  40.      * 合并一次，合并一次后的结果主要看b，因为是从a合并到b
  41.      *
  42.      * @param a   待合并的序列a,从a合并到b
  43.      * @param b   待合并的序列b，从a合并到b
  44.      * @param n   原数组的长度
  45.      * @param len 有序序列的长度
  46.      */
  47.     static void mergeOne(int a[], int b[], int n, int len) {
  48.         int s = 0;
  49.         while (s + len < n) {
  50.             int e = s + 2 * len - 1;
  51.             if (e >= n) {//最后一段可能少于len个节点
  52.                 e = n - 1;
  53.             }
  54.             //相邻有序段合并
  55.             int k = s, i = s, j = s + len;
  56.             while (i < s + len && j <= e) {//如果两个有序表都未结束时，循环比较
  57.                 if (a[i] <= a[j]) {//将较小的元素复制的b中
  58.                     b[k++] = a[i++];
  59.                 } else {
  60.                     b[k++] = a[j++];
  61.                 }
  62.             }
  63.             while (i < s + len) {//未合并的部分复制到数据b中
  64.                 b[k++] = a[i++];
  65.             }
  66.             while (j <= e) {
  67.                 b[k++] = a[j++];
  68.             }
  69.             s = e + 1;
  70.         }
  71.         if (s < n) {
  72.             for (; s < n; s++) {
  73.                 b[s] = a[s];
  74.             }
  75.         }
  76.     }

调用：

  1.     int a[] = {118, 101, 105, 127, 112};
  2.     mergeSort(a, a.length);

输出：

  1. 第1步排序结果： 118 101 105 127 112
  2. 第2步排序结果： 101 105 118 127 112
  3. 第3步排序结果： 101 105 118 127 112

8. 排序算法的计算复杂度

每一种排序算法都各有优缺点，我们要根据实际问题的需要选择合适的、高效的算法进行排序。下面是这几种排序算法的计算复杂度。

  1. 冒泡排序：平均速度为O(n²)，最坏情况下的速度为O(n²)；
  2. 选择排序：平均速度为O(n²)，最坏情况下的速度为O(n²)；
  3. 快速排序：平均速度为O(n²)，最坏情况下的速度为O(n²)；
  4. 插入排序：平均速度为O(nlogn)，最坏情况下的速度为O(n²)；
  5. 堆  排 序：平均速度为O(nlogn)，最坏情况下的速度为O(nlogn)；
  6. 合并排序：平均速度为O(nlogn)，最坏情况下的速度为O(nlogn)；
  7. Shell排序：平均速度为O(n^(3/2))，最坏情况下的速度为O(n²)；

函数O(n²)说明：

  1. 一个算法执行所耗费的时间，从理论上是不能算出来的。
  2. 因为不同的机器，硬件和软件环境不一样，另外还有一些其他因素的影响，
  3. 所以只能用一个函数来表示出来
  4. O(n²)=C*n²，C代表一个常数
  5. 举例说明：
  6. 比如，一个长度为5的数组，进行冒泡排序，最坏的情况就是将已有数组进行逆序。
  7. 每一个元素需要和其他元素比较一次，如果第一个和第二个比较过了，
  8. 那么第二个就不用和第一个再进行比较，所以两两比较的次数也就是4+3+2+1 = 10次；
  9. 如果数组的长度为n，那比较次数就是 (n-1)+(n-2)+......+1 = n(n-1)/2次；
  10. n(n-1)/2 = 0.5*n*(n-1);
  11. 这里0.5就是上面的常数C，因为并不一定都是最坏的情况，还有其他各种因素的影响，
  12. 这个常数不一定都是0.5，所以可以用C来代替0.5表示一个常数。
  13. 而当n足够大时，n-1 ≈ n，所以0.5*n*(n-1) ≈ C*n*n，也就是C*n²，用函数表示就是O(n²)