应用介绍

排序算法汇总  

## 一. 插入排序

### 1.直接插入排序

- **思想**：每次将一个待排序的数据按照其关键字的大小插入到前面已经排序好的数据中的适当位置，直到全部数据排序完成。

- **时间复杂度**：O(n^2)  O(n)  O(n^2) （最坏 最好 平均）

- **空间复杂度**：O(1)

- **稳定性**： 稳定    每次都是在前面已排好序的序列中找到适当的位置，只有小的数字会往前插入，所以原来相同的两个数字在排序后相对位置不变。

```

// 插入排序

public static void insertSort(int[] array) {

    for (int i = 2; i < array.length; i++ ) {

        int val = array[i];

        int j = i -1;

        while (j >= 0 && array[j] > val) {  // array[j] > val

            array[j+1] = array[j];

            j--;

        }

        array[j+1] = val; //  array[j+1] 不是array[j]

    }

}

```   

### 2.希尔排序

- **思想**：希尔排序根据增量值对数据按下标进行分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整体采用直接插入排序得到有序数组，算法终止。

- **时间复杂度**：O(n2)   O(n) O(n1.5)  （最坏，最好，平均）

- **空间复杂度**：O(1)

- **稳定性**：不稳定    因为是分组进行直接插入排序，原来相同的两个数字可能会被分到不同的组去，可能会使得后面的数字会排到前面，使得两个相同的数字排序前后位置发生变化。

- **不稳定举例**:   4 3 3 2   按2为增量分组，则第二个3会跑到前面

```

public static void shellSort(int[] array) {

    int len;

    len = array.length / 2; // 分成n/2组

    while (len >= 1) {

        for (int i = len; i < array.length; ++i) { //对每组进行直接插入排序

            int temp = array[i];

            int j = i - len;

            while (j >= 0 && array[j] > temp) {

                array[j + len] = array[j];

                j -= len;

            }

            array[j + len] = temp;

        }

        len /= 2;

    }

}

```

## 二. 交换排序

### 3.冒泡排序

- **思想**：对待排序元素的关键字从后往前进行多遍扫描，遇到相邻两个关键字次序与排序规则不符时，就将这两个元素进行交换。这样关键字较小的那个元素就像一个泡泡一样，从最后面冒到最前面来。

- **时间复杂度**：最坏：O(n2)  最好: O(n)  平均: O(n2)

- **空间复杂度**：O(1)

- **稳定性**：稳定，相邻的关键字两两比较，如果相等则不交换。所以排序前后的相等数字相对位置不变。

```

public static void bubbleSort(int[] array) {

    boolean flag; // 用来判断当前这一轮是否有交换数值,若没有则表示已经排好许了

    for (int i = 0; i < array.length; i++) {

        flag = false;

        /**

         * 这边要注意 for (int j = array.length -1; j >= i + 1; j--)。 不要写成

         * for (int j =  i + 1; j < array.length ; j++)

         */

        for (int j = array.length -1; j >= i + 1; j--) {

            if (array[j -1 ] > array[j]) {

                //数据交换

                int temp = array[j - 1];

                array[j - 1] = array[j];

                array[j] = temp;

                //设置标志位

                flag = true;

            }

        }

        if (!flag) {

            break;

        }

    }

}

```

。。。。。。。。想了解详情请下载附件。