排序算法合集

排序算法汇总

各类排序算法时间空间复杂度如下表所示：

1：直接选择排序：

排序思想：

选取当前最小（最大）的数据放置在当前状态下的最前面的位置，一直轮循，直到所有序列都有序为止：

代码实现：

    public void sort(int a[]){
        int length = a.length;
        for(int i =0;i<length;i++){
            int min = i;
            for(int j =i+1;j<length;j++){
                if(a[min]>a[j]){
                    min = j;
                }
            }
            if(min !=i){
                int temp = a[i];
                a[i]=a[min];
                a[min]=temp;
            }
        }
    }
}

示例：

[9,5,2,4,3]
i = 0;
根据内部循环，选取当前状态(i = 0)下最小的的值为2，此时下标j为3，将2放置在当前状态下的最前面a[i]处
该循环后序列为：
[2,5,9,4,3]
再进一步循环，直到i = 5,循环终止，序列有序 

时间复杂度分析：

改排序需要经过两重循环，假定有n个元素，则其需要经历n*n次循环才能结束，所以其时间复杂度为O(n^2)

空间复杂度分析：

该排序没有占用额外的存储空间（临时变量常数级别），所以该排序的空间负载度为O(1)

2：插入排序

排序思想：

将整个待排序的序列分成两个部分，前半部分是有序的序列，后半部分为无需部分，然后将后半部分的元素依次添加到前半部分的有序序列中，前半部分为有序序列，因此只需要将后半部分取出来的数据插入到合适的位置即可，直到后半部分为空；

代码实现：

    public void sort(int target[]){
        int length = target.length;
        for(int i=1;i<length;i++){
            for(int j = i;j>0;j--){
                if(target[j]>target[j-1]) {
                    int temp = target[j];
                    target[j]=target[j-1];
                    target[j-1]=temp;
                }else{
                    break;
                }
            }
        }
    }

示例：

[1,4,2,5,3]
将数据分成两个序列[1] 和 [4,2,5,3]
将4 加入到前半部分中,此时序列为[1,4] 和 [2,5,3]
将2 加入到前半部分中,此时序列为[1,2，4] 和 [5,3]
直到最后序列有序

时间复杂度分析：

该算法基础步骤执行的次数为：(1+n)*n/2,其数量级在n^{2,因此其时间复杂度为O(n}2)

最好情况为整个序列有序，每次只需移动后半部分的一个元素到前半部分，移动次数为n，故为O(n)

空间复杂度分析：

该排序没有占用额外的存储空间（临时变量常数级别），所以该排序的空间负载度为O(1)

3:希尔排序

排序思想：

希尔排序(Shell)是插入排序的升级版，假设一个序列是倒叙的，现在要求对这个数列正序排列，在数组基数较大的情况下，将最后的元素移动到最前面需要经历n-1次的比较，比较次数较多，元素移动较多，排序效率自然低下，希尔排序，是在这样的情况下产生的，其实想思想是先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上比前两种方法有较大提高，这样元素移动跨度较大，效率也自然的得到提升；

希尔排序的步长可以自定义，下面，我选用步长为3

代码实现：

    public void sort(int target[]){
        int length = target.length;
        int h = 1;
        while(h<length/3) h = 3*h+1;（步长）
        while(h >=1){
            for(int i = h;i<length;i++){
                for(int j = i;j>=h;j-=h){
                    if(target[j]<target[j-h]){
                        int temp = target[j];
                        target[j]=target[j-h];
                        target[j-h] = temp;
                    }
                }
            }
            h=h/3;
        }
    }

时间复杂度分析：

希尔排序的时间复杂度与选择的步长度有关

空间复杂度：

该排序没有占用额外的存储空间（临时变量常数级别），所以该排序的空间负载度为O(1)