八大排序算法总结

佚名 5年前 (2019-03-28) 算法 2111人围观抢沙发百度已收录

1、选择排序

主要思想：在数组中找到那个最小的数让它与第一个数交换，然后在剩下的数组中找到最小的数让它与第二个数交换，依次将整个数组排序。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

复杂度：N个数排序，需要N²/2次比较和N次交换。

Java代码：

package sort;
import java.util.Arrays; ;

public class SelectSort {
    public static void show(int[] num) {
        System.out.println(Arrays.toString(num));
    }
    public static void SelectSorting(int [] numbers) {
        for(int i = 0 ; i < numbers.length ; i ++) {
            int minIndex = i ;
            for(int j = 0 ; j < numbers.length ; j ++) {
                if(numbers[j] < numbers[i]) {
                minIndex = j  ;
                }
            }
            swap(numbers , i , minIndex) ;
        }
    }
    public static void swap(int[] num , int n, int m) {
        int temp = num[n] ;
        num[n] = num[m] ;
        num[m] = temp ;
    }    
    public static void main(String[] args) {
        int [] nums = new int []  {2,4,8,4,5,7,0} ;
        show(nums) ;
        SelectSorting(nums) ;
        show(nums) ;
    }
}

2、插入排序

主要思想：（升序）从第二数开始遍历整个数组，当当前索引的值比它左边的值小的时候，就将此值往前挪到适当的位置（它左边有部分值就得往后挪），就这样遍历到数组末尾时，整个数组就已经排好序了。在整个过程中，和选择排序一样，当前索引的左边是有序的，与先择排序不一样的是左边的最终位置并不确定，还可能为了更小的值而挪动位置。

复杂度：N个数排序，平均情况下需要N²/4比较，N²/4次交换；最好情况下需要N-1次比较，0次交换；最坏情况下需要N²/2比较，N²/2次交换。

Java代码

package sort;
import java.util.Arrays; ;

public class InsertSort {
    public static void show(int[] num) {
        System.out.println(Arrays.toString(num));
    }
    public static void Sort(int [] numbers) {
        for(int i = 1 ; i < numbers.length ; i ++) {
            for(int j = i ; j > 0 &&  numbers[j] < numbers[j-1]  ; j --) {
                swap(numbers , j , j-1) ;        
            }
        }
    }
    public static void swap(int[] num , int n, int m) {
        int temp = num[n] ;
        num[n] = num[m] ;
        num[m] = temp ;
    }    
    public static void main(String[] args) {
        int [] nums = new int []  {2,4,8,4,5,7,0} ;
        show(nums) ;
        Sort(nums) ;
        show(nums) ;
    }
}

3、冒泡排序

主要思想：对两个相邻的数依次进行比较和调整，让最大数往下沉，最小的数往上冒，也就是发现两个相邻的数的排序与排序要求相反时，交换两个数。

复杂度：

package sort;
import java.util.Arrays; ;

public class BubbleSort {
    public static void show(int[] num) {
        System.out.println(Arrays.toString(num));
    }
    public static void Sort(int [] numbers) {
        for(int i = 0 ; i < numbers.length - 1 ; i ++) {
            for(int j = 0 ; j > numbers.length - 1 - i ; j ++) {
                swap(numbers , j , j+1) ;        
            }
        }
    }
    public static void swap(int[] num , int n, int m) {
        int temp = num[n] ;
        num[n] = num[m] ;
        num[m] = temp ;
    }    
    public static void main(String[] args) {
        int [] nums = new int []  {2,4,8,4,5,7,0} ;
        show(nums) ;
        Sort(nums) ;
        show(nums) ;
    }
}

4、快速排序

参考：https://www.cnblogs.com/coderising/p/5708801.html

主要思想：基于分治的思想，是冒泡排序的改进型。首先在数组中选择一个基准点（该基准点的选取可能影响快速排序的效率，后面讲解选取的方法），然后分别从数组的两端扫描数组，设两个指示标志（lo指向起始位置，hi指向末尾)，首先从后半部分开始，如果发现有元素比该基准点的值小，就交换lo和hi位置的值，然后从前半部分开始扫秒，发现有元素大于基准点的值，就交换lo和hi位置的值，如此往复循环，直到lo>=hi,然后把基准点的值放到hi这个位置。一次排序就完成了。以后采用递归的方式分别对前半部分和后半部分排序，当前半部分和后半部分均有序时该数组就自然有序了。

快速排序的时间复杂度为O(NlogN).

public static int partition(int []array,int lo,int hi){
        //固定的切分方式
        int key=array[lo];
        while(lo<hi){
            while(array[hi]>=key&&hi>lo){//从后半部分向前扫描
                hi--;
            }
            array[lo]=array[hi];
            while(array[lo]<=key&&hi>lo){从前半部分向后扫描
                lo++;
            }
            array[hi]=array[lo];
        }
        array[hi]=key;
        return hi;
    }
    
    public static void sort(int[] array,int lo ,int hi){
        if(lo>=hi){
            return ;
        }
        int index=partition(array,lo,hi);
        sort(array,lo,index-1);
        sort(array,index+1,hi); 
    }

快速排序的优化

对于基准位置的选取一般有三种方法：固定切分，随机切分和三取样切分。固定切分的效率并不是太好，随机切分是常用的一种切分，效率比较高，最坏情况下时间复杂度有可能为O(N²).对于三数取中选择基准点是最理想的一种。

三数取中切分：

public static int partition(int []array,int lo,int hi){
        //三数取中
        int mid=lo+(hi-lo)/2;
        if(array[mid]>array[hi]){
            swap(array[mid],array[hi]);
        }
        if(array[lo]>array[hi]){
            swap(array[lo],array[hi]);
        }
        if(array[mid]>array[lo]){
            swap(array[mid],array[lo]);
        }
        int key=array[lo];
        
        while(lo<hi){
            while(array[hi]>=key&&hi>lo){
                hi--;
            }
            array[lo]=array[hi];
            while(array[lo]<=key&&hi>lo){
                lo++;
            }
            array[hi]=array[lo];
        }
        array[hi]=key;
        return hi;
    }
    
    public static void swap(int a,int b){
        int temp=a;
        a=b;
        b=temp;
    }
    public static void sort(int[] array,int lo ,int hi){
        if(lo>=hi){
            return ;
        }
        int index=partition(array,lo,hi);
        sort(array,lo,index-1);
        sort(array,index+1,hi);
    }