九大排序算法

一、排序算法

1、冒泡排序

• 从左到右不断交换相邻逆序的元素，在一轮的循环之后，可以让未排序的最值元素上浮到右侧。

• 在一轮循环中，如果没有发生交换，那么说明数组已经是有序的，此时可以直接退出。

时间复杂度：O(n^2)

稳定

//改进一点

        int temp = 0;
        boolean flag = true;  //标识是否进行过交换
        for (int i = 0; i < arr.length - 1 && flag; i++){
   
            flag = false;
            for (int j = arr.length -2; j >=i; j--) {
   
                if (arr[j] > arr[j + 1]) {
   
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    flag = true;
                }
            }
        }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

2、直接选择排序

• 和冒泡遍历一样，每轮循环中，通过交换下标，直至遍历完，再交换一次值，相比冒泡排序交换次数减少许多

时间复杂度：O(n^2)

不稳定

• 从数组中选择最小元素，将它与数组的第一个元素交换位置。再从数组剩下的元素中选择出最小的元素，将它与数组的第二个元素交换位置。不断进行这样的操作，直到将整个数组排序。

• 选择排序需要 ~N2/2 次比较和 ~N 次交换，它的运行时间与输入无关，这个特点使得它对一个已经排序的数组也需要这么多的比较和交换操作。

 		for (int i = 0; i < arr.length - 1; i++) {
   
            int min = i;
            for (int j = i + 1; j < arr.length ; j++) {
   
                if (arr[j] < arr[min]) {
   
                    min = j;
                }
            }
            if(min!=i){
   
                int temp = arr[i];
                arr[i] = arr[min];
                arr[min] = temp;
            }
        }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

3、直接插入排序

• 类似整理扑克牌，从左至右，保证遍历过序列（即遍历点的左侧）为有序的，遍历到的某个值依次与左侧有序的序列值比较，并在保证序列有序情况下插入。

时间复杂度：O(n^2)

稳定

• 每次都将当前元素插入到左侧已经排序的数组中，使得插入之后左侧数组依然有序。

  对于数组 {3, 5, 2, 4, 1}，它具有以下逆序：(3, 2), (3, 1), (5, 2), (5, 4), (5, 1), (2, 1), (4, 1)，插入排序每次只能交换相邻元素，令逆序数量减少 1，因此插入排序需要交换的次数为逆序数量。

  插入排序的时间复杂度取决于数组的初始顺序，如果数组已经部分有序了，那么逆序较少，需要的交换次数也就较少，时间复杂度较低。

  • 平均情况下插入排序需要 ~N2/4 比较以及 ~N2/4 次交换；
  • 最坏的情况下需要 ~N2/2 比较以及 ~N2/2 次交换，最坏的情况是数组是倒序的；
  • 最好的情况下需要 N-1 次比较和 0 次交换，最好的情况就是数组已经有序了。

        for (int i = 1; i < arr.length; i++) {
   
            int curtValue = arr[i];
            int InsertIndex = i-1;
            while (InsertIndex >= 0 && curtValue<arr[InsertIndex]){<
1
2
3
4