基础算法——简单排序算法（上）

目录

1.排序的概念

2.常见排序算法的实现

排序：就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。

稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

内部排序：数据元素全部放在内存中的排序。

外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

插入排序的思想；类似于我们打扑克牌时候进行排序的思想。即把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到 一个新的有序序列 。

我们先来看到最简单的直接插入排序。

他采用了双指针 i j 对数组进行遍历，当插入第i个元素时，前面的元素已经是有序的，之后将第i个元素存入tmp变量，向前遍历比较，如果array[j] > tmp（以升序排序举例），array[j+1] = array[j]，反之将tmp插入该位置array[j+1] = tmp。

我们看到代码可能会更好理解：

public static void insertSort(int[] array){
        for(int i=1;i=0;j--){
                if(array[j]>tmp){
                    array[j+1]=array[j];
                }else{
                    break;
                }
            }
            array[j+1]=tmp;
        }
    }

算法时间复杂度：O(N^2)  但是该算法时间复杂度和数据有较大关系，在数据接近有序时该算法时间复杂度可趋近于O（N）

空间复杂度：O（1）

稳定性：稳定

 接下来我们看到希尔排序（缩小增量排序）

希尔排序可以看作是直接插入排序的优化版本。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个组，所 有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后取重复上述分组和排序的工作。当到达=1 时，所有记录在统一组内排好序。由于采用了分组排序的思想，所以总的排序次数相对于直接插入排序有显著降低，但是由于目前尚未有最佳的分组方案，所以时间复杂度并不确定。

 关于时间复杂度的说明我们可以参考下文：

 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。

 希尔排序由于只是插入排序的优化版本，所以我们可以直接在直接插入排序的基础上修改即可得到希尔排序的代码。

public static void shell(int[] array,int gap){
        for(int i=gap;i=0;j-=gap){
                if(array[j]>tmp){
                    array[j+gap]=array[j];
                }
                else{
                    break;
                }
            }
            array[j+gap]=tmp;
        }
    }

 时间复杂度：见上图分析

 空间复杂度：O（1）

 稳定性：不稳定

直接选择排序：

每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。

思路很简单，我们直接看到代码：

public static void selectSort(int[] array){
        for(int i=0;i

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

 空间复杂度：O(1)

 稳定性：不稳定 

堆排序：

堆排序是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆 来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。

关于怎么理解最后一句话，我们首先要知道堆排序的基本思想。当然首先我们要知道的是我们的大根堆或者小根堆在建立好后虽然满足根一定大于/小于他的孩子节点，但是他不一定是有序的。

 堆排序的思想：

 1.创建大根堆或者小根堆

 2.将堆顶元素与最后一个元素交换

 3.数据-1

 4.进行一次至上而下的调整

分析堆排序的思想我们可以知道，假如我们建立的是大根堆，那我们相当于不断把最大的数据放在当前的堆尾，之后堆大小-1。即可以这么理解，每次把数据放在堆尾但这实际相当于数组的首地址 。这样就不难理解排升序要建大堆，排降序建小堆这句话了。

我们可以根据下面这个例子来模拟一下：

交换后可以看到我们将20放到了最后

继续交换

 因为此时数据-1所以20已经不属于堆内元素了，将堆顶元素17与堆尾元素交换就得到了这个结果，所以从图我们也可以理解为什么要升序建大根堆，降序建小根堆了。

理解了算法原理后我们应该可以轻松写出这个代码：

private static void shiftDown(int[] array,int root,int len){
        int parent=root;
        int child = (2*parent) + 1;
        while(child array[parent]) {
                swap(array, child, parent);
                parent = child;
                child = 2 * parent + 1;
            }else{
                break;
            }
        }
    }

    private static void createHeap(int[] array){
        for(int p=(array.length-1-1)/2;p>=0;p--){
            shiftDown(array,p,array.length);
        }
    }

    public static void heapSort(int[] array) {
        createHeap(array);
        int end=array.length-1;
        while(end>=0){
            swap(array,0,end);
            shiftDown(array,0,end);
            end--;
        }
    }

有关堆的知识不理解的也可以看一看我的上一篇博客：基础数据结构——堆_invictusQAQ的博客-CSDN博客 

时间复杂度：O(N*logN)

空间复杂度：O(1)

稳定性：不稳定

剩余的几种排序方式我将会在下一篇更新，敬请期待。