七大排序算法总结

冷不防 2021-09-11 06:20 370阅读 0赞

# 1.快速排序 #

核心思路：  
1.先从数列中取出一个数作为基准数。  
2.分区过程，将比这个数大的放左边，比这个数小的放右边。  
3.在对左右区间重复第二步，直到各区间只有一个数  
*不稳定的排序算法*

public static int partition(int[] a,int low,int high){
            int temp=a[low];
            while(low<high){
                while(low<high&&a[high]>=temp){
                    high--;
                }
                if(low<high){
                    a[low]=a[high];
                    low++;
                }
                while(low<high&&a[low]<temp){
                    low++;
                }
                if(low<high){
                    a[high]=a[low];
                    high--;
                }
            }
            a[low]=temp;
            return low;
        }
    
        public static void quickSort(int[] a,int low,int high){
            if(low<high){
                int i=partition(a,low,high);
                quickSort(a,low,i);
                quickSort(a,i+1,high);
            }
        }

# 2.冒泡排序 #

核心思路：  
每一轮依次进行两两比较，将最大的数沉底  
外圈：因为只剩下一个数时不用再比较，所以共须循环n-1次;  
内圈：第一圈比较n个数，需要n-1次，最大数沉底，第二圈比较n-1个数，需要n-2次。在第i次排序中，比较次数n-i；总移动次数n(n-1)/2；  
*稳定的排序算法*

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

# 3.直接插入排序 #

核心思路：每次将一条数据插入到有序序列中，将大于该数字的数据统一后移一位，形成新的有序序列。重复到全部有序。（顾名思义）  
监视哨：无需重复判断数组下标是否越界，将每个a\[i\]赋给a\[0\]，当比较到0个位置时自动成立退出循环  
*稳定的排序算法*

public static void insertSort(int[] a){
            int i,j;
            for(i=1;i<a.length;i++){
                if(a[i]<a[i-1]){
                    int temp=a[i];
                    for(j=i-1;j>=0&&a[j]>temp;j--)
                        a[j+1]=a[j];
                    a[j+1]=temp;
                }
            }
        }

# 4.希尔排序 #

又称缩小增量排序。直接插入排序的优化，利用直接插入排序N较小时效率高与N基本有序时效率高的特点，将数据分组进行直接插入排序。  
*不稳定的排序算法*

public static void shellSort(int[] a){
            int step=a.length/2;
            int i,j;
            while(step>0){
                for(i=step;i<a.length;i++){
                    int temp=a[i];
                    for(j=i-step;j>=0&&a[j]>temp;j-=step){
                        a[j+step]=a[j];
                    }
                    a[j+step]=temp;
                }
                step=step/2;
            }
        }

# 5.直接选择排序 #

思路：每一圈比较获得最小值的下标，并付给当前数组的第一位。  
时间复杂度：外循环n-1次，内圈循环n-1-i次 O(n^2)  
*不稳定的排序算法*

public static void selectSort(int[] a){
            for(int i=0;i<a.length-1;i++){
                int min=i;
                for(int j=i+1;j<a.length;j++){
                    if(a[j]<a[min])
                        min=j;//找到最小值的下标
                }
                if(min!=i){
                    int temp=a[i];
                    a[i]=a[min];
                    a[min]=temp;
                }
            }
        }

# 6.归并排序 #

利用分治法。先递归地分解数列，再合并**有序**数列

public static void mergeArray(int[] a,int first,int mid,int last,int[] temp){
            int i=first,j=mid+1;
            int m=mid,n=last;
            int k=0;
            while(i<=m&&j<=n){
                if(a[i]<a[j])
                    temp[k++]=a[i++];
                else
                    temp[k++]=a[j++];
            }
            while(i<=m)
                temp[k++]=a[i++];
            while(j<=n)
                temp[k++]=a[j++];
            for(i=0;i<k;i++)
                a[first+i]=temp[i];
        }
        
        public static void mergeSort(int[] a,int first,int last,int[] temp ){
            if(first<last){
                int mid=(first+last)/2;
                mergeSort(a,first,mid,temp);//左边有序
                mergeSort(a,mid+1,last,temp);//右边有序
                mergeArray(a,first,mid,last,temp);//合并两个有序数列
            }
        }

# 7.堆排序 #

重在理解筛选法调整堆 通过它构造堆 和 调整堆  
每次通过每次构造小顶堆获得最小值，依次获得有序序列  
为无序序列创建堆的时候时堆完全二叉树从下往上筛选，最后一个非叶子节点编号\[n/2\]-1  
时间复杂度最坏情况O(n\*log2n) *不稳定的排序算法*

//筛选法调整堆算法 将以LOW为根节点的子树调整成小顶堆
        public static void sift(int[] a,int low,int high){
            int i=low;
            int j=2*i+1;
            int temp=a[i];
            while(j<high){
                if(j<high-1&&a[j]>a[j+1])
                    j++;
                if(temp>a[j]){//若父母结点值较大
                    a[i]=a[j];//孩子节点中较小值上移
                    i=j;
                    j=2*i+1;
                }
                else
                    j=high+1;//退出循环
            }
            a[i]=temp;
        }
        
        public static void heapSort(int[] a){
            for(int i=a.length/2-1;i>=0;i--){
                sift(a,i,a.length);
            }
            for(int i=a.length-1;i>0;i--){
                int temp=a[0];
                a[0]=a[i];
                a[i]=temp;
                sift(a,0,i);
            }
        }

笔记本上写完 又敲到电脑上花了不少时间，希望自己常看看，如果对你有用点个赞/留个言呗~