排序算法（1）

一、基础概念

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

第一种排序稳定，第二种排序不稳定

比如：考试取得同一分数，但是用时不同，所以用时短的人就要排在用时长的人的前面

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

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

二、插入排序

1、直接插入排序

思想：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到 一个新的有序序列 。实际中我们玩扑克牌时，就用了插入排序的思想。

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

直接插入排序的特性总结：

1. 元素集合越接近有序，直接插入排序算法的时间效率越高

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

3. 空间复杂度：O(1)

4. 稳定性：稳定（前提，如果加=就是不稳定，注意稳定可以变为不稳定，但不稳定不能变为稳定）

2、希尔排序（缩小增量排序）

思想：先选定一个整数，把待排序文件中所有数据分成多个组， 所有距离为gap的分在同一组内，并对每一组内的记录进行排序。然后再次分组，在上一组的基础上取gap，重复上述分组和排序的工作。当到达 gap=1时，所有记录在统一组内排好序。

 public static void shell(int[] array,int gap){
        for(int i = gap;i<array.length;i++){
            int tmp = array[i];
            int j=i-gap;
            for(;j>=0;j-=gap){
                if(array[j]>tmp){
                    array[j+gap] = array[j];
                }else{
                    break;
                }
            }
            array[j+gap] = tmp;
        }
    }
    public static void shellSort(int[] array){
        int gap = array.length;
        while(gap>1){
            gap /= 2;
            shell(array,gap);//每组进行插入排序
        }
    }

总结：

1. 希尔排序是对直接插入排序的优化。

2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。

3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些书中给出的希尔排序的时间复杂度都不固定。因为我们的gap是按照Knuth提出的方式取值的，而且Knuth进行了大量的试验统计，我们暂时就按照： 到 来算。

4. 稳定性：不稳定

三、选择排序

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

1、直接选择排序

在元素集合array[i]--array[n-1]中选择关键码最大(小)的数据元素 ，若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换 ，在剩余的array[i]--array[n-2]（array[i+1]--array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素

public static void swap(int[] array,int i,int j){
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
    public void selectSort(int[] array){
        for(int i = 0;i<array.length;i++){
            int minIndex = i;
            for(int j = i+1;j<array.length;j++){
                if(array[j]<array[minIndex]){
                    minIndex = j;
                }
            }
            swap(array,minIndex,i);
        }
    }//时间复杂度O(n^2)空间复杂度O(1) 稳定性：不稳定
    public void selectSort2(int[] array){
        int left = 0;
        int right = array.length-1;
        while(left<right){
            int minIndex = left;
            int maxIndex = left;
            for(int i = left+1;i<=right;i++){
                if(array[i]<array[minIndex]);
                {
                    minIndex = i;
                }
                if(array[i]>array[maxIndex]){
                    maxIndex = i;
                }
            }
            swap(array,minIndex,left);
            //如果最大值是left，上面操作后，就把最大值下标换到最小值下标的位置，所以需要更新最大值的位置
            if(maxIndex == left){
                maxIndex = minIndex;
            }
            swap(array,maxIndex,right);
            left++;
            right--;
        }
    }

总结

1. 直接选择排序非常好理解，但是效率不是很好。实际中很少使用

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

3. 空间复杂度：O(1)

4. 稳定性：不稳定

2、堆排序

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

如果排升序：先通过向下调整创建大根堆，创建完成后先通过将顶部与末尾未被交换的值交换，之后再向下调整，重复这一过程直到都排完。

 private static void createBigHeap(int[] array){
        for(int parent = (array.length-1-1)/2;parent>=0;parent--){
            siftDown(parent,array,array.length);
        }
    }
    private static void siftDown(int parent,int[] array,int end){
        int child = 2*parent+1;
        while(child<end){
            if(child+1<end && array[child]<array[child+1]){
                child++;//左右孩子的最大值
            }
            //child下标就是左右孩子最大值
            if(array[child]>array[parent]){
                swap(array,child,parent);
                parent = child;
                child = 2*parent+1;
            }else{
                break;
            }
        }
    }
    //时间复杂度knlogN
    // 空间复杂度O(1)
    public static void heapSort(int[] array){
        createBigHeap(array);
        int end = array.length-1;
        while(end>=0){
            swap(array,0,end);
            siftDown(0,array,end);
            end--;
        }
    }

总结

1. 堆排序使用堆来选数，效率就高了很多。

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

3. 空间复杂度：O(1)

4. 稳定性：不稳定