十大经典排序算法

排序算法是算法学习中比较经典的内容，面试也会经常考到，学习十大经典排序算法的目的在于理解并掌握其中运用的算法思想，还有装逼(不是

本片文章参考了博客十大经典排序算法(动图演示)，该博客上还有排序的相关图解和JS代码实现，非常清晰

相关概念

• 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
• 不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
• 时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
• 空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。

下面代码通用的排序工具类，用于提供打印数组的方法和测试数据，并且下面排序算法都是按从小到大排序(从大到小反推即可)

public class SortUtil {
    public static void printArray(int[] array){
        for(int i:array)
            System.out.print(" "+i+" ");
    }
    public static int[] array1={100,889,4678,1354,20,1,3,225,502,765,12,10058,52};
    public static int[] array2={1,2,3,4,5,6,77,2,3,80,464,124};
    public static int[] array3={3,5,38,156,1,564,8,4,65,51,321,3,54,31,23,150};
}

1.冒泡排序

冒泡排序的特点就是在交换相邻数组元素时，元素会一步一步地向末尾端移动，像冒泡一样

• 时间复杂度(平均)：O(n^2)
• 时间复杂度(最好)：O(n)
• 时间复杂度(最差)：O(n^2)
• 空间复杂度：O(1)
• 稳定性：稳定

public class BubbleSort {
    public static void main(String[] args) {
        int[] array=SortUtil.array1;
        for (int i=0;i<array.length-1;i++)
        {
            //这里设置j的上限为array.length-1可以减少无效循环语句的执行
            for (int j=0;j<array.length-1-i;j++)
            {
                if(array[j]>array[j+1])
                {
                	//冒泡的核心部分在于相邻元素的交换
                    int temp=array[j];
                    array[j]=array[j+1];
                    array[j+1]=temp;
                }
            }
        }
        SortUtil.printArray(array);
        System.out.println();
    }
}

2.选择排序

选择排序的特点在于把数组分为有序和无序的，初始数组全为无序部分，然后从中选择最小(大)值放到有序部分(有序部分从数组的0下标开始)，依次执行直到无序部分遍历结束

• 时间复杂度(平均)：O(n^2)
• 时间复杂度(最好)：O(n^2)
• 时间复杂度(最差)：O(n^2)
• 空间复杂度：O(1)
• 稳定性：不稳定

public class SelectSort {
    public static void main(String[] args) {
        int[] array = SortUtil.array1;
        //用minIndex作为最小部分的下标
        int minIndex=0;
        //这里上限为array.length-1是为了防止j越界
        for (int i=0;i<array.length-1;i++)
        {
            //这一步很关键，每次在无序部分进行新一轮循环时都要重新初始化最小下标
            //因为不知道哪个是最小值则用第一个下标做minIndex
            minIndex=i;
            for (int j=i+1;j<array.length;j++)
            {
                //每当遇到比最小下标元素更小的元素时就更新最小下标
                if(array[j]<array[minIndex])
                    minIndex=j;
            } 
            int temp=array[i];
            array[i]=array[minIndex];
            array[minIndex]=temp; 
        }
        SortUtil.printArray(array);
        System.out.println();
    }

}

3.插入排序

插入排序的特点是也像选择排序那样分成有序和无序部分，不过它的第二轮循环没有遍历无序部分，而是遍历有序部分与无序部分的第一个元素进行比较，如果满足条件则将这当前元素插入到有序部分中，这里的插入是从后往前插

• 时间复杂度(平均)：O(n^2)
• 时间复杂度(最好)：O(n)
• 时间复杂度(最差)：O(n^2)
• 空间复杂度：O(1)
• 稳定性：稳定

public class InsertSort {
    public static void main(String[] args) {
        int[] array = SortUtil.array1;
        //设置前面有序序列的替换下标、当前值
        int preIndex,current;
        //循环要从1开始，因为要预留下标0给preIndex
        for (int i=1;i<array.length;i++)
        {
            preIndex=i-1;
            //这里要用current记录下标i的值，而不能直接记录下标i，因为后面下标i的元素会被替换掉
            current=array[i];
            //这里判断前面的下标是否大于当前值且在数组元素内，如果大于就让前面元素向后移位空出一格以备当前元素插入
            while(preIndex>=0 && array[preIndex]>current)
            {
                //前面下标后移一格，下标同时向前移动
                array[preIndex+1]=array[preIndex];
                preIndex--;
            }
            //循环结束则说明当前元素大于前面元素，此时插入空格位(看起来是空格为但实际上是前面的后移元素)
            //并且这里的preIndex+1是因为在前面循环后preIndex会比空格位对应的下标还要小1，因此要+1得到空格位
            array[preIndex+1]=current;
        }
        SortUtil.printArray(array);
        System.out.println();
    }

}

4.希尔排序

希尔排序是第一个突破O(n^2)复杂度的排序算法。它是插入排序的优化版本，又叫缩小增量排序，插入排序每次比较的间隔都是1，而希尔排序的比较间隔是从大到小，如果后面的元素满足条件则也会从后往前插入

• 时间复杂度(平均)：O(n^1.3)
• 时间复杂度(最好)：O(n)
• 时间复杂度(最差)：O(n^2)
• 空间复杂度：O(1)
• 稳定性：不稳定

public class ShellSort {
    public static void main(String[] args) {
        int[] array = SortUtil.array1;
        //preIndex作为前面元素下标、gap作为比较间隔、current作为当前元素
        int preIndex,gap,current; 
        //首先外部有个大循环是用gap作条件，不断缩小比较的间隔，如12->6->3->1
        for(gap=array.length/2;gap>0;gap=gap/2)
        {
            //这里的核心部分和插入排序非常相似
            //初始条件i=gap和插入排序的i=1类似
            //初始化preIndex=i-gap和插入排序的i=i-1类似
            //到后面的while循环条件和插入排序直接一致，可以说当gap缩小到1时这段代码就等同于插入排序了
            for (int i=gap;i<array.length;i++)
            {
                preIndex=i-gap;
                current=array[i];
                while(preIndex>=0 && array[preIndex]>current)
                {
                    array[preIndex+gap]=array[preIndex];
                    preIndex-=gap;
                }
                array[preIndex+gap]=current;
            }
        }
        SortUtil.printArray(array);
        System.out.println();
    }
}

5.归并排序

归并排序的特点是通过分治法，先把无序队列分成子序列，分成子序列的关键在于变换首尾下标，起初是子序列是整个数组的长度然后慢慢递减到只有1个长度，然后使子序列有序，然后再把有序子序列合并起来，最终得到一个完整的有序序列

• 时间复杂度(平均)：O(nlogn)
• 时间复杂度(最好)：O(nlogn)
• 时间复杂度(最差)：O(nlogn)
• 空间复杂度：O(n)
• 稳定性：稳定

public class MergeSort {
    public static void main(String[] args) {
        int[] array = SortUtil.array1;
        //用一个辅助数组来帮助实现归并
        int[] result=new int[array.length];
        //初始前后下标设置为数组首尾下标
        merge(array,result,0,array.length-1);
        SortUtil.printArray(array);
        System.out.println();
    }
	//递归方法
    public static void merge(int[] array,int[] result,int start,int end)
    {
        //当只有子序列只有一个元素时结束递归，子序列长度由start和end决定
        if(start>=end)
            return;
        //首先取一半作为子序列
        int mid=start+(end-start)/2;
        //前半段子序列下标为start1~end1，后半段下标为start2~end2
        int start1=start,end1=mid;
        int start2=mid+1,end2=end;
        //然后一直递归直到只有1个元素才会继续后面的代码
        merge(array,result,start1,end1);
        merge(array,result,start2,end2);
        //下面是归并部分，用把两个有序队列合并成一个有序队列来看就很容易理解
        int k=start;
        //首先两个有序队列都未遍历完，因此比较后小的插入result数组，同时变换下标
        while(start1<=end1 && start2<=end2)
        {
            if(array[start1]<array[start2])
                result[k++]=array[start1++];
            else
                result[k++]=array[start2++];
        }
        //当一个队列遍历完后另一个队列就可以直接遍历剩余部分插入到result数组中
        while(start1<=end1)
            result[k++]=array[start1++];
        while(start2<=end2)
            result[k++]=array[start2++];
        
        //最后要修改原数组array，因为result只是一个辅助数组
        for (k=start;k<=end;k++)
            array[k]=result[k];
    }
}

6.快速排序

快速排序的特点在于选择一个队列左侧的一个值作为基准值，然后通过比较基准值把比基准值小(大)的元素移动到队列前端(队列前端的数都比基准值小，后方都比基准值大)，最后再把基准值移动到前端尾部进行下一轮递归。

• 时间复杂度(平均)：O(nlogn)
• 时间复杂度(最好)：O(nlogn)
• 时间复杂度(最差)：O(n^2)
• 空间复杂度：O(nlogn)
• 稳定性：不稳定

public class QuickSort {
    public static void main(String[] args) {
        int[] array = SortUtil.array1;
        quickSort(array,0,array.length-1);
        SortUtil.printArray(array);
        System.out.println();
    }
    //通过递归实现快速排序
    public static void quickSort(int[] array,int left,int right){
        //当队列只有一个元素时结束递归
        if(left<right)
        {
            int partition=getPartition(array,left,right);
            //左边都小于基准值，右边都大于基准值
            quickSort(array,left,partition-1);
            quickSort(array,partition+1,right);
        }
    }
	//分区操作，获得最后
    public static int getPartition(int[] array,int left,int right){
        int pivot=left;
        int index=pivot+1;
        //从基准值后一位开始遍历到右边
        for (int i=index;i<=right;i++)
        {
            //如果当前元素比基准值小，就与初始遍历位交换，然后下标向后移动一位
            if(array[i]<array[pivot])
            {
                swap(array,i,index);
                index++;
            }
        }
        //这里index-1是因为前最后一次循环后index还会后移一位到比基准值大的地方
        //而基准值最后要交换的应当是比其小的最大数，因此需要index-1
        swap(array,pivot,index-1);
        return index-1;
    }
    //交换两个下标的数组元素
    public static void swap(int[] array,int i,int j)
    {
        int temp=array[i];
        array[i]=array[j];
        array[j]=temp;
    }
}

以后再写，困了…