数据结构之常见排序算法

一、排序中的概念

二、常见排序算法--升序

1、插入排序

（1）直接插入排序

（2）希尔排序

2、选择排序

（1）单指针选择排序

（2）双指针选择排序

（3）堆排序

3、交换排序

（1）冒泡排序

（2）双指针快速排序

（3）挖洞快速排序

（4）前后指针快速排序

（5）优化版快速排序

（6）非递归快速排序

4、归并排序

（1）归并排序

（2）归并排序非递归

5、计数排序

6、桶排序

7、基数排序

一、排序中的概念

1、稳定性：在待排序的记录中，存在多个相同的关键字记录，若在排序前和排序后这些相同关键字的相对次序保持不变，则这种排序算法是稳定的，否则称为不稳定的。

二、常见排序算法--升序

1、插入排序

（1）直接插入排序

①思想：将要插入的数据和前面比较，要是前面的小，结束比较，要是前面的大，元素后移，再次比较，直到遇到较小的，元素插入。

②代码实现：

public static void insertSort(int[] a){
        int size=a.length;
        for(int i=1;i<size;i++){
            int j=i-1;
            int temp=a[i];  //后面会被覆盖
            for(;j>=0;j--){
                if(a[j]>temp){
                    a[j+1]=a[j];
                }else {
                    break;
                }
            }
            a[j+1]=temp;
        }
    }

③特性：

元素越接近有序，时间效率越高；

时间复杂度：O(n^2)；空间复杂度：O(1)；稳定性：稳定。

（2）希尔排序

①思想：对元素进行分组，如有10个元素，先分成5组(元素间隔为5)，对着5组进行插入排序；再分成2组(元素间隔为2)，对这2组进行插入排序；最后分成1组(元素间隔为1)，对着1组进行插入排序，此时插入排序时元素已经接近有序了。

②代码实现：

public static void shellSort(int[] a){
        int size=a.length;
        while(size/2>=1){
            size/=2;
            shell(a,size);
        }
    }

    public static void shell(int[] a,int group){
        int size=a.length;
        for(int i=1;i<size;i++){
            int temp=a[i];
            int j=i-group;
            for(;j>=0;j-=group){
                if(a[j]>temp){
                    a[j+group]=a[j];
                }else{
                    break;
                }
            }
            a[j+group]=temp;
        }
    }

③特性：

是直接插入排序的优化。

时间复杂度：O(n^1.25)到O(1.6n^1.25)；空间复杂度：O(1)；稳定性：不稳定。

2、选择排序

（1）单指针选择排序

①思想：

从第一个数开始，每次找到待排序数的最小值，与第一个数交换位置；然后开始第二个数，每次找到待排序数的最小值，与第二个数交换位置......直到最后一个数结束。

②代码实现：

public static void selectSort(int[] a){
        int size=a.length;
        for(int i=0;i<size-1;i++){
            int min=i;
            for(int j=i+1;j<size;j++){
                if(a[j]<a[min]){
                    min=j;
                }
            }
            if(i!=min){
                swap(a,i,min);
            }
        }
    }
    public static void swap(int[] a,int m,int n){
        int temp=a[m];
        a[m]=a[n];
        a[n]=temp;
    }

③特性：

时间复杂度：O(n^2)；空间复杂度：O(1)；稳定性：不稳定。

（2）双指针选择排序

①思想：

一个指针指向要排序数的最小值，一个指针指向要排序数的最大值，最小值放左边，最大值放右边，往中间遍历，但需注意：最大值在要排序数第一个的情况。

②代码实现：

public static void selectSort2(int[] a){
        int size=a.length;
        int left=0;
        int right=size-1;
        while(left<right){
            int max=right;
            int min=left;
            for(int i=left;i<=right;i++){
                if(a[i]>a[max]){
                    max=i;
                }else if(a[i]<a[min]){
                    min=i;
                }
            }
            if(max==left){
                max=min;
            }
            if(min!=left){
                swap(a,min,left);
            }
            if(max!=right){
                swap(a,max,right);
            }
            left++;
            right--;
        }
    }
    public static void swap(int[] a,int m,int n){
        int temp=a[m];
        a[m]=a[n];
        a[n]=temp;
    }

（3）堆排序

①思想：

若是升序的话，建立大根堆，每次将堆顶元素与最后一个元素交换，前n-1个元素，以第一个父结点进行向下调整......直到交换结束。

若是降序的话，建立小根堆，每次将堆顶元素与最后一个元素交换，前n-1个元素，以第一个父结点进行向下调整......直到交换结束。

②代码实现：

public static void buildPile(int[] a){
        int size=a.length;
        int parent=(size-2)/2;
        for(int i=parent;i>=0;i--){
            buildChildPile(a,i,size);
        }
    }
    public static void buildChildPile(int[] a,int parent,int size){
        int child=2*parent+1;
        while(child<size){
            if(child+1<size&&a[child]<a[child+1]){
                child=child+1;
            }
            if(a[child]>a[parent]){
                swap(a,child,parent);
            }
            parent=child;
            child=2*parent+1;
        }
    }
    public static void pileSort(int[] a){
        int size=a.length-1;
        while(size!=0){
            swap(a,0,size);
            buildChildPile(a,0,size-1);
            size--;
        }
    }

③特性：

时间复杂度：O(n*logn)；空间复杂度：O(1)；稳定性：不稳定。

3、交换排序

（1）冒泡排序

①思想：

将大的往左边放，每次遇到一个数，比后面数大，就往后交换。

②代码实现：

   public static void bubbleSort(int[] a){
        int size=a.length;
        boolean flag=true;
        for(int i=0;i<size-1;i++){
            for(int j=1;j<size-i;j++){
                if(a[j-1]>a[j]){
                    swap(a,j-1,j);
                    flag=false;
                }
            }
            if(flag){
                break;
            }
        }
    }

③特性：

时间复杂度：O(n^2)；空间复制度：O(1)；稳定性：稳定。

（2）双指针快速排序

①思想：找到一个基准值，默认为left指针，right往左移，left往右移，如果right小于基准，left大于基准，两者交换，循环进行到left<right不满足，基准值要和最后一个left交换，接着划分区间进行判断，直到区间里只有一个元素结束。

②代码实现：

public static void quickSort(int[] a){
        quickChild(a,0,a.length-1);
    }
    public static void quickChild(int[] a,int left,int right){
        if(left>=right){  //一个元素
            return;
        }
        int index=index(a,left,right); //进行交换，并找到基准值的位置
        quickChild(a,left,index-1);  //左区间接着判断
        quickChild(a,index+1,right);  //右区间接着判断
    }
    public static int index(int[] a,int left,int right){
        int temp=a[left];
        int k=left;
        while (left<right){
            while(left<right&&a[right]>=temp){
                right--;
            }
            while(left<right&&a[left]<=temp){
                left++;
            }
            swap(a,left,right);
        }
        swap(a,k,left);
        return  left;   //left后走的 right一定是走到了小于等于temp的地方
    }

③特性：