算法--排序

合

1

比较

3

交换

5

已排序

5大于3交换

插入排序是将未排序的数据插入到已经排序的数据中。其实仔细发现其实插入排序是冒泡排序的改进版，冒泡排序是从头开始向后面比较，基本上每次都要从头比较到尾部，而插入排序从后向前比较，我们从第二个元素开始向前比较，当遇到一个大于他的数时，就将该数向后移动一位，然后继续向前比较知道遇到不大于他的数停止，然后从第三个元素开始重复上面的操作知道最后一个元素。这样明显的降低了比较的次数，是冒泡排序的进化版。效率任然为O(N^2) --->最坏的情况是完全倒序，此时比较次数就和冒泡排序一样。（插入排序的好处在于他无需从后向前比较到最前面的元素，只需要比较到第一个小于他的数就可以停止了，因为前面是有序的所以前面的数都肯定小于他）

low

4

堆排序步骤：1 ， 创建一个堆（完全二叉树）2，交换首尾的数据值 （此时最大数在最下面）3，下沉（将根节点向下移动直到没有比他大停止（比较元素没到交换位置））4，重复第二 三步上面描述过于抽象下面展示具体过程

插入排序

6

下沉

冒泡排序

从第一个元素开始相邻元素间进行比较知道最后一个元素（如:第一和第二比较第一个如果大于第二个就交换位置，然后第二个与第三个比较。。。），每一躺比较的结果是最大的元素到最后去了，第二趟比较时我们只需要比较到倒数第二个元素就可以了，此时得到的时第二大的元素。效率：O(N^2)

希尔排序是插入排序的一种优化，插入排序在小的数字在靠后时效率任然低下，以为我们比较小的数字时，可能任然要不停的比较直到最前面，这样的比较次数就和冒泡效率差不多了。希尔排序正式抓住了这点他先将比较的范围扩大比如每隔3个数比较一次，然后每隔2个数比较一次，最后每隔一个数比较一次（此时就是插入排序），这样可以先将大范围的大小确定，将大的数据尽量放在后面小的放在前面，等正真插入排序的时候就可以减少因为小数据在后面而需要比较到第一个才停止的情况。当然希尔排序是不稳定的因为小的数据不一定在后面大的数据也不一定在前面，这样可能造成多余的比较。效率为：O(N^2)

high

分

希尔排序

归并排序

1 .构建堆

min

快速排序

快速排序的思想在于取一组数据的一个数据作为基准数据，准备两个指针向前遍历分别与基准数进行比较，然后进行交换，这样可以在两个指针重合之时得到大于基准数的数据在重合位置的右方小于基准数的在左方，然后分别将左右两边作为一组数据做相同的操作，直到数据只有一个为止。效率:快速排序在最好的情况是每次刚好分成一半 O( N * log2(N))        最糟糕的情况是每次取得第一个元素都是最小的数据 O( N ^2) 

3不大于1无需交换

给定一堆乱序数

基准数

5比6大进行上移

由此可见我们构建堆的过程是构建一个二叉树的过程，当我们每插入一个新的节点都需要和他的父结点进行比较，大于父节点就进行上移，父节点继续往上比较，直到不大于父节点或已经到了根节点停止（递归过程）。最终我们可以得到一个父节节点都比子节点大的完全二叉树。

归并排序是一个分合的过程，分:通过递归的手段将一个数组不停的一分为二，递归停止的条件是不能在分时即数组元素只有一个时，然后合并，合并的时候由于两个组数据是有序的所以我们可以通过遍历两组数据，来不断的从中去出小的数据放在一个新的数据里面直到没有数据可以取了。效率分析：分: O(log2(N)) + 合:O(log2(N) * N)  = O(N * log2(N))注意：合中log2(N)是深度，每一层都要对整个数组进行一次遍历。

效率 : 构建完全二叉树的过程为N * log2(N) ， 交换下沉的过程为 N * log2(N)时间复杂度为: O(N * log2(N))

排序

重复上面操作 。。。

3大于1交换

选择排序

已排好序

选择排序思想很简单，从一组数据中从第一个元素开始遍历到最后，找到最小的元素放在与第一个位置数据交换，然后从第二个元素开始遍历到最后的元素找到最小的元素与第二个元素交换，直到最后一个元素为止。效率： O(N^2)

4，3 ，5 ， 1 ，6

1下方为已经交换过的元素无需比较

堆排序

层次遍历二叉树得到升序结果

public void sort(int[] arr){        int len = arr.length;        for(int i = 0 ; i < len ; i++)        {            for(int j = 0 ; j < len - 1 - i; j++)            {                if(arr[j] > arr[j + 1])                {                   int tmp = arr[j];                   arr[j]   = arr[j+1];                   arr[j+1] = tmp;                }            }        }}

未排序

此时由于5比4大，5需要上移到根节点

6比3大上移

4大于1交换