递进的方式　

　　插入，希尔，归并

　　冒泡，选择，快速

　　堆排序（树里）

一：分析排序

1.哪几个方面

　　时间效率

　　空间效率

　　交换次数

　　稳定性

2.稳定性的意义

二：插入排序

1.理解

　　可以理解成抓牌

2.代码

package com.jun.algorithm.foundation.thought;

import org.junit.Test;

import java.util.Arrays;

/**
 * 插入排序
 * 例如打牌场景就是如此
 * 

 * 具体的步骤：
 * 将数组分成已排序段和未排序段，初始化已排序段只有一个元素
 * 到未排序段取元素插入已排序段，保证有序
 * 重复上述操作
 * 

 * 稳定性：稳定
 *
 * @author caojun
 */
public class InsertSort {
    /**
     * 排序
     * 时间复杂度
     * n^2，最好的情况是n
     *
     * @param arr 要排序的数组
     * @return 排序后的数组
     */
    private int[] insert(int[] arr) {
        // 从1开始，第一个不要排序，数组从i进行分开
        for (int i = 1; i < arr.length; i++) {
            int data = arr[i];
            // 将数据插入到已经排好序段，从尾往头进行比较，可以降低时间复杂度，即是break
            // j从i-1开始，就是从当前的前一个开始，与当前的数据进行比较
            int j;
            for (j = i - 1; j >= 0; j--) {
                if (arr[j] > data) {
                    arr[j + 1] = arr[j];
                } else {
                    break;
                }
            }
            // 赋值
            arr[j + 1] = data;
        }
        return arr;
    }

    @Test
    public void test() {
        int[] arr = {1, 3, 2, 7, 5};
        int[] newArr = insert(arr);
        System.out.println(Arrays.toString(newArr));
    }

}

三：希尔排序

1.思想

　　按照几个分段进行排序

　　目标就是让更多的数据已经排序好。

2.程序

package com.jun.algorithm.foundation.thought;

import org.junit.Test;

import java.util.Arrays;

/**
 * 希尔排序
 * 把记录按照下标进行增量分组，对每一组使用插入排序算法排序
 * 随着增量的减少，每组包含的有序的原来越多，当增量减少为1时，整个文件分为一组，算法终止
 * 

 * 稳定性：不稳定
 *
 * @author caojun
 */
public class ShellSort {
    private int[] shell(int[] arr) {
        // 分段
        for (int add = arr.length / 2; add >= 1; add /= 2) {
            for (int i = add; i < arr.length; i++) {
                int data = arr[i];
                int j;
                // 间隔之后，进行前后对比
                for (j = i - add; j >= 0; j -= add) {
                    if (arr[j] > data) {
                        arr[j + add] = arr[j];
                    } else {
                        break;
                    }
                }
                // 赋值
                arr[j + add] = data;
            }

        }
        return arr;
    }

    @Test
    public void test() {
        int[] arr = {1, 3, 2, 7, 5};
        int[] newArr = shell(arr);
        System.out.println(Arrays.toString(newArr));
    }
}

四：归并排序

1.思路

　　将待排序的数组分为两个字数组，分别对它们按同样的方式进行排序，最后将两个有序子数组 归并成一个有序数组。

2.程序

package com.jun.algorithm.foundation.thought;

import org.junit.Test;

import java.util.Arrays;

/**
 * 归并排序
 * 递归与分治的思想结合
 * 

 * 时间复杂度是nlogn
 * 

 * 稳定性：稳定的，因为是对插入排序的优化
 *
 * @author caojun
 */
public class MergeSort {
    /**
     * 排序
     *
     * @param arr   数组
     * @param left  数组的左端
     * @param right 数组的右端
     * @return 排序后的数组
     */
    public int[] merge(int[] arr, int left, int right) {
        // 相等了就表示只有一个数了，不用再分了，终止条件
        if (left < right) {
            int mid = (left + right) / 2;
            merge(arr, left, mid);
            merge(arr, mid + 1, right);
            // 并
            mergeData(arr, left, mid, right);
        }
        return arr;
    }

    private void mergeData(int[] arr, int left, int mid, int right) {
        // 保存合并后的数据
        int[] temp = new int[arr.length];
        // 左边的第一个数据的位置
        int point1 = left;
        // 右边的第一个数据的位置
        int point2 = mid + 1;
        // 表示已经到达的位置
        int loc = left;

        // 合并的终止条件
        while (point1 <= mid && point2 <= right) {
            if (arr[point1] < arr[point2]) {
                temp[loc] = arr[point1];
                point1++;
                loc++;
            } else {
                temp[loc] = arr[point2];
                point2++;
                loc++;
            }
        }
        // 还有一个数组没有进行将数据合并在，这里是左边没有赋值完
        while (point1 <= mid) {
            temp[loc++] = arr[point1++];
        }
        // 还有一个数组没有进行将数据合并在，这里是右边没有赋值完
        while (point2 <= right) {
            temp[loc++] = arr[point2++];
        }

        // 将临时数组中的数据添加到arr中
        if (right + 1 - left >= 0) {
            System.arraycopy(temp, left, arr, left, right + 1 - left);
        }
    }

    @Test
    public void test() {
        int[] arr = {1, 5, 6, 3, 8};
        int[] newArr = merge(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(newArr));
    }
}

五：选择排序

1.思路

　　班级找最高的人。

　　每次从未排序的区间中找到最小的元素，将其放到已排序区间的末尾，但是不是插入那种方式进行移动数组，选择进行交换。

2.程序

package com.jun.algorithm.foundation.thought;

import org.junit.Test;

import java.util.Arrays;

/**
 * 选择排序
 * 使用场景:在班级中选择出身高最高的人
 *
 * 时间复杂度：
 *
 * @author caojun
 */
public class SelectSort {

    public int[] select(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            // 循环的那个就是找到一个最小的
            int min = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[min]) {
                    min = j;
                }
            }
            // 交换
            int temp = arr[min];
            arr[min] = arr[i];
            arr[i] = temp;
        }
        return arr;
    }

    @Test
    public void test() {
        int[] arr = {1, 3, 2, 7, 5};
        int[] newArr = select(arr);
        System.out.println(Arrays.toString(newArr));
    }

}

六：冒泡排序

1.思路

　　冒泡的方式

2.程序

package com.jun.algorithm.foundation.thought;

import org.junit.Test;

import java.util.Arrays;

/**
 * 冒泡排序
 * 每次都和相邻的元素进行比较
 *
 * @author caojun
 */
public class BubbleSort {
    public int[] bubble(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
        return arr;
    }

    @Test
    public void test() {
        int[] arr = {1, 3, 2, 7, 5};
        int[] newArr = bubble(arr);
        System.out.println(Arrays.toString(newArr));
    }
}

七：

1.思路

2.