Java实现简单选择排序、冒泡排序、快速排序

排序是编程中必不可少的一个环节。那么选择一个好的排序算法会增加代码的运行效率。下边主要写一下编程中常用的几种排序算法。

排序的稳定性是指：在一组待排序记录中，如果存在任意两个相等的记录R和S，且待排序记录中R在S前，如果在排序后R依然在S前，即他们的前后位置在排序前后不发生改变，则称该算法为稳定的。不稳定的排序只需一个反例来说明，而稳定的算法则需要证明，因为我们无法验证所有的实例。

排序方法	平均复杂度	最坏情况下时间复杂度	额外空间复杂度	稳定性
简单选择排序	O(N^2)	O(N^2)	O(1)	不稳定
直接插入排序	O(N^2)	O(N^2)	O(1)	稳定
冒泡排序	O(N^2)	O(N^2)	O(1)	稳定
堆排序	O(N log 2 N)	O(N log 2 N)	O(1)	不稳定
快速排序	O( log 2N$)	O()	O(1)	不稳定

PS:简书不支持数据公式编辑器

()![https://img.haomeiwen.com/i2243690/da1c8b997a16c17c.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240]

冒泡排序

就是把最大的数字挪到最右边，比较相邻两个数据，谁大谁在右，指针可以都是从左往右，内循环要写成j-1-i

  private static void BubbleSort() {
    int arr[] = {44, 12, 59, 36, 62, 43, 94, 7, 35, 52, 85};

    int length = arr.length;
    boolean flag;
    int temp;
    for (int i = length - 1; i >= 0; i--) {
      flag = false;
      for (int j = 0; j < i; j++) {
        if (arr[j] > arr[j + 1]) {
          temp = arr[j];
          arr[j] = arr[j + 1];
          arr[j + 1] = temp;
          flag = true;
        }
      }
      print(arr);
      if (!flag) break;//这是过滤掉最后整个数组都有序的情况，这会增加一些性能，但是 评价复杂度是不会变的7
    }
  }

 public static void print(int[] arr) {
    if (arr != null) {
      for (int i = 0; i < arr.length; i++) {
        System.out.print(arr[i] + "-");
      }
    }
    System.out.println();
  }

打印结果

12-44-36-59-43-62-7-35-52-85-94-
12-36-44-43-59-7-35-52-62-85-94-
12-36-43-44-7-35-52-59-62-85-94-
12-36-43-7-35-44-52-59-62-85-94-
12-36-7-35-43-44-52-59-62-85-94-
12-7-35-36-43-44-52-59-62-85-94-
7-12-35-36-43-44-52-59-62-85-94-
7-12-35-36-43-44-52-59-62-85-94-

• 时间复杂度：O(N的平方)。

简单选择排序

思想：找到最小的一个数，并与前面的数交换，依次排列