几种经典的排序算法

淡淡的烟草味﹌ 2022-05-23 02:41 199阅读 0赞

**1.冒泡排序**  
时间复杂度：O(n²)  
冒泡排序算法的运作如下：（从后往前）  
1)比较相邻的元素。如果第一个比第二个大，就交换他们两个。  
2)对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。  
3)针对所有的元素重复以上的步骤，除了最后一个。  
4)持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。  
**代码实现：**

package cn.lpq.sort;
    
    public class BubbleSort {
        public static void main(String[] args) {
            System.out.println("排序前：");
            int[] arr={
       51, 46, 20, 18, 65, 97, 82, 30, 77, 50,2,33,12,100 };
            printSort(arr);
            System.out.println("排序后：");
            bubbleSort(arr);
            printSort(arr);
    
        }
        public static void bubbleSort(int[]arr){
            for(int x=0;x<arr.length-1;x++){
                for(int y=0;y<arr.length-1-x;y++){
                    if(arr[y]>arr[y+1]){
                        int temp=arr[y];
                        arr[y]=arr[y+1];
                        arr[y+1]=temp;
                    }
                }
    
            }
        }
        public static void printSort(int []arr){
            StringBuilder res=new StringBuilder();
            res.append("[");
            for(int i=0;i<arr.length;i++){
                if(i==arr.length-1)
                    res.append(arr[i]+"]");
                else
                    res.append(arr[i]+",");
            }
            System.out.println(res.toString());
        }
    }

结果：  
![冒泡排序结果][70]  
**2.选择排序：**  
时间复杂度：O(n²)  
选择排序（Selection sort）同样也是最经典最简单的排序算法之一，特点就是简单直观。  
排序的原理：首先在未排序的序列里找到最小(大)元素，放到序列的首端，再从剩余元素中找到最小(大)的元素，放到序列的尾端。依次循环，直到排序完成。  
**代码实现：**

package cn.lpq.sort;
    
    public class SelectSort {
        public static void main(String[] args) {
            int[] arr={
       11,9,3,44,12,98,292,34,522,232};
            System.out.println("选择排序前：");
            printSort(arr);
            selectSort(arr);
            System.out.println("选择排序后：");
            printSort(arr);
        }
        public static void selectSort(int[]arr){
            for(int x=0;x<arr.length-1;x++){
                for(int y=x+1;y<arr.length;y++){
                    if(arr[x]>arr[y]){
                        int temp=arr[y];
                        arr[y]=arr[x];
                        arr[x]=temp;
    
                    }
                }
    
            }
        }
        public static void printSort(int []arr){
            StringBuilder res=new StringBuilder();
            res.append("[");
            for(int i=0;i<arr.length;i++){
                if(i==arr.length-1)
                    res.append(arr[i]+"]");
                else
                    res.append(arr[i]+",");
            }
            System.out.println(res.toString());
        }
    }

结果：  
![选择排序结果][70 1]

**3.快速排序：**  
**快排思想：**  
快速排序的原理：选择一个关键值作为基准值。比基准值小的都在左边序列（一般是无序的），比基准值大的都在右边（一般是无序的）。一般选择序列的第一个元素。  
一次循环：从后往前比较，用基准值和最后一个值比较，如果比基准值小的交换位置，如果没有继续比较下一个，直到找到第一个比基准值小的值才交换。找到这个值之后，又从前往后开始比较，如果有比基准值大的，交换位置，如果没有继续比较下一个，直到找到第一个比基准值大的值才交换。直到从前往后的比较索引>从后往前比较的索引，结束第一次循环，此时，对于基准值来说，左右两边就是有序的了，接着分别比较左右两边的序列，重复上述的循环。  
时间复杂度为：nlog(n)

package cn.dataStructures.Sort;
    //快速排序算法--利用递归
    public class QuickSort {
        public static void main(String[] args) {
            int []arr={
       12,20,5,16,15,1,2,100,30,45,23,9};
            int low=0;
            int high=arr.length-1;
            quickSort(arr,low,high);
            printSortArr(arr);
        }
        public static void quickSort(int [] arr,int low,int high){
            int start=low;//设置可以移动的最小值
            int end=high;//设置可以移动的最大值
            int key=arr[low];//设置标识
            while(start<end){
       //整体大循环
                while(start<end&&arr[end]>=key)//先从循环后面的，从后向前，找小于key的
                    end--;
                if(arr[end]<=key){
                    int temp=arr[end];
                    arr[end]=arr[start];
                    arr[start]=temp;
                }
                while(start<end&&arr[start]<=key)//循环前面的，从前往后找大于key的值
                    start++;
                if(arr[start]>=key){
                    int temp=arr[start];
                    arr[start]=arr[end];
                    arr[end]=temp;
                }
            }
            //递归调用
            if(low<start)
                quickSort(arr,low,start-1);
            if(end<high)
                quickSort(arr,end+1,high);
    
        }//打印输出数组
        public static void printSortArr(int []arr){
            StringBuilder res=new StringBuilder();
            res.append("[");
            for(int i=0;i<arr.length;i++){
                if(i==arr.length-1){
                    res.append(arr[i]+"]");
                }
                else{
                    res.append(arr[i]+",");
                }
            }
            System.out.println(res.toString());
        }
    }

结果：  
![快速排序结果][70 2]  
**4.归并排序：**  
时间复杂度为：nlog(n)  
**排序原理：**  
（1）申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列  
（2）设定两个指针，最初位置分别为两个已经排序序列的起始位置  
（3）比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置  
（4）重复步骤3直到某一指针达到序列尾  
（5）将另一序列剩下的所有元素直接复制到合并序列尾

package cn.dataStructures.Sort;
    
    /** * **归并排序（理解描述）**: * 思想： * 1.对原始序列arr进行一半分割，设置原始序列的第一个索引low和最后一个索引值high，并创建临时序列 * 2.求出原始序列的中间索引mid=(low+high)/2，根据mid对序列分割 * 3.判断low是否小于high，满足则递归调用步骤1和2，一直对分割的序列再分割，直到剩余一个元素为止 * 4.对分割的序列分别根据其索引指向的元素值进行比较，小的则放入临时序列中，各序列索引加1、、 * 5.对剩余没有加入到临时序列中的元素直接添加到临时序列的最后的位置 * 6.将临时序列赋值给原始序列，此时原始序列就是已经排好序的序列 * @author lpq * */
    
    public class MergeSort { 
        public static void main(String[] args) {
            System.out.println("排序前：");
            int[] arr={
       51, 46, 20, 18, 65, 97, 82, 30, 77, 50 };
            printSort(arr);
            mergeSort(arr,0,arr.length-1);
            System.out.println("排序后：");
            printSort(arr);
        }
        //切分原始数组
        public static void mergeSort(int[]arr,int low,int high){
            int mid=(low+high)/2;//将序列按中间分开
    
            if(low<high){
                //分开左边
                mergeSort(arr,low,mid);
                //右半边
                mergeSort(arr,mid+1,high);
                //将左右已经排序好的合并
                merge(arr,low,mid,high);
            }
    
    
        }
        public static void merge(int[]arr,int low,int mid,int high){
            /** * 这里的start和end分别是左半边序列和右半边序列的其实指针，分别指向各半边序列的第一个位置，随着的元素的比较而发生改变 * 而low和high是不发生改变的，一般来说low指的是序列的第一个索引0即low=0，high=arr.lenth-1, * low和length值不发生改变 */
            //临时数组（序列）
            int [] temp=new int[high-low+1];
            //左半边序列的指针（一般指向第一个位置low）
            int start=low;
            //右半边序列的指针
            int end=mid+1;
            //临时数组序列的索引
            int k=0;
            //把小的元素加入到临时数组中
            while(start<=mid&&end<=high){
                if(arr[start]<arr[end])
                    temp[k++]=arr[start++];
                else
                    temp[k++]=arr[end++];
            }
            //把左边剩余元素加入到临时数组的后面
            while(start<=mid)//这里不能用if判断，因为if只能判断一次，while只要满足条件就会一直循环判断下去
                temp[k++]=arr[start++];
            //把右半边剩余元素加入到临时数组的后面
            while(end<=high)
                temp[k++]=arr[end++];
            //将排序好的临时数组复制给原始数组arr
            for(int i=0;i<temp.length;i++){
                arr[i+low]=temp[i];
            }
        }
        public static void printSort(int []arr){
            StringBuilder res=new StringBuilder();
            res.append("[");
            for(int i=0;i<arr.length;i++){
                if(i==arr.length-1)
                    res.append(arr[i]+"]");
                else
                    res.append(arr[i]+",");
            }
            System.out.println(res.toString());
        }
    }

结果：  
![归并排序结果][70 3]  
**时间复杂度分析:**  
递归法分析：  
因为归并排序实现要将原始序列分为2部分，然后将这2个序列排序好后再赋值给临时序列temp，假设原始序列的元素个数为N，则时间复杂度的主要表达式为：T(N)=2T(N/2)+N;  
1.首先将N/2带入主要表达式。结果：2T(N/2)=2(2T(N/4))+N=4T(N/4)+N,根据主要表达式可知：2T(N/2)=T(N)-N,所以可简化为：T（N）=4T(N/4)+2N  
2.将N/4带入主表达式，同理可得到：T(N)=8T(N/8)+3N,可类比为：T(N)=2^kT(N/2^k)+kN  
3.利用k=log(N),可得T(N)=NT(1)+Nlog(N)=Nlog(N)+N  
4.时间复杂度为：O(Nlog(N))  
**二分搜索法：**  
二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。  
注意：二分查找前提条件是：该序列有序

package cn.lpq.sort;
    
    import java.util.Arrays;
    
    //二分查找前提是该数组有序
    public class BinarySerch {
        public static void main(String[] args) {
            int []arr={
       11,22,33,44,55,66,77};
            Arrays.sort(arr);//对数组排序
            System.out.println(binarySerch(arr,55));
        }
        public static int binarySerch(int[]arr,int value){
            int min=0;
            int max=arr.length-1;
            int mid=(min+max)/2;
            while(arr[mid]!=value){
                if(arr[mid]>value){
                    max=mid-1;
                }
                else if(arr[mid]<value){
                    min=mid+1;
                }
                mid=(min+max)/2;
            }
            if(min>max){
                return -1;//说明数组为空或所查找元素不存在
            }
            return mid;
    
        }
    }

[70]: /images/20220523/ca4baf9423cb4d22bca63ab9718238a6.png
[70 1]: /images/20220523/9adde6c9bde24505a9b1c7c7b75949a7.png
[70 2]: /images/20220523/feaae39022774f1094b12c60ad8d0b9b.png
[70 3]: /images/20220523/3ad5369093bc4511bd53e6b0c54e2340.png